# Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states

How can you prove that any DFA accepting the language generated by the regular expression $$\{0|1\}^*0\{0|1\}^n$$ requires at least $$2^{n+1}$$ states?

I first attempted induction on $$n$$. But I don't even see how to prove the base-case, like if $$n=1$$. You need the DFA to take any string and, when it encounters a 0, get set down a track of checking that $$n$$ characters follow. If it's fewer than $$n$$ then fine you reject. But if there are more characters, to sort of re-set it so that it looks for the first 0 after the earlier one was found. But DFAs don't have that kind of memory.

And once you've established the base-case, the inductive case doesn't seem clear either. If you know the result is true up to $$n$$, then if you consider the regex with $$n+1$$ then you get a DFA which accepts it. You intuitively want to remove the accepting states and "move them back" one vertex in the graph. Now you have a DFA with at least $$2^n$$ states. But how do you know that you needed $$2^n$$ accepting states so that the net number of accepting states is then $$2^{n+1}$$?

This isn't about induction, it's about proving that the correct DFA must have enough memory to remember everything about the last $$n+1$$ characters. The very number $$2^{n+1}$$ should have been a clue to this.

Imagine that the DFA has just now read some prefix that's longer than $$n+1$$, but it doesn't yet know if there are any more characters left. Ask the question: what must the DFA currently remember?

• Well, clearly, it must remember what it read $$n$$ characters ago, to decide whether to accept or reject if the string just ends right now
• It also must remember what was $$n-1$$ characters ago, just in case the string ends 1 character later
• And it must remember what was $$n-2$$ characters ago, just in case the string ends 2 characters later
• And it must remember what was $$n-3$$ ...

As you can see, by that kind of logic it must be absolutely sure about each of $$2^{n+1}$$ bits. To formalize this deduction, try to prove the following:

LEMMA: If $$a$$ and $$b$$ are two different strings of length $$n+1$$, then they should lead the DFA in question to two different states.

The method for proving this lemma is to append things to $$a$$ and $$b$$, such that, for example, string $$ac$$ must be accepted and string $$bc$$ must be rejected. If the automaton knows the difference between $$ac$$ and $$bc$$, then it must have known the difference between $$a$$ and $$b$$. Look up "right invariant equivalence" if you don't already know that concept.

Once you prove the lemma, the rest is obvious. There are $$2^{n+1}$$ different strings which all lead to different states. Therefore, there are at least $$2^{n+1}$$ different states.