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

Question

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}$?

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