# Size of minimal DFA

Assume a given NFA for a regular language with $$n$$ states. It is clear that determinizing it may result in an DFA with $$\Omega(2^n)$$ states. However, the minimization might decrease the number of states. Is there a counterexample which would show that the minimized version might aswell be of superpolynomial size? I.e. is the following true?

For every NFA with $$n$$ states, its (unique) minimal DFA has $$O(\operatorname{poly}(n))$$ states? If not, what is the counterexample? Here $$\operatorname{poly}(n)$$ is a polynomial in $$n$$.

If you consider the language over $$\Sigma = \{a, b\}$$ defined by the set of words that contain a $$a$$ in the $$n$$-th position before the end, or formally: $$L_n = \{uav\mid u,v\in \Sigma^*, |v| = n-1\}$$
Then $$L_n$$ is recognized by a NFA with $$n+1$$ states (quite simple to find), but the minimal DFA has $$2^n$$ states.
To prove that, suppose that there is a DFA $$A = (Q, \delta, q_0, F)$$ such that $$L(A) = L_n$$. Consider $$u,v\in \Sigma^n, u\neq v$$ two words of length $$n$$. Consider $$w$$ their longest common suffix. Without loss of generality, $$u = u'aw$$ and $$v = v'bw$$, with $$u', v'\in \Sigma^*$$, and $$w\in \Sigma^k$$ (with $$k).
Now, note that $$ua^{n-1-k}\in L$$ but $$va^{n-1-k}\notin L$$. That means that $$\delta(q_0, u)\neq \delta(q_0, v)$$ (otherwise $$\delta(q_0, va^{n-1-k}) = \delta(q_0, ua^{n-1-k})\in F$$)
What we proved is that two words in $$\Sigma^n$$ lead to two differents states when read from $$q_0$$. That means that $$|Q| \geq |\Sigma^n| = 2^n$$.