
Introduction
The post correspondence problem is an undecidable decision problem introduced by Emil post in 1946. The post correspondence problem consists of two strings, A and B, of equal input. The two lists of strings are A =y1,y2,y3…,yn , B= x1,x2,x3….xn, then there exists a non-empty list of integers i1,i2,i3…. Such that, x1,x2,x3…xn = y1,y2,y3…..yn.
There is N number of dominos in this problem, also known as tiles. The task is to arrange dominos so that strings made by the numerator and strings produced by the denominator are equal.
Also see, Turing Machine in TOC.
What is Post Correspondence Problem?
Post correspondence problem is an undecidable problem. It was introduced by Emil Post in 1946. Here in this problem, there is N number of dominos, i.e., tiles. And we have to arrange the dominos in such a way that the string produced by the denominators and the numerators is same.
Post Correspondence problem can be represented in two ways:
1. Domino’s Form

2. Table form

Example of Post Correspondence Problem
Example 1:
A | B | |
1. | 1 | 111 |
2. | 10111 | 10 |
3. | 10 | 0 |
Explanation:
- Step-1: First, we will start with a domino in which the first symbol at the top and the first symbol at the bottom is the same. In this example, we will go with the second domino.
The string at the top is 10111, and the string at the bottom is 10.
A: 1 0 1 1 1
B: 1 0
- Step-2: Now, we need 1’s in the denominator to match the 1’s in the numerator; we will go with the first domino. The string at the top is 10111 1, and the string at the bottom is 10111.
A: 1 0 1 1 1 1
B: 1 0 1 1 1
- Step-3: Now, there is an extra 1 in the numerator, and to match this 1, we will add the first domino again in sequence. The string at the top is 1011111, and the bottom is 10111111.
A: 1 0 1 1 1 1 1
B: 1 0 1 1 1 1 1 1
- Step-4: Now there is an extra 1 in the denominator, and to match it, we will add the third domino; the string at the top is 101111110, and the string at the bottom is 101111110.
A: 1 0 1 1 1 1 1 1 0
B: 1 0 1 1 1 1 1 1 0
Sequence for this solution is: 2 1 1 3
Example 2:
Numerator | Denominator | |
1 | B | CA |
2 | A | AB |
2 | CA | A |
4 | ABC | C |
Explanation:
- Step-1: We will start with a domino in which 1st symbol at the numerator and the first symbol at the denominator are the same. So we will choose domino 2.
A: A
B: A B
- Step-2: Now, we need B in the numerator and denominator to match the numerator; we will go with domino 1.
A: A B
B: A B C A
- Step-3: Now, for matching the denominator, we will add domino 3 for matching the numerator.
A: A B C A
B: A B C A A
-
Step-4: There is an extra A in the denominator, so to match the string, we will add domino 2.
A: A B C A A
B: A B C A A A B - Step-5: There is an extra AB in the denominator; to match it, we will add domino 4. The string in the denominator and numerator is ABCAAABC and ABCAAABC, respectively.
A: A B C A A A B C
B: A B C A A A B C
Sequence: 21324