Theorem 12.9
There exists no algorithm for deciding whether or not
L(G 1 ) L(G 2 ) = Ø
for arbitrary context-free grammars G 1 and G 2 .
Proof: Take as G 1 the grammar G A and as G 2 the grammar G B as defined in the
proof of Theorem 12.8. Suppose that L (G A ) and L (G B ) have a common
element, that is,
and
Then the pair (A, B) has a PC solution. Conversely, if the pair does not have a PC
solution, then L(G A ) and L (G B ) cannot have a common element. We conclude
that L (G A ) L(G B ) is nonempty if and only if (A,B) has a PC solution. This
reduction proves the theorem.
There is a variety of other known results along these lines. Some of them can
be reduced to the Post correspondence problem, while others are more easily
solved by establishing different intermediate results first (see, for example,
Exercises 6 and 7 at the end of this section). We will not give the arguments
here, but point to some additional results in the exercises.
That there are many undecidable problems connected with context-free
languages seems surprising at first and shows that there are limitations to
computations in an area in which we might be tempted to try an algorithmic
approach. For example, it would be helpful if we could tell if a programming