GATE 2026 CS2 Q.29: solution and answer

Official answer: B, CSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

1. A grammar is ambiguous if some string in its language has two distinct parse trees (equivalently, two distinct leftmost derivations).

2. (A) $S\to aSb\mid \epsilon$ generates $\{a^n{b}^n\mid n\ge 0\}$. In a string $a^n{b}^n$ with $n\ge 1$, the first symbol $a$ and the last symbol $b$ must come from the same use of $S\to aSb$, and the string is $\epsilon$ only when $n=0$. So every step is forced, and each string has exactly one parse tree. Unambiguous.

3. (B) $E\to E+E\mid E\ast E\mid id$ fixes no precedence or associativity. For $id+id\ast id$, the root can be $E\to E+E$ with $id\ast id$ as the right child. It can also be $E\to E\ast E$ with $id+id$ as the left child. These are two different parse trees for the same string. Ambiguous.

4. (C) $S\to aS\mid Sa\mid \epsilon$ generates $a^{\ast }$. For the string $a$, one derivation is $S\Rightarrow aS\Rightarrow a$ and another is $S\Rightarrow Sa\Rightarrow a$. In the first, the root has children $a,S$. In the second, the root has children $S,a$. These are two different parse trees. Ambiguous.

5. (D) $S\to aS\mid \epsilon$ is right-linear and generates $a^{\ast }$. The string $a^n$ can only be derived by applying $S\to aS$ exactly $n$ times and then $S\to \epsilon$. There is one parse tree per string. Unambiguous.

6. The ambiguous grammars are (B) and (C).