GATE CS 2022 Q.12: Regular Expressions, Finite Automata and Regular Languages

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

$ab^*bab^* + ba^*aba^*$

$(ab^*b)^*ab^* + (ba^*a)^*ba^*$

$(ab^*b + ba^*a)^*(a^* + b^*)$

$(ba^*a + ab^*b)^*(ab^* + ba^*)$

Official answer and solution

Solution

Decompose paths in the finite automaton into loops from the initial state $q_0$ and transitions to accepting states.

The automaton has start state $q_0$ and two accepting states $q_1$ and $q_2$ .

From state $q_0$ :

Moving to $q_1$ on 'a', looping on 'b' ( $b^*$ ), and returning to $q_0$ on 'b' corresponds to the sub-expression $a b^* b$ .
Moving to $q_2$ on 'b', looping on 'a' ( $a^*$ ), and returning to $q_0$ on 'a' corresponds to the sub-expression $b a^* a$ .

Any number of round trips that start and end at $q_0$ can be represented by $(ba^*a + ab^*b)^*$ .

From $q_0$ , the path can terminate in an accepting state:

Reaching and accepting in $q_1$ via 'a' followed by zero or more 'b's: $a b^*$ .
Reaching and accepting in $q_2$ via 'b' followed by zero or more 'a's: $b a^*$ .

Combining the cycles at $q_0$ with the terminal paths to the accepting states gives:

(ba^*a + ab^*b)^*(ab^* + ba^*)

This matches Option (D).

Final answer

Option (D)

Common trap

Forgetting that loops at $q_0$ can alternate arbitrarily between the $q_1$ branch and the $q_2$ branch.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.