Question

Which of the following grammars is/are ambiguous?

• A. \(S \rightarrow aSb \mid \epsilon\)
• B. \(E \rightarrow E+E \mid E*E \mid id\)
• C. \(S \rightarrow aS \mid Sa \mid \epsilon\)
• D. \(S \rightarrow aS \mid \epsilon\)

Hint:

Try to find one string in the language that has two different parse trees or two different leftmost derivations; if you can, the grammar is ambiguous.

Answer 1

The Correct Option is B, C

Step 1: Recall what ambiguous means.
A grammar is ambiguous if at least one string in its language has two or more different parse trees, equivalently two different leftmost derivations. We check each grammar by trying to build one string in two different ways.

Step 2: Check option (A), \(S \rightarrow aSb \mid \epsilon\).
This grammar generates strings of the form \(a^n b^n\) for \(n \geq 0\). Every derivation must apply \(S \rightarrow aSb\) exactly \(n\) times, matching each \(a\) with a \(b\) on the outside, and then apply \(S \rightarrow \epsilon\) once. There is only one order in which this nesting can happen for a given string, so each string in the language has exactly one parse tree. This grammar is unambiguous.

Step 3: Check option (B), \(E \rightarrow E+E \mid E*E \mid id\).
This is the classic unparenthesised expression grammar, with no precedence or associativity rule built in. Consider the string \(id+id*id\).
One parse tree groups it as \(id + (id*id)\), applying \(E \rightarrow E+E\) first at the top level.
Another parse tree groups it as \((id+id)*id\), applying \(E \rightarrow E*E\) first at the top level.
Both derivations are valid under the grammar and produce the same string but different parse trees. This grammar is ambiguous.

Step 4: Check option (C), \(S \rightarrow aS \mid Sa \mid \epsilon\).
This grammar generates the language \(a^*\), but it allows growing the string from the left using \(aS\) or from the right using \(Sa\), and these can mix in different orders. Consider the string \(aa\).
One derivation: \(S \rightarrow aS \rightarrow a(aS) \rightarrow aa(\epsilon) = aa\), using \(aS\) twice.
Another derivation: \(S \rightarrow Sa \rightarrow (aS)a \rightarrow a(\epsilon)a = aa\), mixing \(aS\) and \(Sa\).
A third derivation: \(S \rightarrow Sa \rightarrow (Sa)a \rightarrow (\epsilon a)a = aa\), using \(Sa\) twice.
These give different parse trees for the same string \(aa\), so this grammar is ambiguous.

Step 5: Check option (D), \(S \rightarrow aS \mid \epsilon\).
This grammar also generates \(a^*\), but it is purely right linear, growing only on the left through \(aS\). For a string \(a^n\), the rule \(S \rightarrow aS\) must be applied exactly \(n\) times in a row, followed by \(S \rightarrow \epsilon\) once. There is no other way to arrange this single fixed sequence of rule applications. This grammar is unambiguous.

Final Answer:
Grammars (B) and (C) each allow more than one parse tree for some string, so they are ambiguous.
\[ \boxed{\text{(B) and (C)}} \]