Which of the following grammars is/are ambiguous?

A context-free grammar is ambiguous if there exists at least one string generated by the grammar that has more than one distinct leftmost derivation (or more than one parse tree).

• Option (A): $S \rightarrow aSb \mid \epsilon$ This grammar generates the language $L = \{a^n b^n \mid n \ge 0\}$. Every string of length $2n$ has a unique derivation sequence, so it is unambiguous.

• Option (B): $E \rightarrow E + E \mid E * E \mid \text{id}$ This is the classic ambiguous arithmetic expression grammar. For example, the string $\text{id} + \text{id} * \text{id}$ can be parsed as either $(\text{id} + \text{id}) * \text{id}$ or $\text{id} + (\text{id} * \text{id})$, resulting in two different parse trees. Hence, it is ambiguous.

• Option (C): $S \rightarrow aS \mid Sa \mid \epsilon$ This grammar generates $L = a^*$. Consider the string $w = a$:

  1. $S \Rightarrow aS \Rightarrow a\epsilon = a$

  2. $S \Rightarrow Sa \Rightarrow \epsilon a = a$

  Since there are two distinct leftmost derivations for the string $a$, the grammar is ambiguous.

• Option (D): $S \rightarrow aS \mid \epsilon$ This grammar generates $L = a^*$ and is regular/right-linear. Each string $a^n$ has a unique derivation, so it is unambiguous.

Therefore, the ambiguous grammars are B and C.