Identify the language generated by the following grammar, where S is the start variable. S &→ XY X &→ aX a Y &→ aYb
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2017 Set 2 · Q16
Time
Select one answerSingle correct
Solution
Official answer: C) {am bn m > n, n ≥ 0}
Context-Free Grammars and PDAsTo find the language generated by the grammar:
Variable has productions , which generates the regular language :
Variable has productions , which generates equal numbers of 's and 's:
The start variable derives :
Let . Since , we have , and .
Therefore, the language generated is:
Hence, (C) is the correct option.
Try the question first, then check your work.
Examiner trap
Analyze the languages generated by variables and separately. generates at least one ( with ), and generates equal numbers of 's and 's ( with ).
This Context-Free Grammars and PDAs previous year question is Q16 of the GATE CSE 2017 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 1-mark MCQs like this one, and it is the only one in GATE CSE 2017 Set 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.