1 votes 1 votes Can number of states in minimized DFA be less than number of states than minimal NFA from which it is converted? Theory of Computation theory-of-computation minimal-state-automata finite-automata number-of-states + – smsubham asked Apr 8, 2018 • edited Apr 9, 2018 by smsubham smsubham 2.7k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Mk Utkarsh commented Apr 8, 2018 reply Follow Share yes nfa can have as many states as you want 0 votes 0 votes smsubham commented Apr 8, 2018 reply Follow Share can you give an example? 0 votes 0 votes Satyajeet Singh commented Apr 9, 2018 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes yes it may be NFA have more then number of states from minimized DFA. abhishekmehta4u answered Apr 9, 2018 abhishekmehta4u comment Share Follow See all 2 Comments See all 2 2 Comments reply smsubham commented Apr 9, 2018 reply Follow Share 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. 0 votes 0 votes sanju77767 commented Apr 21, 2018 reply Follow Share @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........ 0 votes 0 votes Please log in or register to add a comment.