Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2024 Set 2 · Q22
Time

Select one answerSingle correct
Solution
Official answer: A) 0*1(0 + 10*1)*
Regular Expressions and Finite AutomataLet the initial state be and the final state be .
Transitions from the DFA:
At state (start state): a loop on , and a transition on to .
At state (accepting state): a loop on , and a transition on to .
Reaching the accepting state for the first time:
From , the automaton can loop on zero or more times, followed by a to transition to . This path is represented by the regular expression .
Looping back to :
Once in state , any sequence that leaves and returns to (without staying in ) can be repeated arbitrarily:
Reading loops directly on .
Reading goes to , followed by any number of s (), and another transitions back to , which corresponds to the sequence .
Thus, any sequence of loops at is given by .
Combining the paths:
Therefore, option A is the correct regular expression.
Try the question first, then check your work.
Examiner trap
Identify the path to reach the final state from the start state initially, and then determine all cycles that start and end at the final state.
This Regular Expressions and Finite Automata previous year question is Q22 of the GATE CSE 2024 Set 2 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 GATE CSE 2024 Set 2 has 3.
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.