DFA 5 种状态的状态图

Question

设 F 为 {0,1} 上所有不包含由奇数个符号分隔的 1 的字符串的语言。给出具有识别 F 的五个状态的 DFA 的状态图。 （您可能会发现首先找到 F 的补集的 4 态 NFA 很有帮助。）

如何提出解决方案

Answer 1

让我们稍微分析一下。一些接受的输入是：

00000000000
100000
0010010
01100

值得注意的是，每个少于两个“1”符号的输入都会被接受。如果有两个，它们之间的符号是零，并且应该有偶数个。

最重要的认识是，输入中不能有三个或更多“1”符号，因为第三个符号肯定会违反规则，因为它与第一个“1”或第二个“1”配对。一个例子：

1001001

虽然中间的 1 没有违反约束，但它遵循，外面的两个do违反了它（因为中间的“1”包含在计数中，使其成为奇数）。

所以我们可以有这些状态：

• 𝑞₀：到目前为止没有遇到“1”符号
• 𝑞₁：到目前为止遇到了一个“1”符号，后面跟着偶数个零（如果下一个符号是“1”则可以接受）
• 𝑞₂：到目前为止遇到了一个“1”符号，后面跟着奇数个零（如果下一个符号是“1”，那么不是可以接受的）
• 𝑞₃：到目前为止遇到了两个“1”符号，它们之间有偶数个零，第二个“1”后面跟着任意数量的零（仅）
• 𝑞₄：遇到三个“1”符号，或者遇到两个“1”符号，其间有奇数个零。这是水槽（不接受输入）。

DFA图：