Problem Detail: 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$?
Asked By : Kapes
Answered By : bellpeace
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18278
