# Context-free grammars: GATE CS question with solution

From the GATE Daily set of 27 October 2026, question 6 of 10 (https://gatedaily.in/q/2026-10-27-two-grammars-language-and-regularity/). Difficulty: hard.

### Q.6 · Theory of Computation · Context-free grammars · MCQ, 2 marks (choose one option)

Consider the following two context-free grammars over the terminal alphabet $\{a, b\}$. In each grammar $S$ is the only non-terminal and the start symbol, and $\epsilon$ denotes the empty string.

$$G_1:\quad S \to aSbb \mid aS \mid \epsilon$$

$$G_2:\quad S \to aSb \mid aS \mid Sb \mid \epsilon$$

Which one of the following statements is CORRECT?

(A) $L(G_1) = \{a^m b^{2n} \mid m \ge n \ge 0\}$ and $L(G_2)$ is regular
(B) $L(G_1) = \{a^m b^{2n} \mid m \ge n \ge 0\}$ and $L(G_2)$ is context-free but not regular
(C) $L(G_1) = \{a^m b^{2n} \mid n \ge m \ge 0\}$ and $L(G_2)$ is regular
(D) $L(G_1) = \{a^m b^{2n} \mid n \ge m \ge 0\}$ and $L(G_2)$ is context-free but not regular

**Answer:** (A) $L(G_1) = \{a^m b^{2n} \mid m \ge n \ge 0\}$ and $L(G_2)$ is regular

**Solution.** **Method.** Find what every sentential form looks like, then read off the language.

*$G_1$.* Every rule puts its $a$'s to the left of $S$ and its $b$'s to the right, so a sentential form is $a^i\,S\,b^{j}$. The rule $S \to aSbb$ adds one $a$ and two $b$'s; $S \to aS$ adds one $a$ only. If $aSbb$ is used $n$ times and $aS$ is used $k$ times, the final string is $a^{n+k} b^{2n}$. So $m = n + k \ge n$, and every pair $m \ge n \ge 0$ is reachable (apply $aSbb$ $n$ times, then $aS$ $m-n$ times, then $\epsilon$). Hence $L(G_1) = \{a^m b^{2n} \mid m \ge n \ge 0\}$. Quick check: $abb \in L(G_1)$ but $abbbb \notin L(G_1)$.

*$G_2$.* Again all $a$'s stay left of $S$ and all $b$'s right of it, so every string is $a^i b^j$. Conversely any $a^i b^j$ is derived by applying $S \to aS$ $i$ times, $S \to Sb$ $j$ times, then $S \to \epsilon$. So $L(G_2) = a^*b^*$, which is regular. The rule $S \to aSb$ is redundant.

**The trap.** A rule of the form $S \to aSb$ suggests $\{a^n b^n\}$, but a grammar's language is not decided by one rule: here $aS$ and $Sb$ let the two counts vary independently, so the "matching" is lost. In $G_1$ the opposite care is needed: the extra rule $aS$ adds only $a$'s, so the $a$-count can exceed the number of $bb$ blocks but never fall below it.

**What was tested.** Deriving a grammar's language from the contribution of each production (a symbol-count argument in both directions), and not judging regularity from the shape of a single production.

**Remember:** To find L(G), write what each production contributes to the symbol counts, then show both directions: every derivation gives a string of the claimed form, and every string of that form has a derivation. One self-embedding rule does not make a language non-regular if other rules undo the count matching.

**Why each option:**
- (A) Each aSbb adds one a and two b's while aS adds only a's, so m >= n; G2 can add a's and b's independently, giving a*b*.
- (B) Sees the aSb wrapping rule in G2 and assumes it forces equal counts; aS and Sb break any count relation, so L(G2) = a*b*.
- (C) Reverses the inequality: extra a's come from aS, so a's can exceed the number of bb blocks, not fall short of it (abb, aabb are in, abbbb is not).
- (D) Combines both slips: reverses G1's inequality and assumes the aSb rule in G2 makes it non-regular.