GATE CS 2026 Set 2 Q.29: Parsing and Syntax Analysis (LL and LR)

Which of the following grammars is/are ambiguous?

$S \rightarrow aSb \mid \epsilon$

$E \rightarrow E + E \mid E * E \mid id$

$S \rightarrow aS \mid Sa \mid \epsilon$

$S \rightarrow aS \mid \epsilon$

Official answer and solution

Solution

Check whether each grammar admits two distinct parse trees (or leftmost derivations) for some string.

(A) $S \rightarrow aSb \mid \epsilon$ generates $\{a^n b^n \mid n \ge 0\}$ uniquely; it is unambiguous.
(B) $E \rightarrow E + E \mid E * E \mid id$ is the classic ambiguous expression grammar (e.g., $id + id + id$ and $id + id * id$ each have two parse trees).
(C) $S \rightarrow aS \mid Sa \mid \epsilon$ is ambiguous because the string $a$ has two distinct leftmost derivations: $S \Rightarrow aS \Rightarrow a$ and $S \Rightarrow Sa \Rightarrow a$ .
(D) $S \rightarrow aS \mid \epsilon$ is a right-linear deterministic grammar generating $a^*$ unambiguously.

Thus (B) and (C) are ambiguous.

Final answer

Options (B), (C)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 29 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.