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

Approach ?

edited | 88 views
0
is the ans 3?
0
Yes.
+1

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.

0
your NFA is not accepting ababa and so many strings.
0
corrected it
0

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

0

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

0

Ok.. Thanks @Shobhit

+1

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

+1 vote
1