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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.