The GATE Grind

GATE 2026 CS (CS2) – Question 29

Theory of Computation · Context-Free Grammars and Pushdown Automata · 1 mark · Multiple select

Which of the following grammars is/are ambiguous?

  1. $S \to aSb \mid \epsilon$
  2. $E \to E + E \mid E * E \mid id$
  3. $S \to aS \mid Sa \mid \epsilon$
  4. $S \to aS \mid \epsilon$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $E \to E + E \mid E * E \mid id$; (C) $S \to aS \mid Sa \mid \epsilon$

Explanation

Grammar (B) is the standard ambiguous expression grammar because strings like `id+id*id` have multiple parse trees. Grammar (C) is also ambiguous because the string `a` can be derived as $aS \Rightarrow a\epsilon$ or as $Sa \Rightarrow \epsilon a$. Grammar (A) generates balanced strings of the form $a^n b^n$ unambiguously, and grammar (D) generates $a^{*}$ unambiguously. Therefore, the ambiguous grammars are (B) and (C).