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.
$\begingroup$
$\endgroup$
-
1$\begingroup$ What do you mean by "equivalent NFA"? $\endgroup$ – Yuval Filmus Feb 24 '17 at 15:52
-
$\begingroup$ If the NFA is converted to DFA, the resulting states in the DFA should be less than the NFA. $\endgroup$ – user7518348 Feb 24 '17 at 16:04
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ Thanks, I get it now. Actually I meant NFA with min states $\endgroup$ – user7518348 Feb 24 '17 at 16:11
