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
GATE CSE 2022 · Q12
Time

Select one answerSingle correct
Solution
Official answer: D) (ba*a + ab*b)*(ab* + ba*)
Regular Expressions and Finite AutomataLet the start state be , the top final state be , and the bottom final state be .
From , transitioning to requires symbol . While at , reading any number of 's keeps the automaton in (represented by ). A subsequent takes it back to . Thus, a round trip from to and back to is given by .
From , transitioning to requires symbol . While at , reading any number of 's keeps the automaton in (represented by ). A subsequent takes it back to . Thus, a round trip from to and back to is given by .
Any string that returns to zero or more times is generated by the regular expression:
To be accepted, the path must finally end in either:
State , which contributes an additional
State , which contributes an additional
Combining these, the complete regular expression is:
This matches option D.
Try the question first, then check your work.
Examiner trap
Identify the loops from the initial state back to itself, followed by paths that terminate in one of the two accepting states.
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
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.
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 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 AutomataIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.