GATE CS 2022 Q2 — Regular Expressions and Finite Automata

To find the regular expression for the given finite automaton, we analyze the paths starting from the initial state $q_0$ to the final states $q_1$ and $q_2$:

1. Loops returning to $q_0$: From the start state $q_0$, we can loop back to $q_0$ in two ways:
   • By going to $q_1$ via $a$, looping on $q_1$ with $b^*$, and returning to $q_0$ via $b$. This path is represented by $ab^*b$.
   • By going to $q_2$ via $b$, looping on $q_2$ with $a^*$, and returning to $q_0$ via $a$. This path is represented by $ba^*a$.
   Any number of these loops can be combined in any order, which is represented by:$$(ba^*a + ab^*b)^*$$
2. Reaching the final states: From $q_0$, the final transition to an accepting state must be:
   • To the final state $q_1$ via $a$ followed by any number of $b$'s: $ab^*$
   • To the final state $q_2$ via $b$ followed by any number of $a$'s: $ba^*$
   This gives the final part of the expression: $(ab^* + ba^*)$.

Combining these two parts, the complete regular expression is:

Thus, the correct option is D.