*76*

# Post Correspondence Problem

In this section, we will discuss the undecidability of string and not of Turing machines. The undecidability of the string is determined with the help of Postâ€™s Correspondence Problem (PCP). Let us define the PCP.

â€œThe Postâ€™s correspondence problem consists of two lists of string that are of equal length over the input. The two lists are A = w_{1}, w_{2}, w_{3}, â€¦. , w_{n} and B = x_{1}, x_{2}, x_{3}, â€¦. x_{n} then there exists a non empty set of integers i_{1}, i_{2}, i_{3}, â€¦. , in such that,

w_{1}, w_{2}, w_{3}, â€¦. w_{n} = x_{1}, x_{2}, x_{3}, â€¦. x_{n}â€œ

To solve the post correspondence problem we try all the combinations of i_{1}, i_{2}, i_{3}, â€¦. , in to find the w1 = x1 then we say that PCP has a solution.

### Example 1:

Consider the correspondence system as given below

A = (b, bab^{3}, ba) and B = (b^{3}, ba, a). The input set is âˆ‘ = {0, 1}. Find the solution.

**Solution:**

A solution is 2, 1, 1, 3. That means w_{2}w_{1}w_{1}w_{3} = x_{2}x_{1}x_{1}x_{3}

The constructed string from both lists is bab^{3}b^{3}a.

### Example 2:

Does PCP with two lists x = (b, a, aba, bb) and y = (ba, ba, ab, b) have a solution?

**Solution:** Now we have to find out such a sequence that strings formed by x and y are identical. Such a sequence is 1, 2, 1, 3, 3, 4. Hence from x and y list

### Example 3:

Obtain the solution for the following system of posts correspondence problem. A = {100, 0, 1}, B = {1, 100, 00}

**Solution:** Consider the sequence 1, 3, 2. The string obtained from A = babababb. The string obtained from B = bababbbb. These two strings are not equal. Thus if we try various combination from both the sets to find the unique sequence, we could not get such a sequence. Hence there is no solution for this system.

### Example 4:

Obtain the solution for the following system of posts correspondence problem, X = {100, 0, 1}, Y = {1, 100, 00}.

**Solution:** The solution is 1, 3, 1, 1, 3, 2, 2. The string is

X1X3X1X1X3X2X2 = 100 + 1 + 100 + 100 + 1 + 0 + 0 = 1001100100100

Y1Y3Y1Y1Y3Y2Y2 = 1 + 00 + 1 + 1 + 00 + 100 + 100 = 1001100100100