**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.