2
$\begingroup$

If an NFA with $n$ states is converted to an equivalent minimized DFA then what will be the maximum number of states in the DFA? Will it be $2^n$ or $2n$?

$\endgroup$
2
  • 1
    $\begingroup$ Try the canonical NFA for the language $L=\{ w\in \{a,b\}^* | \text{ $n$th character from behind is $a$}\}$. Check the number classes of the Myhill-Nerode relation for $L$, which gives you the number of states of the minimal DFA. $\endgroup$
    – A.Schulz
    Nov 23 '13 at 16:42
  • 3
    $\begingroup$ See this question $\endgroup$
    – J.-E. Pin
    Nov 23 '13 at 18:06
3
$\begingroup$

The maximum number of states is $2^n$. Conversion from NFA to DFA is done by subset construction and the number of states of the resulting DFA is in the worst case $2^n$. Minimization of the resulting DFA in the worst case might not reduce the number of states.

An example of this is automaton that accepts strings over $\Sigma = \{0, 1\}$ which have $1$ as the $n$th symbol from the end. Of course, $n$ is a concrete number. A NFA has states $q_0...q_n$ and the following transition function:

$$(q_0, 0) \rightarrow \{q_0\} \;\;\;\; (q_0, 1) \rightarrow \{q_0, q_1 \}$$ $$(q_i, 0) \rightarrow \{q_{i+1}\} \;\;\;\; (q_i, 1) \rightarrow \{q_{i+1}\} \;\;\; 1 \leq i \leq n-1$$

Intuitively, the corresponding DFA needs to remember last $n$ symbols since it does not know has it seen the end, which means there are $2^{n}$ states. For more details, I suggest looking into this book. It has a more detailed proof and generally covers these topics in thorough.

$\endgroup$

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