Consider the following Finite State Automaton. The language accepted by this…
2007
Consider the following Finite State Automaton. The language accepted by this automaton is given by the regular expression
- A.
A
- B.
B
- C.
C
- D.
D
Attempted by 154 students.
Show answer & explanation
Correct answer: C
Key idea: the automaton accepts exactly those strings that contain at least one 'a', with any number of leading 'b's allowed and any continuation after the first 'a'.
Reasoning steps:
From the start state, reading 'b' keeps the automaton in the start state, so any number (including zero) of leading 'b's is allowed (prefix b*).
The first time an 'a' is read the automaton moves to an accepting state, so a string must contain at least one 'a' to be accepted.
After reaching an accepting state, further symbols (either 'a' or 'b') keep the machine within accepting states (there are transitions on both symbols that lead to accepting states), so any continuation is allowed.
Conclusion:
The language is described by the regular expression b* a (a+b)*.
A video solution is available for this question — log in and enroll to watch it.