32 votes 32 votes State whether the following statements are TRUE or FALSE: A minimal DFA that is equivalent to an NDFA with $n$ nodes has always $2^{n}$ states. Theory of Computation gate1987 theory-of-computation finite-automata minimal-state-automata + – makhdoom ghaya asked Nov 9, 2016 • recategorized Apr 22, 2021 by Lakshman Bhaiya makhdoom ghaya 5.3k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply muthu kumar commented Oct 24, 2018 reply Follow Share Here, Nodes and States are same or not? 0 votes 0 votes Verma Ashish commented Oct 24, 2018 reply Follow Share Yes 1 votes 1 votes Kishor Bundhe commented Sep 12, 2020 reply Follow Share what is node here ? 0 votes 0 votes Please log in or register to add a comment.
Best answer 35 votes 35 votes No a minimal DFA that is equiavlent to an NDFA with $n$ nodes has always $2^n$ states. Correct statement is A minimal DFA that is equivalent to an NDFA with $n$ nodes has atmost $2^n$ states. Example : Prashant. answered Nov 9, 2016 • edited Feb 9, 2018 by kenzou Prashant. comment Share Follow See all 6 Comments See all 6 6 Comments reply Soumya29 commented Nov 24, 2018 i edited by Lakshman Bhaiya Apr 14, 2021 reply Follow Share For a given $NFA$ with $n$ states, it's equivalent minimal $\ DFA$ can have minimum $1$ state and maximum $2^n$ states. 12 votes 12 votes srestha commented Dec 12, 2018 reply Follow Share @Soumya29 is it correct For Decimal( Binary String ) = 0 mod n i) if $n = 2^{m}$ then No.of states in Minimal DFA = m + 1 https://gateoverflow.in/272643/cant-understand-the-intution-behind-the-shortcut minimal DFA could be $1$ isnot it? 0 votes 0 votes mrinmoyh commented Sep 13, 2019 reply Follow Share I have one doubt. for n states of NFA we'll get atmost 2^n states in DFA. This 2^n including the dead state of DFA or excluding the dead state. 0 votes 0 votes Neelam_$ingh_222 commented Sep 26, 2020 reply Follow Share 2^n , excluding the dead state –1 votes –1 votes jeeruajay commented Jan 21, 2021 reply Follow Share Is there any example that satisfies NDFA with n states → DFA with 2^n states ? 0 votes 0 votes Manu Shaurya commented Jun 25, 2021 reply Follow Share @mrinmoyh This includes the dead state.The subset would have ∅ state in the corresponding DFA which would become the Dead State. Watch this from 38:33 https://www.youtube.com/watch?v=EPgZlAn4EC0&list=PLTke5lHMAdSNmi57H0DOTzClHPK6UwSTN&index=2 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 votes false. it is just upperbound on number of states obtained after coverting NFA to DFA Anusha Motamarri answered Nov 9, 2016 Anusha Motamarri comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes False, the minimal DFA can have states in range of n<= states<=2^n.In worst case it have 2^n states and in best case it have n states. Tushar Garg answered Mar 15, 2018 Tushar Garg comment Share Follow See 1 comment See all 1 1 comment reply Soumya29 commented Nov 24, 2018 reply Follow Share In the best case, Minimal $DFA$ can have just $1$ state. 3 votes 3 votes Please log in or register to add a comment.