Exam-style question
Try this first
An FSM has a start state q0 and an accepting state q1. The only transition from q0 is labelled a and leads to q1. From q1, there are transitions labelled a and b that both lead back to q1. Write a regular expression for the language recognised by this FSM and explain how the expression corresponds to the FSM.
Model answer
What a good answer should say
- The regular expression is a(a|b)*.
- The initial a represents the transition from q0 to q1.
- Once q1 has been reached, the FSM can read any number of a or b characters because both transitions loop back to q1.
- The * represents zero or more repetitions, so the string may consist of the initial a alone or may have further a and b characters.
Explanation
Why this works
The FSM requires the first character to be a and then permits any sequence of a and b characters. The regular expression expresses exactly those two stages: a followed by (a|b)*.
Common mistake
No common mistake is linked to this question yet.