创建包含“11”或以“10”结尾的 DFA

Question

我正在尝试构建一个包含“11”或以“10”结尾的 DFA（仅限二进制）。

我尝试执行以下操作：

$q2$ 和 $q3$ 正在接受状态

状态01$q0$$q0$$q1$$q1$$q3$$q2$$q2$$q3$$q2$$q3$??????

这就是我到目前为止所做的。

从 q0 开始，如果我们读到 0，我们就留在 q0，否则如果我们读到 1，我们就转到 q1。

从 q1 开始，如果我们读到 0，我们可以转到 q3，并且 q3 正在接受状态（因此它以 10 结尾），否则如果我们读到 1，我们就转到接受状态 q2，它包含 11。

从q2开始，如果我们读到1，我们可以留在q2，如果我们读到0，我们可以转到q3，还是我应该改变它？

在第三季度，我不确定。

Answer 1

我首先要明确状态是什么，然后应该清楚每个输入值的作用：

状态（说明）01$q0$（初始/最后=0）$q0$$q1$$q1$（最后=1，而不是11）$q3$$q2$$q2$（已经有11个）$q2$$q2$$q3$（当前 10）$q0$$q1$

换句话说，如果您最终处于状态

$q2$

 或 

$q3$

，则您已满足 DFA 结束条件（找到 

11

 或以 

10

 结束）。