Consider the deterministic finite-state automaton (DFA) below. The alphabet is…
2023
Consider the deterministic finite-state automaton (DFA) below. The alphabet is {a,b}. The state with a small incoming arrow is the initial state, while the double circle state denotes a final state.
Which of the following regular expressions defines the language accepted by the DFA?
- A.
ab*
- B.
a*b*
- C.
(ab)*
- D.
a*b
Attempted by 75 students.
Show answer & explanation
Correct answer: A
To determine the regular expression, we trace the valid paths from the start state to the final accepting state.
First, observe that reading 'b' from the start state leads immediately to a trap state (the bottom node with self-loops on 'a' and 'b'), which is not a final state. Therefore, any valid string must start with 'a'.
Reading 'a' from the start state takes us to the final accepting state (the top-right node with a double circle). From this state, there is a loop on 'b', meaning we can accept any number of 'b's (including zero) after the initial 'a'. However, reading another 'a' leads to the trap state.
Combining these observations, the language consists of strings starting with 'a' followed by zero or more 'b's. This is represented by the regular expression ab*.