0 votes 0 votes 1. For a $N$ state DFA its equivalent NFA would contain how many numbers of states:- a) In worst case? b) In best case? 2. For a $N$ state NFA its equivalent DFA would contain how many numbers of states:- a) In worst case? b) In best case? Theory of Computation theory-of-computation + – Naveen Kumar 3 asked Nov 3, 2018 Naveen Kumar 3 696 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Naveen Kumar 3 commented Nov 3, 2018 reply Follow Share for 2nd part https://gateoverflow.in/34006/can-we-find-out-minimum-numbers-of-states-in-dfa-nfa-has-states?show=34007#a34007 answered. 0 votes 0 votes Vikas Verma commented Nov 3, 2018 reply Follow Share @Naveen, A DFA is also an NFA, so no need to add additional states hence it remains to be N 0 votes 0 votes Naveen Kumar 3 commented Nov 3, 2018 reply Follow Share 1st part I'm still confused. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 1. Every DFA is a NFA. Worst Case : N Best Case : N 2.If NFA have N states, then DFA have Worst Case : 2^N Best Case : 1 Dharmendra Verma answered Nov 4, 2018 • edited Nov 4, 2018 by Dharmendra Verma Dharmendra Verma comment Share Follow See all 2 Comments See all 2 2 Comments reply Naveen Kumar 3 commented Nov 4, 2018 reply Follow Share @Dharmendra Verma for 2nd part pls check https://gateoverflow.in/34006/can-we-find-out-minimum-numbers-of-states-in-dfa-nfa-has-states?show=34007#a34007 and https://cs.stackexchange.com/questions/18278/maximum-number-of-states-in-minimized-dfa-from-nfa-with-n-states 0 votes 0 votes Dharmendra Verma commented Nov 4, 2018 reply Follow Share yes you are right by mistake i wrote it. 0 votes 0 votes Please log in or register to add a comment.