# DFA with less states than NFA

Is it possible for a DFA to have less states than its equivalent NFA? Number of transitions does not matter. If possible also give an example.

• What do you mean by "equivalent NFA"? – Yuval Filmus Feb 24 '17 at 15:52
• If the NFA is converted to DFA, the resulting states in the DFA should be less than the NFA. – user7518348 Feb 24 '17 at 16:04

Theoretically yes, that NFA could have 9001 unreachable stats that are completely useless.

If you expect that NFA to be connected (common sense) then if you allow epsilon-moves you can have a huge useless cykle.

If you rephrase your question to:

Lets consider any Language and its 'smallest' (min number of states) NFA with $\epsilon$-moves and its 'samllest' DFA then the answer is no and the reason is simple.

any DFA is also NFA (names does not suggest that though). therefore if we take a 'smallest' NFA and then manage find equivalent DFA that is 'smaller' that would contradict previous NFA being smallest.

No. There are infinitely many NFA that are equivalent to any given DFA – it does not make sense to speak of "a DFA and its equivalent NFA". Moreover, every DFA is a very predictable NFA.

• Thanks, I get it now. Actually I meant NFA with min states – user7518348 Feb 24 '17 at 16:11