Let denote the transition function and denote the extended transition function of the -NFA whose transition table is given below: Then (q2, aba) is
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2017 Set 2 · Q39
Time

Select one answerSingle correct
Solution
Official answer: C) {q0, q1, q2}
Regular Expressions and Finite AutomataTo compute the extended transition function for the given -NFA, we process the string symbol-by-symbol using -closures:
Initial state closure:
(Since and ).
On reading input symbol 'a':
Taking -closure:
(Since ).
On reading input symbol 'b':
Taking -closure:
On reading input symbol 'a':
Taking -closure:
Thus, , which corresponds to option (C).
Try the question first, then check your work.
Examiner trap
Compute the -closure of first, then iteratively apply the transition on each input character (, then , then ) followed by computing the -closure of the resulting state set.
This Regular Expressions and Finite Automata previous year question is Q39 of the GATE CSE 2017 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. 10 of them are 2-mark MCQs like this one, and GATE CSE 2017 Set 2 has 2.
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.