需要帮助创建一个 5 状态 DFA，如果二进制字符串的十进制值等于或大于 6，则接受该字符串。字符串从左到右读取

Question

我尝试这样做，但它错误地处理了字符串为 1000 的情况。（q4 是这里的接受状态，a0 是初始状态。）我的 DFA 的图像位于下面的 imgur 链接中： DFA ().

必须有 5 个状态，不能多也不能少。

Answer 1

初始的“0”字符不应移动到另一个状态，因为它们不会影响输入表示的值。所以第一个状态应该有一个“0”循环。

您应该能够判断每个状态代表哪些值。

当输入为“11”（您的 q₂）时，如果后面有另一个字符，则应该始终导致接受状态，而不是两个不同的状态。

更正如下：

• q₁：进入状态，值为0
• q₂：值 1
• q₃：值 2
• q₄：值 3、4 或 5
• q₅：所有其他值（即 >= 6）=> 接受状态。