Search code examples
computation-theory

{ w | at every odd position of w is a 1}

The task is to construct a DFA for this language over the alphabet {0,1}.

I have constructed a DFA that consists of 4 states and that does not accept an empty word. However, in the answers they give a 3 state DFA that accepts it.

Why should my DFA accept an empty word if in the empty word there is no 1 at the odd position which means that it is not in the language?

Solution

  • I think you are confused why should an empty string be a part of a mentioned set.

    Let's take a look at another example. Consider you have a set of all possible strings having every character equal to 0. Such strings would be 0, 00, 000, 00000, etc. What about an empty string *? It actually pertain to this set as well. Empty string does not violate the definition of the set.

    Compare this example with yours. You should check every odd position of the string and if you'll find anything other than 1 you should say that it is not an element of you set. It is not said anything about whether a string should have an odd position to be checked.