GATE CS 2023 Q29 — Context-free Grammars and Push-down Automata

To find the language generated by the grammar $G$, we analyze the non-terminals step-by-step.

Step 1: Analyze the language generated by $X$
The production rules for $X$ are: $$X \rightarrow a X \mid X b \mid a \mid b$$ Any derivation from $X$ must terminate with either $a$ or $b$. We can prepend any number of $a$'s and append any number of $b$'s. Thus, $X$ generates all strings of the form $a^i b^j$ where $i + j \ge 1$ (i.e., at least one terminal is present, and all $a$'s precede all $b$'s). $$L(X) = a^* (a+b) b^*$$

Step 2: Analyze the language generated by $S$
The production rules for $S$ are: $$S \rightarrow a S b \mid X$$ This means $S$ wraps strings from $L(X)$ with an equal number of $a$'s on the left and $b$'s on the right: $$L(G) = \{ a^k w b^k \mid w \in L(X), k \ge 0 \}$$ Substituting $w = a^i b^j$ (where $i+j \ge 1$): $$a^k w b^k = a^k a^i b^j b^k = a^{k+i} b^{j+k}$$ Let $m = k+i$ and $n = j+k$. Since $i+j \ge 1$ and $k \ge 0$, we have $m+n \ge 1$. Conversely, for any $m, n \ge 0$ with $m+n \ge 1$, we can simply choose $k = 0$, which yields $i = m$ and $j = n$ (where $i+j \ge 1$). Thus, all such strings are generated: $$L(G) = \{ a^m b^n \mid m+n \ge 1 \} = a^* (a+b) b^*$$

Since this language is regular and matches option B, the correct statement is B.