regex - 正则表达式转 DFA

Question

有人能告诉我所附的 DFA 是否正确吗？

我想为具有字母 Σ ={a, b} 的语言提供 DFA

我需要 DFA ----> A={ε, b, ab}

Answer 1

不，有多种原因:

您的自动机 bab

您的自动机不接受 ab

您的自动机不是 DFA，至少在某些严格的定义中是这样的

关于第一点:从q1开始，我们看到b ，转至 q2 ，见 a ，转至 q3 ，见 b ，然后转到 q4 ，这是接受。我们看到了 bab并接受了它。

关于第二点:从q1开始，我们看到a但没有明确的过渡。自动机“崩溃”并且无法接受。所以没有以 a 开头的字符串被接受，包括 ab .

关于第三点:DFA 通常需要显示所有状态和转换，包括死状态和永远不会返回任何接受状态的转换。您不会显示所有转换，也不会显示自动机中的所有状态。

您可以使用 Myhill-Nerode 定理来确定您的语言的最小 DFA 具有多少个状态。我们注意到空状态可以附加空字符串，b或 ab获取语​​言中的字符串； a可以有b附加；和 b可以附加空字符串。什么都不能附加到 aa , bb , 或 ba获取语​​言中的字符串(因此无法区分)；但是 ab可以附加空字符串(因此与 b 无法区分)。

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

字符串如空字符串

字符串如 b

字符串如 a

字符串如 aa

我们注意到 b是在语言中，所以第二个类将对应于一个接受状态。我们注意到什么都不能附加到 aa获取语​​言中的字符串，因此该类对应于 DFA 中的死状态。我们通过查看新符号的附加将我们置于哪个新等价类来编写这些状态之间的转换:

附加 a由于附加 a 将我们置于 (3)空字符串给出 a在(3)中。附加 b由于附加 b 将我们置于 (2)空字符串给出 b这是在(2)

附加 a由于附加 a 将我们置于 (4)到 b给 ba就像 aa因为它不是语言中任何字符串的前缀。附加 b ，我们通过类似的论证得出(4)。

附加 a我们得到 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