Number of States in FA

Question

Can number of states in minimized DFA be less than number of states than minimal NFA from which it is converted?

Comments

yes nfa can have as many states as you want

---

can you give an example?

---

No, we cannot  have minimized DFA having no of states less than corresponding nfa.

For a nfa with n states , the corresponding dfa can have n( in case of minimzed dfa) to 2^n states.

Ex. Consider a minimized DFA with a dead state.  Now if we have to make a nfa for the same language , you can make it less no of states by avoiding the need of dead state.( Note here I m taking a genral case. we can further reduce nfa size depending on the language)

Reason-In nfa  we dont have to define transition for every input

Answer 1

yes it may be NFA have more then number of states from minimized DFA.

Comments

NFA isn't minimal in your diagram. Is it possible for minimal NFA to have less states than Minimal DFA. Else you can add many arbitrary states like you have done here to show that its correct.

---

@abhishekmehta4u the DFA which u hav created because the same language can be acceped in less no of states in normal NFA  but if question is asking about NFA

IF we take epsilon NFA  because in Epsilon nfa also we can can give any number of epsilon moves Because that is the only case where the above condition is getting satisfied........ plzzzz correct me if I'm wrong somewhere........