DFA 用于以“1”开头并包含“11”的输入。为什么它不接受这个输入？

Question

我正在尝试创建一个确定性有限自动机（DFA）来接受以“1”开头并且在 {0,1} 上包含子字符串“11”的二进制字符串。

这是我创建的 DFA：

问题：

• 输入字符串：“10011”
• 预期结果：已接受
• 实际结果：拒绝

我尝试过的：

• 我通过 DFA 跟踪了字符串“10011”的转换，但最终处于不接受状态。
• 我已经仔细检查了我的状态转换和接受状态，但我不知道我可能在哪里出了问题。

问题：

我的 DFA 设计有什么问题？如何让 DFA 正确处理字符串？

Answer 1

从你的DFA中可以清楚地看出，输入“01”后，最终处于“trap”状态。这是不对的。唯一一次不可能再获得有效输入的情况是输入以“0”开头的情况。对于任何以“1”开头的输入，应该始终有一种方法来扩展输入以进入接受状态。所以不应该有从状态 q₁ 到“陷阱”状态的转换。

您需要一个附加状态，q₃，这是您已读取一个或多个“0”的状态（其后面可能仍然有“1”甚至“11”）。

以下是带有附加状态的 DFA 的外观：