我的 DFA 正确吗？ （任意长的 0 和 1 序列）

Question

对于我的练习，我应该创建两个 DFA。如果这个问题很愚蠢，我事先很抱歉，我还在学习。 任务具体是：

在字母表 Σ={1,0} 上构造一个 DFA，接受以下常规语言。

a) 由零和一组成的任意长序列，以零结尾，后跟零或一。 b) 由 0 和 1 组成的任意长序列，以 0 开头并以 1 结尾。

这些是我的 DFA：

它们几乎相同（除了接受状态），我想知道它们是否正确？也许我错过了什么？

我尝试画两个DFA。他们似乎接受这些语言，但我认为还有更多……这是可以避免的吗？还是仍然正确？

Answer 1

第一个DFA

第一种语言的 DFA 仅接受状态，并接受所有 0 和 1 的序列。例如，它接受任何不带零的字符串，但我们需要唯一但最后一个输入符号为零。 .

对于第一种语言，您需要四种状态：

• 𝑞₀：最近两次读取中没有遇到

  0

  。这也是开始状态，但不是接受状态。
• 𝑞₁：最后一个符号是

  0

  ，但前面没有

  0

  。所以这不是接受状态。
• 𝑞₂：最后两个符号是

  01

  。接受状态。
• 𝑞₃：最后两个符号是

  00

  。接受状态。

看起来像这样：

第二次DFA

您的第一语言的 DFA 将接受“1”，这不遵守以“0”开头的规则。另外，如果输入以“1”开头，则该输入中没有任何内容可以使其被接受，因此您需要一个“接收器”，即不是接受状态并且无法从该状态转换到另一个状态的状态状态。

同样，我们需要四种状态：

• 𝑞₀：开始状态。
• 𝑞₁：输入以

  0

  开始，到目前为止最后一个符号是

  0

  。这不是接受状态。
• 𝑞₂：输入以

  0

  开始，到目前为止最后一个符号是

  1

  。接受状态。
• 𝑞₃：输入以

  1

  开头，因此无论后面如何，都无法接受。这是一个水槽。

看起来像这样：