GateAI
Context-Free Grammars and PDAs

GATE CSE 2025 Set 1 · Q19

MCQ1 markEasy

Time

Consider the following context-free grammar GG, where SS, AA, and BB are the variables (non-terminals), aa and bb are the terminal symbols, SS is the start variable, and the rules of GG are described as: S→aaB∣AbbS \rightarrow aaB \mid Abb A→a∣aAA \rightarrow a \mid aA B→b∣bBB \rightarrow b \mid bB Which ONE of the languages L(G)L(G) is accepted by GG?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: A) L(G) = {a2 bn n ≥ 1} ∪ {an b2 n ≥ 1}

Context-Free Grammars and PDAs

To determine the language generated by the context-free grammar GG:

  1. Language derived from variable AA: The productions for AA are:

    A→a∣aAA \rightarrow a \mid aA

    This generates one or more copies of terminal aa, i.e., L(A)=a+={an∣n≥1}L(A) = a^+ = \{a^n \mid n \ge 1\}.

  2. Language derived from variable BB: The productions for BB are:

    B→b∣bBB \rightarrow b \mid bB

    This generates one or more copies of terminal bb, i.e., L(B)=b+={bn∣n≥1}L(B) = b^+ = \{b^n \mid n \ge 1\}.

  3. Language derived from the start variable SS: The productions for SS are:

    S→aaB∣AbbS \rightarrow aaB \mid Abb
    • From S→aaBS \rightarrow aaB, the generated strings are aab+={a2bn∣n≥1}aa b^+ = \{a^2 b^n \mid n \ge 1\}.

    • From S→AbbS \rightarrow Abb, the generated strings are a+bb={anb2∣n≥1}a^+ bb = \{a^n b^2 \mid n \ge 1\}.

Combining both production paths:

L(G)={a2bn∣n≥1}∪{anb2∣n≥1}L(G) = \{a^2 b^n \mid n \ge 1\} \cup \{a^n b^2 \mid n \ge 1\}

Hence, (A) 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 Q19 of the GATE CSE 2025 Set 1 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 2025 Set 1.

How GATE tests Context-Free Grammars and PDAs

More from GATE CSE 2025 Set 1

Share this solution

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

GateAI solution cardGATE CSE 2025 Set 1 · Q19 · MCQ

Consider the following context-free grammar G, where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is the start variable, and the rules of G are described as: S → aaB Abb A → a aA B → b bB Which ONE of the languages L(G) is accepted by G?

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.