0
$\begingroup$

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.

|cite|improve this question
$\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
9
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks, I get it now. Actually I meant NFA with min states $\endgroup$ – user7518348 Feb 24 '17 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.