0 votes 0 votes Can NFA has more states or equal states than DFA? Say NFA has n states and DFA has m states then - n>=m possible? Theory of Computation theory-of-computation finite-automata + – iarnav asked Aug 21, 2017 iarnav 689 views answer comment Share Follow See 1 comment See all 1 1 comment reply joshi_nitish commented Aug 21, 2017 reply Follow Share for a particular language, you can have as much state NFA as you wish, NFA has n states and DFA has m states then - n>=m possible...it is possible. 1 votes 1 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes Yes definitely n could be greater than m ( but not always(n>=m).it may) like if DFA has m states you may introduce a null production and get m+1 state NFA. An example G.K.T answered Aug 21, 2017 • selected Aug 21, 2017 by iarnav G.K.T comment Share Follow See all 3 Comments See all 3 3 Comments reply iarnav commented Aug 21, 2017 reply Follow Share I'm confused how with seeing epsilon in NFA you can go to next state? please explain, like people are saying NFA has as many states with epsilon transistions? HOW? Please draw an example! @G.K.T @joshi_nitish 0 votes 0 votes G.K.T commented Aug 21, 2017 reply Follow Share Here a simple example 0 votes 0 votes iarnav commented Aug 21, 2017 reply Follow Share @ G.K.T Well done, thanks MATE! 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes epsilon nfa can have any number of states. but minimised nfa can never have more states than dfa Surabhi Kadur answered Aug 22, 2017 Surabhi Kadur comment Share Follow See all 2 Comments See all 2 2 Comments reply iarnav commented Aug 22, 2017 reply Follow Share Minimized NFA?! 0 votes 0 votes Surabhi Kadur commented Aug 22, 2017 reply Follow Share I meant nfa with no epsilon moves and least possible number of states for a given language . 1 votes 1 votes Please log in or register to add a comment.