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

By analyzing the paths from the start state $q_0$ in the given $\text{NFA}$, we can identify three distinct branches of accepted strings:

1. Only $0$s: The automaton can transition to a loop that accepts any number of $0$s, including the empty string $\epsilon$. This corresponds to the regular expression $0^*$.
2. Odd number of $0$s followed by an even number of $1$s: This path accepts strings of the form $0(00)^*(11)^*$.
3. Odd number of $1$s: This path accepts strings consisting of an odd number of $1$s, represented by $1(11)^*$.

Combining these three independent paths, the complete language accepted by the $\text{NFA}$ is represented by the union of their regular expressions:

By factoring out $(11)^*$ from the last two terms, we get:

This matches Option B.