Discussion
Let \(M\) be the 5-state NFA with \(\epsilon\)-transitions shown in the diagram below.
Which one of the following regular expressions represents the language accepted by \(M\) ?
Answer: B
The language is \(0^{*} + (1 + 0(00)^{*})(11)^{*}\).
From the start, an \(\epsilon\)-move reaches either state 2 or state 4. Through state 2, pairs of 0s loop 2 to 3 to 2, so \((00)^{*}\) is accepted at 2; after an odd number of 0s, \(0(00)^{*}\), the machine is at 3 and can take the \(\epsilon\)-move to the accepting state 5, then read \((11)^{*}\) looping 5 to 4 to 5. Through state 4, one 1 reaches 5, then \((11)^{*}\). So
\[ L = (00)^{*} + 0(00)^{*}(11)^{*} + 1(11)^{*} \]
Since \((00)^{*} + 0(00)^{*} = 0^{*}\), this is exactly \(0^{*} + (1 + 0(00)^{*})(11)^{*}\).
\((00)^{*} + 1(11)^{*}\) misses strings such as 0 and 011. The third option includes 11, which M rejects. The last omits the empty string, which M accepts at state 2, and strings such as 00011.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development