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

Question

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

我构建了一个包含 4 个状态且不接受空词的 DFA。但是，在答案中，他们给出了接受它的 3 状态 DFA。

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

Answer 1

唯一的要求是任何奇数位置的符号必须是1。对特定数量的符号没有要求，特别是至少有一个。

因此，初始状态为 0 的 DFA 会导致拒绝状态，1 会导致第二个状态接受任一符号，returns 会开始是一个可接受的答案，并且会接受空字符串。这将是一个三态机：

Answer 2

我想你很困惑为什么一个空字符串应该是提到的集合的一部分。

我们再来看一个例子。假设您有一组所有可能的字符串，每个字符都等于 0。这样的字符串将是 0、00、000、00000 等。空字符串 * 怎么样？它实际上也属于这个集合。空字符串不违反集合定义。

将此示例与您的示例进行比较。您应该检查字符串的每个奇数位置，如果您发现 1 以外的任何位置，您应该说它不是您设置的元素。对于一个字符串是否应该有一个奇数位置要检查没有任何说明。