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$?
$\begingroup$
$\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.SchulzNov 23, 2013 at 16:42
-
3$\begingroup$ See this question $\endgroup$– J.-E. PinNov 23, 2013 at 18:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
