GATE CS 2025 Set 1 Q9 — Context-free Grammars and Push-down Automata

To find the language $L(G)$ accepted by the context-free grammar $G$, we can analyze the production rules step-by-step.

Step 1: Analyze the variables $A$ and $B$

• The production rule for $A$ is:
  $$A \rightarrow a \mid aA$$
  This generates any sequence of one or more $a$'s. Thus, the language generated by $A$ is:
  $$L(A) = \{a^n \mid n \geq 1\}$$
• The production rule for $B$ is:
  $$B \rightarrow b \mid bB$$
  This generates any sequence of one or more $b$'s. Thus, the language generated by $B$ is:
  $$L(B) = \{b^n \mid n \geq 1\}$$

Step 2: Analyze the start variable $S$

The production rule for $S$ has two alternative branches: $S \rightarrow aaB$ and $S \rightarrow Abb$. We evaluate each branch separately:

1. First branch ($S \rightarrow aaB$):

   Substituting the language of $B$, we get:

   $$aa \cdot L(B) = \{a^2 b^n \mid n \geq 1\}$$
2. Second branch ($S \rightarrow Abb$):

   Substituting the language of $A$, we get:

   $$L(A) \cdot bb = \{a^n b^2 \mid n \geq 1\}$$

Step 3: Combine the branches

Since $S$ can derive either of the two branches, the language $L(G)$ is the union of the languages generated by both branches:

This matches Option A.