224 views
The minimal DFA that accepts all strings of a's and b's, and ends with 'aa' has _____ number of states.

But this dfa will accept other string also like abaab,abaaab etc.

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

Its not accepting abaab,abaaab check again.

Ans- 3 states.

by

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

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.
@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

1
577 views