Consider the following languages: L1 = {an bm cn+m : m, n ≥ 1} L2 = {an bn c2n : n ≥ 1} Which one of the following is TRUE?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2016 Set 2 · Q43
Time
Select one answerSingle correct
Solution
Official answer: B) L1 is context-free while L2 is not context-free.
Context-Free Grammars and PDAsLet us analyze both languages:
Language :
The number of 's equals the sum of the number of 's and 's ().
A Pushdown Automaton (PDA) can push all incoming 's and 's onto the stack and pop one symbol from the stack for each matching .
A Context-Free Grammar (CFG) generating can be written as:
Therefore, is a context-free language.
Language :
A single stack PDA cannot simultaneously verify that the number of 's equals the number of 's and that the number of 's equals .
Using the Pumping Lemma for CFLs, one can show that pumping will disrupt either the count equality of 's and 's or the proportion of 's.
Therefore, is not context-free.
Thus, is context-free while is not context-free.
Therefore, the correct option is (B).
Try the question first, then check your work.
Examiner trap
Check how many independent comparisons are required. A single stack can match the sum of two counts against a third, but cannot enforce equality across three distinct parts simultaneously.
This Context-Free Grammars and PDAs previous year question is Q43 of the GATE CSE 2016 Set 2 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 GATE CSE 2016 Set 2 has 2.
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.