DFA 正则表达式

Question

谁能告诉我附加的 DFA 是否正确？

我想为字母表 Σ ={a, b}

的语言提供 DFA

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

Answer 1

不，有多种原因：

1. 你的自动机bab
2. 你的自动机不接受ab
3. 你的自动机不是 DFA，至少从一些严格的定义来看是这样

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

关于第二点：从 q1 开始，我们看到 a 但没有定义的过渡。自动机 "crashes" 无法接受。所以不接受以 a 开头的字符串，包括 ab.

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

您可以使用 Myhill-Nerode 定理来确定您的语言的最小 DFA 有多少个状态。我们注意到，空状态可以附加空字符串 b 或 ab 以获取语言中的字符串； a 可以附加 b；并且 b 可以附加空字符串。不能向 aa、bb 或 ba 附加任何内容以获取该语言的字符串（因此它们无法区分）；但是 ab 可以附加空字符串（因此与 b 没有区别）。

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

1. 类似空串的字符串
2. 像b
这样的字符串
3. 像a
这样的字符串
4. 像aa
这样的字符串

我们注意到 b 在语言中，所以第二个 class 将对应于一个接受状态。我们注意到无法将任何内容附加到 aa 以获取语言中的字符串，因此此 class 对应于 DFA 中的死状态。我们通过查看新符号的附加 class 使我们处于以下状态来编写这些状态之间的转换：

1. 追加 a 使我们进入 (3)，因为将 a 追加到空字符串会得到 a，它在 (3) 中。追加 b 使我们进入 (2)，因为将 b 追加到空字符串会得到 b，它位于 (2)

2. 追加 a 使我们进入 (4)，因为将 a 追加到 b 得到 ba 就像 aa因为它不是语言中任何字符串的前缀。追加 b，我们通过类似的论证得出 (4)。

3. 追加 a 我们得到 aa 并且在 (4) 中。追加 b 我们得到 ab 就像 b 所以我们在 (2).

4. 所有从死状态return到死状态的转变； 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

Answer 2

我认为此 DFA 对于该语言是正确的。