regex - 正则表达式到 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但没有定义的过渡。自动机“崩溃”并且无法接受。因此不接受以 开头的字符串a，包括ab.

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

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

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

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

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

1. 附加a将我们置于（3）中，因为附加a到空字符串会给出a（3）中的内容。附加b将我们置于（2）中，因为附加b到空字符串会给出b（2）中的

2. 追加a将我们置于 (4) 中，因为追加ato就像b它不是语言中任何字符串的前缀一样。附加，我们通过类似的论点到达（4）。baaab

3. 附加a我们得到aa并且在（4）中。附加b我们得到ab的结果就像b我们在（2）中一样。

4. 所有从死状态的转换都返回到死状态；两者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 对那种语言是正确的。