GATE CS 2026 Set 2 Q19 — Parsing (LL, LR)

A grammar is ambiguous if there exists at least one string in its language that has more than one leftmost derivation (or equivalently, more than one distinct parse tree).

Let's analyze each option:

• Option A: $S \rightarrow a S b \mid \epsilon$
  This grammar generates the language $L = \{a^n b^n \mid n \ge 0\}$. For any string $a^n b^n$, there is exactly one unique derivation sequence (applying $S \rightarrow aSb$ exactly $n$ times followed by $S \rightarrow \epsilon$). Since every string in the language has a unique parse tree, this grammar is unambiguous.
• Option B: $E \rightarrow E+E \mid E * E \mid id$
  This is the classic expression grammar. For the string $id + id * id$, we can construct two distinct parse trees representing different operator precedences:
  • One where $+$ is evaluated first: $(E + E) * E$
  • One where $*$ is evaluated first: $E + (E * E)$
  Since there is more than one parse tree for the same string, this grammar is ambiguous.
• Option C: $S \rightarrow a S \mid S a \mid \epsilon$
  This grammar generates the language $L = \{a^n \mid n \ge 0\}$. Consider the string $w = a$. We can derive it in two distinct ways:
  • Derivation 1: $S \Rightarrow aS \Rightarrow a\epsilon = a$
  • Derivation 2: $S \Rightarrow Sa \Rightarrow \epsilon a = a$
  Since the string $a$ has two distinct leftmost derivations (and thus two distinct parse trees), this grammar is ambiguous.
• Option D: $S \rightarrow a S \mid \epsilon$
  This grammar generates $L = \{a^n \mid n \ge 0\}$. For any string $a^n$, we must apply $S \rightarrow aS$ exactly $n$ times and then terminate with $S \rightarrow \epsilon$. There is no other way to derive any string, so this grammar is unambiguous.

Therefore, the ambiguous grammars are B and C.