Test by Bikram | Theory of Computation | Test 1 | Question: 2

Question

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

Comments

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.

Answer 1

Ans- 3 states.

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 = > 2ⁿ = 2³ =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