正则表达式 – 正则表达式到DFA

>你的自动机宝贝
>您的自动机不接受ab
>您的自动机不是DFA,至少通过一些严格的定义

关于第一点：从q1开始,我们看到b,转到q2,看到a,转到q3,看到b,然后转到q4,这是接受的.我们看到了bab并接受了它.

关于第二点：从q1开始,我们看到了一个但没有定义过渡.自动机“崩溃”并且无法接受.因此,不接受以a开头的字符串,包括ab.

关于第三点：通常要求DFA显示所有状态和转换,包括永不导致任何接受状态的死状态和转换.您不显示所有过渡,也不显示自动机中的所有状态.

您可以使用Myhill-Nerode定理来确定您的语言的最小DFA的状态数.我们注意到空状态可以附加空字符串,b或ab来获取语言中的字符串; a可以附加b;和b可以附加空字符串.没有任何东西可以附加到aa,bb或ba来获取语言中的字符串(所以这些是无法区分的);但是ab可以附加空字符串(因此与b无法区分).

如此确定的等价类对应于最小DFA中的状态.我们的等价类是：

>字符串就像空字符串
>像b这样的字符串
>像一个字符串
>像aa一样的字符串

我们注意到b是语言,因此第二类将对应于接受状态.我们注意到没有任何东西可以附加到aa以获取语言中的字符串,因此该类对应于DFA中的死状态.我们通过查看新符号附加到哪个新等价类来编写这些状态之间的转换：

>附加一个把我们放入(3),因为在空字符串后附一个给出了(3)中的一个.附加b将我们放入(2),因为将b附加到空字符串给出b中的(2)
>附加一个把我们放入(4)因为附加一个to给b给出了ba,就像它不是语言中任何字符串的前缀.附加b,我们通过类似的论证到达(4).
>附加一个我们得到aa并在(4).附加b我们得到ab就像b,所以我们在(2).
>从死亡状态的所有转变都返回到死亡状态; a和b都回到(4).

你最终会得到类似的东西：

q1 --a--> q3
 |        /|
 b  --b--< a
 | /       |
 vv        v
q2 -a,b-> q4 
           ^ a,b
           _/

或者以表格形式：

q    s    q'
==   =    ==
q1   a    q3
q1   b    q2
q2   a    q4
q2   b    q4
q3   a    q4
q3   b    q2
q4   a    q4
q4   b    q4