GATE CS 2023 Q4 — Regular Expressions and Finite Automata

To find the regular expression accepted by the DFA $\mathcal{A}$, let us analyze the state transitions from the diagram:

• Start State: $s$
• Final State: $p$
• Trap State: $r$ (any transition to $r$ cannot reach the final state $p$)

Let's trace the transitions step-by-step:

1. Initial step: To reach the final state $p$ from the start state $s$, the first symbol must be $1$ ($\delta(s, 1) = p$). If the first symbol is $0$, the DFA transitions to the trap state $r$. Thus, every accepted string must start with $1$.
2. Behavior at state $p$: Once we are at the final state $p$, we can loop back to $p$ in two ways:
   • By reading a $0$ directly: $\delta(p, 0) = p$.
   • By reading $11$: $\delta(p, 1) = q$ and then $\delta(q, 1) = p$.
   Any other transition from $q$ (such as reading a $0$) leads to the trap state $r$.

Thus, from state $p$, we can repeat any sequence of $0$ or $11$ any number of times and remain in the final state $p$. This loop behavior is represented by the regular expression $(0 + 11)^*$.

Combining the initial step and the loop behavior, the regular expression for the language accepted by the DFA is:

Therefore, the correct option is C.