in Theory of Computation edited by
224 views
1 vote
1 vote
The minimal DFA that accepts all strings of a's and b's, and ends with 'aa' has _____ number of states.
in Theory of Computation edited by
by
224 views

4 Comments

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

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
0
Its not accepting abaab,abaaab check again.
0
0

1 Answer

3 votes
3 votes
Best answer

Ans- 3 states.

selected by

3 Comments

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
0
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
0
@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
0
Answer:

Related questions