# Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?

The wikipedia page Powerset construction says that the DFA equivalent to this $(n + 1)$-state NFA (with $n=4$ here) "requires $2^n$ states, one for each $n$-character suffix of the input".

I understand that the author wants to say that the smallest DFA equivalent to this NFA needs at least $2^n$ states.

But I can find a very much smaller DFA equivalent to this NFA just below:

Is Wikipedia wrong? Or am I? (which is much more likely)

The NFA accepts strings where the fourth letter from the end is 1. Your DFA doesn't accept 11000.

A DFA doesn't know how much input is left, so the property "the fourth character from the end" is difficult. You need to remember the last four characters to know whether it was a 1 or a 0 once you reach the end of the string. To do so you need a state for each possible combination of the last four characters, so 2^4 states. If you look hard at the DFA the Wikipedia gives you should be able to figure out which of the states stores which combination of characters.

You can prove the lower bound on the number of states using Myhill-Nerode theory.

Suppose that we are given a language $L$, in this case the language over $\{0,1\}$ of words in which the $n$th last symbol is $1$. We say that two words $x,y$ (over the same alphabet) are equivalent if for all words $z$, $xz \in L$ iff $yz \in L$. It is easy to check that if two words $x,y$ are not equivalent, then $\delta(q_0,x) \neq \delta(q_0,y)$ for every DFA for $L$. In particular, if we can find $N$ pairwise inequivalent words, then it follows that every DFA for $L$ must contain at least $N$ states.

For our language $L$, I claim that the set of $2^n$ words of length exactly $n$ are pairwise inequivalent. Indeed, suppose that $x \neq y$ are two words of length $n$. Then $x_i \neq y_i$ for some $i$, say $x_i = 0$ and $y_i = 1$ (without loss of generality). Then $x0^{i-1} \notin L$ whereas $y0^{i-1} \in L$, since in both cases the $n$th symbol from the end is $x_i$ or $y_i$. Thus every DFA for $L$ must contain at least $2^n$ states.

• Thanks for your contribution. Myhill-Nerode has always be unclear for me and your explanation is very easy to understand.
– Luz
Commented Jan 16, 2017 at 13:29