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: The test we will run.
For each grammar, pick one string in its language and try to build it in two genuinely different ways. If we succeed, the grammar is ambiguous. If every string can only be built one way, it is not.

Step 2: Grammar (A), $S \to aSb \mid \epsilon$.
This makes matched strings like $aabb$. Think of it as nested brackets: the outermost $a$ must pair with the outermost $b$, then the next $a$ with the next $b$, and so on inward. There is no freedom in how the nesting can be arranged, so each string has just one shape. Not ambiguous.

Step 3: Grammar (B), $E \to E+E \mid E*E \mid id$.
Take the string $id*id+id$. We can either treat the $*$ as happening first at the top, giving the shape $(id*id)+id$, or treat the $+$ as happening first at the top, giving the shape $id*(id+id)$. Since the grammar has no rule saying $*$ binds tighter than $+$, both top level splits are legal, so we get two different trees for the same string. Ambiguous.

Step 4: Grammar (C), $S \to aS \mid Sa \mid \epsilon$.
Take the short string $a$. We can derive it as $S \to aS \to a\epsilon = a$, or as $S \to Sa \to \epsilon a = a$. These are two distinct derivations, using a different first rule, for the exact same one letter string. So even the simplest nonempty string already has two trees. Ambiguous.

Step 5: Grammar (D), $S \to aS \mid \epsilon$.
Take the string $a$. The only way to produce it is $S \to aS \to a\epsilon = a$. There is no $Sa$ rule to mix in, so there is exactly one route for every string of $a$'s. Not ambiguous.

Step 6: Conclude.
The grammars that allow two different builds for the same string are (B) and (C).
\[ \boxed{\text{(B) and (C)}} \]