Size of minimal DFA

Question

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$.

Answer 1

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<n$).

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$.