Size comparison of NFA and minimal DFA Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? Due to the conversion of an NFA to DFA (which produces $2^Q$ states) it seems to me that a NFA can indeed have less states than a minimal DFA, but I'm not quite sure of this. Thanks in advance.
For every $n$ there is a language over $\{a,b\}$ which is accepted by an NFA having $n$ states, but its minimal DFA has $2^n$ states.

Unfortunately I don't remember the reference, but here is how to get almost this result. Let $L_n$ be the language of all words over $\{a_1,\ldots,a_n\}$ that don't contain all letters. Then $L_n$ can be accepted by an NFA with multiple initial states having $n$ states (or with a normal NFA with $n+1$ states), but its minimal DFA has $2^n$ states. Take it as an exercise to prove these statements (for the latter one, use Myhill-Nerode theory).