Theorem 12.8
There exists no algorithm for deciding whether any given context-free grammar
is ambiguous.
Proof: Consider two sequences of strings A = (w 1 ,w 2 ,…,w n )and B = (v 1 ,v 2 ,
…v n )over some alphabet Σ. Choose a newset of distinct symbols a 1 ,,a 2 ,…, a n ,
such that
{a 1 ,a 2 ,…,a n } Σ = Ø,
and consider the two languages
L A = {w i w j …w l w k a k a l …a j a i }
and
L B = {v i v j …v l v k a k a l …a j a i }
Now look at the context-free grammar
G =({S, S A ,S B },Σ ∪ {a 1 ,,a 2 ,…a n },P,S),
where the set of productions P is the union of the two subsets: The first set P A
consists of
while the second set P B has the productions
Take
G A =({S,S A },Σ ∪{a 1 ,a 2 ,…a n },P A ,S)
and