GateAI
Regular Expressions and Finite Automata

GATE CSE 2022 · Q12

MCQ1 markEasy

Time

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

GATE CSE 2022 Q12 diagram

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: D) (ba*a + ab*b)*(ab* + ba*)

Regular Expressions and Finite Automata

Let the start state be q0q_0, the top final state be q1q_1, and the bottom final state be q2q_2.

  1. From q0q_0, transitioning to q1q_1 requires symbol aa. While at q1q_1, reading any number of bb's keeps the automaton in q1q_1 (represented by b∗b^*). A subsequent bb takes it back to q0q_0. Thus, a round trip from q0q_0 to q1q_1 and back to q0q_0 is given by ab∗ba b^* b.

  2. From q0q_0, transitioning to q2q_2 requires symbol bb. While at q2q_2, reading any number of aa's keeps the automaton in q2q_2 (represented by a∗a^*). A subsequent aa takes it back to q0q_0. Thus, a round trip from q0q_0 to q2q_2 and back to q0q_0 is given by ba∗ab a^* a.

  3. Any string that returns to q0q_0 zero or more times is generated by the regular expression:

    (ba∗a+ab∗b)∗(ba^*a + ab^*b)^*
  4. To be accepted, the path must finally end in either:

    • State q1q_1, which contributes an additional ab∗a b^*

    • State q2q_2, which contributes an additional ba∗b a^*

Combining these, the complete regular expression is:

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

This matches option D.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Regular Expressions and Finite Automata previous year question is Q12 of the GATE CSE 2022 paper. Find more GATE CSE PYQs on Regular Expressions and Finite Automata in Theory of Computation, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Regular Expressions and Finite Automata PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Regular Expressions and Finite Automata in GATE CSE

Regular Expressions and Finite Automata has 41 GATE CSE PYQs across 24 papers from 2011 to 2026. 14 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2022.

How GATE tests Regular Expressions and Finite Automata

More from GATE CSE 2022

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2022 · Q12 · MCQ

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

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.