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.2k 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 Show 3 previous comments 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.