Problem Solving in Automata, Languages, and Complexity

5.6 Undecidable Problems 275

So, from the above induction proof, we know that either

I[ a!0 * l l l * %+q+p* I

I [ q) * l l l * &+g+p *w+q+p+1*

is a partial solution. Now, we can attach one of the pairs in group 7 to them

to obtain the desired solution.

Conversely, assume that Pz has a solution x. We note that it must begin

with [cue*, since the pair in group 1 is the only one whose top string and

bottom string begin with the same symbol. The only way to extend this

partial solution to x is to add erg* to the top part and, from the observation

above, we know that this will add to the bottom part an extra string 51%.

Continuing this argument, we can see that the solution must contain prefixes

of the form

[a() 51% l l l a!j

for an even i, or

for an odd i. Now, suppose M does not halt on 2, then the computation of
M(z) never enters the state qn, and so these partial solutions do not contain
qn or in and, hence, do not contain qn+l or &+I. However, the two pairs of
group 7 are the only ones whose two strings have the same ending symbol,
and they contain either qn+l or &+I. That is a contradiction. We conclude
that M must halt on X.^0

Example 5.46 Prove that the problem of determining whether two given

context-free grammars Gl and G2 have the property L(G1) CT L(G2) = 8 is

undecidable.

Proof. Let A = {(G,G2) I L(6) n L(G2) = 8). We reduce the prob-

lem PCP to A. Let C be a fixed alphabet with respect to which PCP is

known to be undecidable. Let $ be a symbol not in C. For any instance

{(Q, Yl), l l l I (zn, y,J} of PCP, we construct two grammars G1 and G2 over

the alphabet C U {$} as follows:

Grammar G1 consists of the following rules:

S + aSa 1 a%, for all a E C.

So, L(G1) = {w$wR 1 w E C+}. G rammar G2 consists of the following rules:

S,-KI$?J~ IX;$yR, for alli= l,...,n.