276 COMPUTABILITYTHEORY
Then, L(G2) = {xi,xi, .*x;m$(yilyiz ..yim)R 1 i&,.. .,i, E (1,.. .,n},
m > 1).
Now, if the instance {(zl,y&... , (zn, yn)} has a solution, then L(G2)
contains at least a string of the form UI$W~ and so L(G1) n L(G2) # 0. If it
has no sulution, then L(G2) d oes not contain any string of the form w$wR
and so L(G1) n L(G2) = 8. Th us, this construction is a reduction from PCP
to X, and so A is undecidable. cl
Recall that a context-free grammar G is ambiguous if there exists a string
2 E L(G) such that there are two distinct leftmost derivations S & x for X.
L
Example 5.47 Prove that the problem of determining whether a given
context-free grammar G is ambiguous is undecidable.
Proof. We reduce PCP to the ambiguity problem of the context-free gram-
mars. For each instance { (~1, yl),... , (zn, y,>} of PCP over alphabet C, de-
fine a context-free grammar G that has the following rules:
S1 -+ x&ba”b 1 xibaib, for all 1 < - i < - n,
5‘2 + y&baib 1 yibaib, for all 1 < - i < - n,where a, b 4 C.
We observe that if the instance {(xl, yl),... , (x,, yn)} of PCP has a solu-
tion xi1xi2 l l l x:ik, then the string..
x = x;,x~,..~x~,baakb..~baa2bba2’b
has two distinct leftmost derivations, one from S1 and the other from S2.
Conversely, we note that if Si 5 x then it is easy to see that there must
be a unique derivation from S1 to x, and x must be of the form...
xilxi2 •w~x~kba2kb~~~baa2bba21b. (5 5).
Similarly, if S2 3 x then there must be a unique derivation from S2 to x and
z must be of the form
Yjl Yj2 l ’ l yj,baj’b**. baj2 bbajl b.
So, suppose that x E L(G) h as t wo distinct derivations, then
two derivations of the form S 3 S1 5 x and S 3 S2 3 x.
x must be of the form (5.5) and of the form (5.6). Since a, b $
true that k = k? and il = j,,... , ik = j,. It follows that xi1xi2
to yilyi2 l l l yik 7 and is a solution to the instance {(xi, yl),... , (
(5. 6)they must be
Furthermore,
C, it must be.. xik is equal
Xnt Yn >I l^0