标签: finite-automata

例如,在给我的作业中,我们被要求查明两个正则表达式是否相等.

(a+b+c)*  and ((ab)**c*)*

我的问题是如何做到这一点？如果我绘制两者的转换图,然后通过它运行几个字符串并显示两个TG都能够接受它,这是否足以证明？如果没有,我该怎么办？对此有一种数学/公理方法吗？

提前致谢.

编辑:还有一件事我想清楚哪一点与这个问题有关.下面照片中描绘的两个FA是否相同？

即上图中的(1)和(2)是否相同？

找不到任何肯定的东西.任何epsilon过渡的NFA都是epsilon-NFA？谢谢.

我想写一些能够绘制有限状态自动机的东西.有谁知道任何与此相关的算法？

编辑:我应该提一下我对graphviz的了解.我想构建自己的绘图程序/函数,所以我正在寻找的是一些更理论化的东西/算法的伪代码.

有没有人对构建两个给定DFA的并集算法有直截了当的描述？例如,假设我们有两个DFA超过{0,1}

{w|w has an odd number of characters}
  w has states A and B

delta | 0  | 1
----------------
  A   | B  | B
----------------
  B   | A  | A


{x|x has an even number of 1s}
  x has states a and b

delta | 0  | 1
----------------
  a   | a  | b
----------------
  b   | b  | a

我有一个结果转换表显示联合:

delta | 0  | 1 
----------------
  Aa  | Ba | Bb
----------------
  Ab  | Bb | Ba
---------------- …

我的朋友们觉得我被卡住了.有人可以解释我从"功能算法设计珍珠"第11章("不是最大段总和")中挑选方程式.

这是问题(稍微简化)让我们有一些具有给定转换的状态:

data State = E | S | M | N 
                deriving (Show, Eq) 

step E False = E 
step E True = S 
step S False = M 
step S True = S 
step M False = M 
step M True = N 
step N False = N 
step N True = N 

现在,我们来定义选择:

 pick q = map snd . filter ((== q) . fst) . map (\a -> (foldl step E a, a))

作者声称以下七个等式成立:

pick E xs …

所以这不是关于泵浦引理及其工作原理,而是关于先决条件.

你可以阅读网络中的任何地方,常规语言必须通过抽取引理,但现在任何人都会谈论有限语言,它实际上是常规语言的一部分.

所以我们可能都是aggree,以下语言是有限语言,也是常规语言,但它肯定不会通过泵引理:

L = {'abc', 'defghi'}

请告诉我,如果没有人写它或为什么我们错了 - 甚至没有.

哪个是确定两个自动机之间等价的最佳或最简单的方法？

即,如果给出两个有限自动机A和B,我如何确定两者是否识别相同的语言？

它们既具有确定性,也具有不确定性.

什么是Python最完整的有限自动机库,它能够执行基本操作,例如:

• 最小化,
• 非确定性有限自动机的确定
• 这些自动机等生成的语言的联合,交集和产品等.

我找到的所有库都不完整或者不是即插即用的.

?: Q × ? ? Q用英语怎么说？描述什么×和?意思也会有所帮助.

下午好,

有没有人知道在.NET 中使用Levenshtein DFA(确定性有限自动机)的"开箱即用"实现(或者很容易翻译)？我有一个非常大的字典,有超过160000个不同的单词,我希望,给出一个内在的单词w,以高效的方式在Levenshtein距离中找到所有已知单词最多2个w.

当然,具有在编辑距离处计算所有可能编辑的功能,给定单词中的一个并将其再次应用于这些编辑中的每一个解决了该问题(并且以非常简单的方式).问题是效率刍议---给予7字母的单词,这已经可以采取超过1秒即可完成,而我需要的东西很多更有效的---如果可能的话,因为它与莱文斯坦的DFA,这需要O(解决方案| w |)步骤.

编辑:我知道我可以通过一些学习来构建我自己的问题方法,但目前我无法负担阅读Schulz和Mihov长达60页的文章.

非常感谢你.