Question

Which of the following grammars is/are ambiguous?

• A. 𝑆→𝑎𝑆𝑏 | 𝜖
• B. 𝐸→𝐸+ 𝐸 | 𝐸∗𝐸 | 𝑖𝑑
• C. 𝑆→𝑎𝑆 | 𝑆𝑎 | 𝜖
• D. 𝑆→𝑎𝑆 | 𝜖

Hint:

Look for a string with more than one distinct parse tree; grammar B (no operator precedence between + and *) and grammar C (mixed left and right recursion on the same symbol) both admit this, while A and D generate every string uniquely.

Answer 1

The Correct Option is B, C

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

Step 1: Check Option A - \(S \to aSb \mid \epsilon\). This generates \(\{a^n b^n \mid n \ge 0\}\). Every string has exactly one derivation, since at each step there is only one way to expand \(S\) (terminate with \(\epsilon\), or wrap another \(a \ldots b\) pair). Unambiguous.

Step 2: Check Option B - \(E \to E+E \mid E*E \mid id\). Consider the string \(id + id * id\). It can be parsed as \((id + id) * id\) (applying \(+\) first) or as \(id + (id * id)\) (applying \(*\) first). Since the grammar defines no precedence or associativity, both are valid derivations, giving two distinct parse trees for the same string. Ambiguous.

Step 3: Check Option C - \(S \to aS \mid Sa \mid \epsilon\). This generates \(\{a^n \mid n \ge 0\}\), but because both left recursion (\(Sa\)) and right recursion (\(aS\)) are available simultaneously, a string like \(aa\) can be built in more than one structurally distinct way (attaching the two symbols in different orders via \(aS\) versus \(Sa\)), producing multiple parse trees for the same string. Ambiguous.

Step 4: Check Option D - \(S \to aS \mid \epsilon\). A simple right-linear grammar generating \(\{a^n \mid n \ge 0\}\), with only one production choice at each step. Every string has a unique derivation. Unambiguous.

Final Answer: \(\boxed{\text{Options B and C are ambiguous}}\)