{ w | w 的每个奇数位置都是 1}

Question

任务是在字母表 {0,1} 上构建该语言的 DFA。

我构建了一个由 4 个状态组成且不接受空字的 DFA。然而，在答案中，他们给出了接受它的 3 状态 DFA。

如果空词中奇数位置没有 1（这意味着它不在该语言中），为什么我的 DFA 应该接受空词？

Answer 1

唯一的要求是奇数位置上的任何符号都必须是1。对于特定数量的符号没有要求，并且具体而言不要求至少有一个。

因此，具有初始状态 where0导致拒绝状态以及 where1导致接受任一符号并返回到开始的第二状态的 DFA 将是可接受的答案，并且将接受空字符串。这将是一个三状态机：