COMS W3261 CS Theory
Lecture 17: Post's Correspondence Problem

1. Complements of L_d and L_u

The diagonal language L_d is not recursively enumerable.
The universal language L_u is recursively enumerable but not recursive.
The complement of the diagonal language is recursively enumerable but not recursive.
The complement of the universal language is not recursively enumerable.
Note that if the complement of a recursively enumerable language L is recursively enumerable, then L and its complement are both recursive.

We now prove a string-oriented problem called Post's Correspondence Problem is undecidable. We will use PCP to show various important problems about context-free grammars are undecidable.
An instance of Post's correspondence problem consists of two lists of strings over some alphabet where the two lists have the same number of strings. Let A = (w₁, w₂, …, w_k) and B = (x₁, x₂, …, x_k) be the two lists.
A solution to this instance of PCP, if one exists, is a sequence of one or more integers i₁, i₂, …, i_m such that w_i₁ w_i₂ … w_{i_m} = x_i₁ x_i₂ … x_{i_m}. An integer index can be repeated many times in a solution.
Example: Consider the instance of PCP with A = (a, b, ca, abc) and B = (ab, ca, a, c). The sequence 1, 2, 3, 1, 4 is a solution because the same string abcaaabc is obtained by concatenating the corresponding strings from either list A [(a)(b)(ca)(a)(abc)] or list B [(ab)(ca)(a)(ab)(c)].
Post's correspondence problem is to determine whether an instance has a solution.
We will show that Post’s correspondence problem is undecidable by reducing the universal language to PCP.
We will then show that the ambiguity problem for CFG’s is undecidable by reducing PCP to the ambiguity problem for CFG’s.

The Modified PCP has the additional requirement that the first string from list A and the first string from list B has to be the first string in the solution. The example above has this property.
Formally, a solution to an instance of the MPCP is a sequence of zero or more integers i₁, i₂, …, i_m such that w₁w_i₁ w_i₂ … w_{i_m} = x₁x_i₁ x_i₂ … x_{i_m}.
We can show that the modified PCP problem can be reduced to the PCP problem as follows:

We are given an instance of MPCP with lists A = (w₁, w₂, …, w_k) and B = (x₁, x₂, …, x_k).
Assume * and $ are new symbols.
From (A, B) we construct a PCP instance (C, D) with
C = (y₀, y₁, …, y_k+1) and D = (z₀, z₁, …, z_k+1) where
1. y_i is w_i with a * after each symbol in w_i, for i = 1, 2, ..., k.
2. z_i is x_i with a * before each symbol in x_i, for i = 1, 2, ..., k.
3. y₀ = *y₁ and y_k+1 = $.
4. z₀ = z₁ and z_k+1 = *$.
We can show i₁, i₂, …, i_m is a solution to the given (A,B)-MPCP instance iff 0, i₁, i₂, …, i_m, i_k+1 is a solution to this constructed (C, D)-PCP instance.

We can show that given (M, w), an instance of L_u, we can reduce this instance of L_u to an instance (A, B) of the MPCP such that M accepts w iff (A, B) has a solution. We do this by showing that (A, B) simulates the computation of M on w. See Section 9.4.3 of HMU, pp. 407-412, for details.
This shows that both the MPCP and the PCP problems are undecidable.

We can reduce an instance of the PCP problem to an instance of determining whether a CFG is ambiguous, thereby showing it is undecidable to determine whether a CFG is ambiguous.
We will illustrate the reduction with the following example. Let (A, B) be an instance of the PCP problem with A = (a, b, ca, abc) and B = (ab, ca, a, c). Let G be the CFG with the productions


S → A | B
A → aA1 | bA2 | caA3 | abcA4 | a1| b2 | ca3 | abc4
B → abB1 | caB2 | aB3 | cB4 | ab1 | ca2 | a3 | c4

There are two distinct leftmost derivations for the string abcaaabc41321 because this instance of the PCP problem has a solution.

Does the following instance of PCP have a solution: A = (ab, aab, ba) and B = (abb, ba, aa)?
Does the following instance of PCP have a solution: A = (ab, b, aba, aa) and B = (abab, a, b, a)?
Does the following instance of PCP have a solution: A = (ab, baa, aba) and B = (aba, aa, baa)?
Is PCP on lists over a single-symbol alphabet decidable?
Show that the PCP problem can be formulated as a language recognition problem.