Which of the following languages are context-free? L1 = {am bn an bm m, n ≥ 1} L2 = {am bn am bn m, n ≥ 1} L3 = {am bn m = 2n + 1}
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2015 Set 3 · Q32
Time
Select one answerSingle correct
Solution
Official answer: B) L1 and L3 only
Context-Free Grammars and PDAsLanguage : The dependencies in are nested in a LIFO manner (the inner can be matched first, and the outer is matched afterward). A pushdown automaton (PDA) can push all initial 's onto the stack, then push all 's, pop a for each subsequent to match , and finally pop an for each trailing to match . Because a single stack suffices, is context-free.
Language : The dependencies in are cross-serial (the first block of 's matches the second block of 's, and the first block of 's matches the second block of 's). A single stack cannot maintain and verify both counts simultaneously. By the Pumping Lemma for Context-Free Languages, is not context-free.
Language : . A PDA can easily match one for every two 's popped from the stack (ignoring the single extra leading ). Thus, is context-free (generated by , ).
Therefore, only and are context-free, which matches option (B).
Try the question first, then check your work.
Examiner trap
Analyze the dependency structure of each language: nested dependencies and single linear constraints can be parsed using a single stack, whereas cross-serial comparisons cannot.
This Context-Free Grammars and PDAs previous year question is Q32 of the GATE CSE 2015 Set 3 paper. Find more GATE CSE PYQs on Context-Free Grammars and PDAs 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 Context-Free Grammars and PDAs 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.
Context-Free Grammars and PDAs has 26 GATE CSE PYQs across 17 papers from 2011 to 2026. 9 of them are 2-mark MCQs like this one, and it is the only one in GATE CSE 2015 Set 3.
How GATE tests Context-Free Grammars and PDAsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.