G B =({S,S B },Σ ∪{a 1 ,a 2 ,…a n },P B ,S)
then clearly
and
L(G) = L A ∪ L B
It is easy to see that G A and G B by themselves are unambiguous. If a given
string in L(G) ends with a i , then its derivation with grammar G A must have
started with S ⇒ w i Sa i . Similarly, we can tell at any later stage which rule has to
be applied. Thus, if G is ambiguous it must be because there is a w for which
there are two derivations
and
Consequently, if G is ambiguous, then the Post correspondence problem with the
pair (A, B)has a solution. Conversely, if G is unambiguous, then the Post
correspondence problem cannot have a solution.
If there existed an algorithm for solving the ambiguity problem, we could
adapt it to solve the Post correspondence problem as shown in Figure 12.14. But
since there is no algorithm for the Post correspondence problem, we conclude
that the ambiguity problem is undecidable.
Figure 12.14
PC algorithm.