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

To solve this problem, we need to determine the regular expression that describes the language accepted by the given DFA.

Firstly, let's analyze the DFA transitions based on the diagram:

• The DFA has the start state \(s\) and a final state \(p\).
• From state \(s\), on input '1', it transitions to state \(p\).
• State \(p\) has a loop on '0' (stays in \(p\)) and transitions to state \(q\) on '1'.
• From state \(q\), on '1', it transitions back to \(p\) and on '0', it transitions to state \(r\).
• State \(r\) has loops on both '0' and '1' and is a dead state (cannot reach \(p\) or another final state).

To construct the regular expression, consider the paths that lead to and stay within the accepting state:

1. To reach \(p\) from \(s\), the input must start with '1'.
2. Once in state \(p\), it can either:
   • Stay in \(p\) by taking '0' zero or more times.
   • Transition to \(q\) and back to \(p\) using the sequence '11'.
3. This results in the path being captured by the expression \(1(0 + 11)^*\).

Thus, the regular expression that correctly describes the language accepted by the DFA is:

1(0 + 11)^*

All other options do not match the transitions and states within the DFA correctly.