The GATE Grind

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?

Diagram for GATE 2022 CS question 12
  1. $ab^*bab^*+ba^*aba^*$
  2. $(ab^*b)^*ab^*+(ba^*a)^*ba^*$
  3. $(ab^*b+ba^*a)^*(a^*+b^*)$
  4. $(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^*)$.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →