problem is undecidable; consequently, we cannot have an algorithm for deciding
the Post correspondence problem.
EXERCISES
1. Let A = {001, 0011,11,101} and B = {01, 111, 111, 010}. Does the pair (A,B)
have a PC solution? Does it have an MPC solution?
2. Provide the details of the proof of Theorem 12.5.
3. Show that for |Σ| = 1, the Post correspondence problem is decidable, that is,
there is an algorithm that can decide whether or not (A,B) has a PC solution
for any given (A,B) on a single-letter alphabet.
4. Suppose we restrict the domain of the Post correspondence problem to
include only alphabets with exactly two symbols. Is the resulting
correspondence problem decidable?
5. Show that the following modifications of the Post correspondence problem
are undecidable.
(a) There is an MPC solution if there is a sequence of integers such that
w i w j …w k w 1 = v i v j …v k v 1 .
(b) There is an MPC solution if there is a sequence of integers such that
w 1 w 2 w i w j …w k = v 1 v 2 v i v j …v k
6. The correspondence pair (A, B) is said to have an even PC solution if and
only if there exists a nonempty sequence of even integers i,j,…k such that
w i w j …w k = v i v j …v k . Show that the problem of deciding whether or not an
arbitrary pair (A,B) has an even PC solution is undecidable.
12.4 Undecidable Problems for Context-Free
Languages
The Post correspondence problem is a convenient tool for studying undecidable
questions for context-free languages. We illustrate this with a few selected
results.