Grammatical Ambiguity
Definition: Let G = (N, T, P, S) be a CFG.
If there exists x Î L(G) with more than one derivation tree, then G is ambiguous; otherwise, G is unambiguous.
Definition: A CFL, L,  is inherently ambiguous if L is generated by no unambiguous grammar.
Example:
• Gexpr1 is unambiguous, because for every x Î L(Gexpr1) there exists only one derivation tree
• Gexpr2 is ambiguous, because for i+i*i Î L(Gexpr2) there exist two derivation trees
• Lexpr = L(Gexpr1) = L(Gexpr2) is not inherently ambiguous because Gexpr1 is unambiguous
19/50