# 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}$$? Posted on Categories proxies