识别没有 3 个连续零的语言的自动机

Question

我会创建一个有限状态自动机，它可以识别不包含 3 个连续零的 0 和 1 字符串的语言。 我尝试执行以下自动机，但不完整，例如，它无法识别字符串：1001110

如何更改？对于其余的，我解决练习的推理是否正确？ 非常感谢

Answer 1

我用油漆做了这个，所以看起来不太好，但是，尝试下面的自动化。

Answer 2

您的起始状态 q0 是通过读取零无法达到的状态。当您在自动机中正确建模时，您必须允许自动机从状态 q0 读取最多两个零，因此您需要状态 q1（通过精确读取一个连续零来达到）和 q2（通过精确读取两个连续零来达到）。

每当您读取 1 时，您将处于读取 0 无法达到的状态。 现在的问题是，你需要多少个状态？

有限自动机中允许有多个最终状态。在这种情况下，你必须有多个结束状态，因为任何时候你读取一个1，你都必须达到一个允许读取两个连续的零的状态，而每次你读取一个零时，你都会达到一个允许读取两个连续零的状态。 not 允许读取两个连续的零，并且您的语言具有以 0 结尾的字符串以及以 1 结尾的字符串。

Answer 3

这是有限状态自动机的经典问题。 Divyesh Jesadiya 给出了正确答案。如果你想通过完成更多类似于“识别没有三个连续零的语言的自动机”的任务来更加熟悉有限状态自动机，我推荐一款将于 2023 年 11 月在 Steam 上推出的游戏：有限状态自动机挑战。它在有限状态自动机上提供 30 个任务。完成这些任务会让你对它有更深入的了解。