Sipser Exercise 1.61


let and define the family of languages:

Theorem: Any DFA recognizing must have at least states.


Proof: Consider the set of words and note that there are unique words in . We will show that any DFA must take different strings in to different states.

Let such that . Write and . Since they are unequal, let be the first index at which and differ. Then, between and , one must be an and one must be a . WLOG, suppose that and (otherwise, relabel and ).

Now, we want to construct new strings and , adding characters at the end until has its in the th spot from the end, and has its in the th spot from the end. So let and . Of course, we could have added s to the end as well, the choice doesn’t matter. Then , and the index from the end is . So, since and , and .

Now, notice that , because is accepted.

At the same time, because is rejected.

If it were the case that , then the same starting point and the same string would drive the machine to different states, which is a contradiction. So it must be the case that .

So since each of the strings in must drive the machine to a unique state, must have at least states.