Which of the following grammars are ambiguous?
2026
Which of the following grammars are ambiguous?
Answer: B. E→ 𝐸 + 𝐸 | 𝐸 ∗ 𝐸 | 𝑖𝑑; C. S→ 𝑎𝑆 | 𝑆𝑎 | epsilon — Analysis of Grammar AmbiguityA grammar is considered ambiguous if there exists at least one string that has more than one leftmost derivation or parse tree.…
- A.
𝑆 → 𝑎𝑆𝑏 | epsilon
- B.
E→ 𝐸 + 𝐸 | 𝐸 ∗ 𝐸 | 𝑖𝑑
- C.
S→ 𝑎𝑆 | 𝑆𝑎 | epsilon
- D.
S → 𝑎𝑆 | epsilon
Attempted by 40 students.
Show answer & explanation
Correct answer: B, C
Analysis of Grammar Ambiguity
A grammar is considered ambiguous if there exists at least one string that has more than one leftmost derivation or parse tree.
Option A generates strings of the form an bn. Each string has a unique derivation sequence, making this grammar unambiguous.
Option B allows multiple parse trees for expressions like id + id * id due to missing operator precedence rules. This creates ambiguity.
Option C allows derivation of strings like 'aa' via left recursion (S -> aS -> aa) or right recursion (S -> Sa -> aa). This results in ambiguity.
Option D generates strings of the form an. Each string length corresponds to a unique number of recursive steps, ensuring a single derivation tree.
Conclusion: Options B and C are ambiguous grammars.
A video solution is available for this question — log in and enroll to watch it.