GATE 2022 CS – Question 12

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice

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

start state q0; on a it goes to an accepting state with a b self-loop and a b transition back to q0; on b it goes to another accepting state with an a self-loop and an a transition back to q0.

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $(ba^*a+ab^*b)^*(ab^*+ba^*)$

Explanation

Each return loop to the start is $ab^*b$ or $ba^*a$, repeated any number of times. The string then ends in either accepting state, via $ab^*$ or $ba^*$. This gives $(ba^*a+ab^*b)^*(ab^*+ba^*)$.