if a context free grammar g has more than one derivation tree for some string w ∈ l(g), it is called an ambiguous grammar. there exist multiple right-most or left-most derivations for some string generated from that grammar.

problem

check whether the grammar g with production rules −

x → x+x | x*x |x| a

is ambiguous or not.

solution

let’s find out the derivation tree for the string "a+a*a". it has two leftmost derivations.

derivation 1 − x → x+x → a +x → a+ x*x → a+a*x → a+a*a

parse tree 1 −

derivation 2 − x → x*x → x+x*x → a+ x*x → a+a*x → a+a*a

parse tree 2 −

since there are two parse trees for a single string "a+a*a", the grammar g is ambiguous.