does a DFA converted from NFA always contain 2^Q states?

Problem Detail: 

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states? or if some sub-sets are unreachable then they are not included in it?

Asked By : Tom

Answered By : G. Bach

As per suggestion, I'm posting this as an answer.

Any DFA already is an NFA. Determinizing it will not change the number of states it has, so there are NFA that do not have fewer states than the equivalent minimal DFA.

Maybe also a non-trivial example:

Take the NFA with states $\{q_o, q_1\}$, alphabet $\Sigma = \{a\}$, initial state $q_0$, transitions $\delta(q_0, a) = \{q_0,q_1\}$ and final state $q_1$. It generates the same language as the DFA with the same set of states and alphabet, but transitions $\delta(q_0,a)=q_1$ and $\delta(q_1,a)=q_1$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18577