Testbook Test Series: Theory of Computation - Minimal State Automata

Question

$Que-$ The minimum number of states in the $NFA$ for the regular expression $(a + a(b + aa)*b)* a(b + aa)*a$ is ______.

Approach ?

Comments

is the ans 3?

---

Yes.

---

The DFA would like this.

Try making the DFA for $(a+(b+aa)^*b)^*$, we can easily see $q_3$ will be the final state.

---

your NFA is not accepting ababa and so many strings.

---

corrected it

---

@Shobhit Joshi, Thank you.
Is there any alternative approach to solve this question quickly?
Something making DFA consumes a lot of time if given RE is complicated. 
 

---

@Soumya29 I don't know if there is some method, I do it this way only.

---

Ok.. Thanks @Shobhit 

---

@Soumya29 I first made the NFA for the smallest string that the given regular expression was accepting and then completed it as to accept the other strings also.. So I guess for the minimum no of states of a particular NFA we should see the minimum no of states required to accept the string of minimum length and then proceed with the necessary modifications.

---

I don’t think this DFA is correct. For example, the string ‘aaababababa’ will be accepted by this NFA whereas the language should not.