The GATE Grind

GATE 2025 CS (CS1) – Question 19

Theory of Computation · Context-Free Grammars and Pushdown Automata · 1 mark · Multiple choice

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 \rightarrow aaB \mid Abb$
$A \rightarrow a \mid aA$
$B \rightarrow b \mid bB$

Which ONE of the languages $L(G)$ is accepted by $G$?

  1. $L(G) = \{a^2b^n \mid n \ge 1\} \cup \{a^nb^2 \mid n \ge 1\}$
  2. $L(G) = \{a^nb^{2n} \mid n \ge 1\} \cup \{a^{2n}b^n \mid n \ge 1\}$
  3. $L(G) = \{a^nb^n \mid n \ge 1\}$
  4. $L(G) = \{a^{2n}b^{2n} \mid n \ge 1\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $L(G) = \{a^2b^n \mid n \ge 1\} \cup \{a^nb^2 \mid n \ge 1\}$

Explanation

S→aaB gives a^2 b^n (n≥1), since B generates b^+. S→Abb gives a^n b^2 (n≥1), since A generates a^+. The language is the union of the two.