# 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)

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.