确定性有限状态自动机 (DFA) 考试题

Question

问题是：

根据以下内容设计确定性有限状态自动机 (DFA) 规格：

 它的字母表是 {0, 1}。

 它的语言由所有具有奇数个 1 的单词组成。

 0 将不被接受（即使它们是字母表的一部分）。

所以我确定这意味着它只会接受例如“111”并拒绝“11”

我的第一次尝试，虽然它有效（接受 111 拒绝 11）它正在接受 0

我的第二次尝试是先尝试创建一个转换 table 然后是图表，但是 q1 没有到 q2 的阶段，除非我 table 做错了

我最后的尝试..我认为有效吗？但我不确定这张图是否有效

有人可以告诉我 3 个图表中哪一个是 correct/heading 正确的方法以及我将如何解决 this/do 转换 table

更新：你的意思是这样吗@Pavel Pája Halbich

Answer 1

你的最终图表很好（但无效）。要使其有效，您需要添加转换：

• q1 -> q2 使用 0
• q2 -> q2 使用 0,1（这是典型的失败状态）

然后你将有 3 个状态，并且对于每个状态定义到其他状态的转换，一个起始状态 (q0) 和一组接受状态 ({q1})。