the post correspondence problem (pcp), introduced by emil post in 1946, is an undecidable decision problem. the pcp problem over an alphabet ∑ is stated as follows −

given the following two lists, m and n of non-empty strings over ∑ −

m = (x₁, x₂, x₃,………, x_n)

n = (y₁, y₂, y₃,………, y_n)

we can say that there is a post correspondence solution, if for some i₁,i₂,………… i_k, where 1 ≤ i_j ≤ n, the condition x_i1 …….x_ik = y_i1 …….y_ik satisfies.

example 1

find whether the lists

m = (abb, aa, aaa) and n = (bba, aaa, aa)

have a post correspondence solution?

solution

here,

x₂x₁x₃ = ‘aaabbaaa’

and y₂y₁y₃ = ‘aaabbaaa’

we can see that

x₂x₁x₃ = y₂y₁y₃

hence, the solution is i = 2, j = 1, and k = 3.

example 2

find whether the lists m = (ab, bab, bbaaa) and n = (a, ba, bab) have a post correspondence solution?

solution

in this case, there is no solution because −

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (lengths are not same)

hence, it can be said that this post correspondence problem is undecidable.