1 votes 1 votes The minimal DFA that accepts all strings of a's and b's, and ends with 'aa' has _____ number of states. Theory of Computation tbb-toc-1 numerical-answers + – Bikram asked Nov 26, 2016 edited Aug 20, 2019 by Counsellor Bikram 464 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Neelesh Pandey commented Dec 26, 2016 reply Follow Share But this dfa will accept other string also like abaab,abaaab etc. 0 votes 0 votes vinay chauhan commented Oct 1, 2018 reply Follow Share Isn't the question ambiguous? It says "The minimal DFA that accepts all strings of a's and b's and ending with 'aa' " that means it includes both, in that case it will need only one state because (a+b)* is a superset of strings ending with 'aa', I think the question should be "The minimal DFA that accepts all strings of a's and b's which are ending with 'aa' " in this case 3 is the correct answer, please clarify on the conventions 0 votes 0 votes Ravi kumar singh commented Dec 27, 2018 reply Follow Share Its not accepting abaab,abaaab check again. 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes Ans- 3 states. vijaycs answered Dec 26, 2016 selected Oct 27, 2017 by Arjun vijaycs comment Share Follow See all 3 Comments See all 3 3 Comments reply A_i_$_h commented Oct 27, 2017 reply Follow Share I drew an NFA as A on a -> A,B......A on b ->A B on a -> c now this NFA has 3 states on converting to DFA = > 2n = 23 =8 states where did i go wrong 0 votes 0 votes Arjun commented Oct 27, 2017 reply Follow Share When an NFA with $n$ states is converted to a DFA, it can get up to $2^n$ states -- $2^n$ states are not a requirement but an upper limit. 0 votes 0 votes A_i_$_h commented Oct 27, 2017 reply Follow Share @arjun sir But my NFA is right for the above requirement na? and when i converted it to DFA by the process of coverting NFA to DFa i got 8 states 0 votes 0 votes Please log in or register to add a comment.