GateAI
Context-Free Grammars and PDAs

GATE CSE 2017 Set 2 · Q16

MCQ1 markEasy

Time

Identify the language generated by the following grammar, where SS is the start variable. S→XYX→aX∣aY→aYb∣ϵ \begin{aligned} S &\to XY X &\to aX \mid a Y &\to aYb \mid \epsilon \end{aligned}

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: C) {am bn m > n, n ≥ 0}

Context-Free Grammars and PDAs

To find the language generated by the grammar:

  1. Variable XX has productions X→aX∣aX \to aX \mid a, which generates the regular language a+a^+:

    L(X)={ak∣k≥1}L(X) = \{a^k \mid k \ge 1\}
  2. Variable YY has productions Y→aYb∣ϵY \to aYb \mid \epsilon, which generates equal numbers of aa's and bb's:

    L(Y)={anbn∣n≥0}L(Y) = \{a^n b^n \mid n \ge 0\}
  3. The start variable SS derives XYXY:

    L(S)=L(X)⋅L(Y)={akanbn∣k≥1,n≥0}={ak+nbn∣k≥1,n≥0}L(S) = L(X) \cdot L(Y) = \{a^k a^n b^n \mid k \ge 1, n \ge 0\} = \{a^{k+n} b^n \mid k \ge 1, n \ge 0\}

Let m=k+nm = k + n. Since k≥1k \ge 1, we have m=k+n≥1+n>nm = k + n \ge 1 + n > n, and n≥0n \ge 0.

Therefore, the language generated is:

{ambn∣m>n, n≥0}\{a^m b^n \mid m > n,\ n \ge 0\}

Hence, (C) is the correct option.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

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

Where do you stand for GATE?

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.

One GATE CSE PYQ every morning

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 in GATE CSE

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 PDAs

More from GATE CSE 2017 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2017 Set 2 · Q16 · MCQ

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

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.