Question 7717 – Theory-of-Computation

Before solving this question you should know what is PCP problem.
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.