Discussion
Which one of the following regular expressions correctly represents the language of the finite automaton given below?
(Figure: the automaton has a start state and two accepting states. From the start state, a goes to the first accepting state, which loops on b and returns to the start state on b; b goes to the second accepting state, which loops on a and returns to the start state on a.)
Answer: D
The automaton's language is \((ba^{*}a + ab^{*}b)^{*}(ab^{*} + ba^{*})\).
Every run starts at the start state. A round trip through the upper state reads \(a\), any number of \(b\)s on its loop, then the \(b\) back: \(ab^{*}b\). A round trip through the lower state reads \(ba^{*}a\). A run may take any number of these round trips in any order, then must finish in an accepting state, either by \(a\) followed by \(b\)s (\(ab^{*}\)) or by \(b\) followed by \(a\)s (\(ba^{*}\)).
Option A allows exactly one round trip, so it misses even the single letter a. Option B never mixes the two kinds of round trip, so it misses abbaa, which the automaton accepts as the round trip ab followed by the finish baa. Option C accepts the empty string and strings such as aa, but the start state is not accepting and has no way to read aa.
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