GATE CS 2024 Set 2 Q12 — Regular Expressions and Finite Automata

The given DFA consists of two states: $q_0$ (the initial state) and $q_1$ (the only final state), with the following transitions:

• $\delta(q_0, 0) = q_0$ and $\delta(q_0, 1) = q_1$
• $\delta(q_1, 0) = q_1$ and $\delta(q_1, 1) = q_0$

To find the equivalent regular expression, we analyze the paths to reach and stay in the final state $q_1$:

1. Reaching $q_1$ initially: To reach $q_1$ for the first time from the start state $q_0$, the automaton must consume any number of $0$s followed by a single $1$. This is represented by: $$0^* 1$$
2. Looping at $q_1$: Once at $q_1$, we can return to $q_1$ in two ways:
   • Directly via the self-loop on $0$.
   • By transitioning to $q_0$ on $1$, looping on $0$ any number of times ($0^*$), and returning to $q_1$ on $1$. This path is $1 0^* 1$.
   Any combination of these loops can be repeated zero or more times, which is represented by: $$(0 + 1 0^* 1)^*$$

Combining these two parts, the complete regular expression for the language accepted by the DFA is:

Thus, the correct option is A.