is the ans 3?

The Gateway to Computer Science Excellence

0 votes

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

Approach ?

Approach ?

+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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,834 questions

57,752 answers

199,483 comments

108,193 users