0
$\begingroup$

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

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.