Ambiguous Grammar Identification

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

Grammar Analysis

1. Grammar $S \rightarrow aSb \mid \epsilon$

This grammar generates the language $L = \{a^n b^n \mid n \ge 0\}$. For any string generated by this grammar, there is only one possible sequence of production rules to follow. For example, to generate $a^2b^2$, the derivation must be $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$. This grammar is unambiguous.

2. Grammar $E \rightarrow E + E \mid E * E \mid id$

This grammar is commonly used for arithmetic expressions. It is ambiguous because it does not inherently define the precedence or associativity of operators '+' and '*'. For instance, the string $id + id * id$ can be parsed in multiple ways:

• $(id + id) * id$ (implying '+' has higher precedence or is evaluated left-to-right before '*')
• $id + (id * id)$ (implying '*' has higher precedence)

The existence of multiple parse trees for the same string demonstrates ambiguity.

3. Grammar $S \rightarrow aS \mid Sa \mid \epsilon$

This grammar generates strings containing any number of 'a's. Consider the string $aa$. It can be derived in multiple ways:

• Derivation 1: $S \Rightarrow aS \Rightarrow a(Sa) \Rightarrow a(a\epsilon) = aa$
• Derivation 2: $S \Rightarrow Sa \Rightarrow (aS)a \Rightarrow (a\epsilon)a = aa$

Since there are multiple distinct leftmost derivations (and thus parse trees) for the string $aa$, this grammar is ambiguous.

4. Grammar $S \rightarrow aS \mid \epsilon$

This grammar generates the language $L = \{a^n \mid n \ge 0\}$. To generate any string $a^n$, the only possible derivation involves applying the rule $S \rightarrow aS$ exactly $n$ times, followed by $S \rightarrow \epsilon$. For example, $S \Rightarrow aS \Rightarrow aaS \Rightarrow aaaS \Rightarrow aaaa$. There is only one sequence of choices. This grammar is unambiguous.

Conclusion

Based on the analysis, grammars 2 ($E \rightarrow E + E \mid E * E \mid id$) and 3 ($S \rightarrow aS \mid Sa \mid \epsilon$) are ambiguous.