Topic: Theory of Computation
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. (Diagram shows initial state transitioning to final state on 'a'. Final state loops on 'b', and transitions to a trap state on 'a'. Initial state transitions to trap state on 'b'. Trap state loops on 'a,b'). Which of the following regular expressions defines the language accepted by the DFA?
- A. $ab^{*}$
- B. $a^{*}b^{*}$
- C. $(ab)^{*}$
- D. $a^{*}b$
Answer: A. $ab^{*}$
Explanation: Based on the transitions in the DFA: The string must start with an 'a' to reach the final state. From the final state, any number of 'b's keeps it in the final state. Any 'b' at the start or an 'a' after the initial 'a' sends the automaton to a trap/dead state. This corresponds to the regular expression $ab^{*}$.