Maximum number of states in minimized DFA from NFA with $n$ states

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