Context-free grammars: GATE CS question with 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 $ϵ$). 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 ϵ$. So $L(G_2)=a^{\ast }{b}^{\ast }$, 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.