Question

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet \(\{0, 1\}\), and has the set of states \(\{s, p, q, r\}\), with \(s\) being the start state and \(p\) being the only final state.

Which one of the following regular expressions correctly describes the language accepted by A?
 

• A. \( 1(0^*11)^* \)
• B. \( 0(0 + 1)^* \)
• C. \( 1(0 + 11)^* \)
• D. \( 1(110^*)^* \)

Hint:

When converting DFA to regular expression, first trace all possible transitions and determine the patterns that the DFA accepts. Then form the regular expression based on the observed transitions.

Answer 1

The Correct Option is C

The DFA has the following transitions:
- State \( s \) is the start state.
- On input \( 1 \), the DFA moves to state \( p \).
- From state \( p \), on input \( 1 \), it moves to state \( q \), and on input \( 0 \), it moves to state \( r \).
- From state \( q \), on input \( 0 \), it goes to state \( r \), and on input \( 1 \), it goes to state \( p \).
- From state \( r \), on input \( 0 \), it moves to state \( s \), and on input \( 1 \), it moves to state \( p \).
- The final state is \( p \).
To describe the language accepted by the DFA, we observe:
- Starting from state \( s \), the first \( 1 \) moves the automaton to state \( p \).
- After that, the DFA can accept zero or more repetitions of either \( 0 \) or \( 11 \), which leads to the regular expression \( 1(0 + 11)^* \).
Thus, the correct answer is option (C).