Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2014 Set 1 · Q16
Time

Select one answerSingle correct
Solution
Official answer: A) {q0, q1, q2}
Regular Expressions and Finite AutomataWe can trace the set of reachable states step-by-step starting from the initial state with the input string :
Initial state:
On first input symbol '0':
Set of states =
On second input symbol '0':
Set of states =
On third input symbol '1':
Set of states =
On fourth input symbol '1':
Thus, the set of reachable states is , which corresponds to option (A).
Try the question first, then check your work.
Examiner trap
Trace the transitions from the start state symbol by symbol for the string , taking the union of all reachable states at each step.
This Regular Expressions and Finite Automata previous year question is Q16 of the GATE CSE 2014 Set 1 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 2014 Set 1 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.