Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

Post Correspondence Problem

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
Post Correspondence Problem

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 

Domino’s Form

 

2. Table form              

Table form

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

Proof of undecidability

Undecidability of a problem means that there is no particular algorithm that can determine whether a given problem has a solution or not. A common undecidable problem is a Turing problem, so its undecidability is also proved if we can reduce the Turing problem into post Correspondence problem.

Consider an instance of a post correspondence problem that can simulate the computation of an arbitrary Turing Machine on random input. A match will occur if the Turing machine accepts the input. The problem of deciding whether a Turing machine will accept the given information or not is a well-known problem. As the post Correspondence problem reduces to this particular problem, we can say the post correspondence problem is undecidable, which completes our proof.

Check out this problem - Shortest Common Supersequence.

Read About - Moore Machine

Frequently Asked Questions

What is post correspondence problem in automata?

Post correspondence problem is an undecidable problem in automata. 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.

Why is post correspondence problem undecidable?

Because no specific method can tell whether a post correspondence problem has a solution or not, the postman correspondence problem is intractable. The technique for proving the theorem can be done in a number of ways, but they are all essentially the same.

What is the difference between post correspondence problem and modified post correspondence problem?

Identifying whether a set of dominoes has a match or not is the Post's Correspondence Problem (PCP). Similar to PCP, the modified Post's Correspondence Problem (MPCP) just requires that we specify the set of tiles as well as a particular tile.

What is silly post correspondence problem?

A set of dominoes S is in the silly Post Correspondence Problem (SPCP) if and only if S contains a piece whose top string perfectly matches the bottom string. As a result, SPCP is decidable in nature. 

Conclusion

In this article, we have extensively discussed the postman correspondence problem. We started with what domino or tile is, then we saw some examples of how to solve PCP, and then the proof of undecidability.

After reading about the target machines, are you not feeling excited to read/explore more articles on the topic of compiler design? Don’t worry, Coding Ninjas has you covered. To learn, see the compiler design course, and you can visit our website coding ninjas!  

Recommended Readings


Refer to our guided path on Coding Ninjas Studio to upskill yourself in Data structure and algorithmsCompetitive Programming, JavascriptSystem Design, and many more if you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy learning!

Topics covered
1.
Introduction
2.
What is Post correspondence problem?
3.
Example 1: 
3.1.
Explanation:
4.
Example 2:
4.1.
Explanation:
5.
Proof of undecidability
6.
Frequently Asked Questions
6.1.
What is post correspondence problem in automata?
6.2.
Why is post correspondence problem undecidable?
6.3.
What is the difference between post correspondence problem and modified post correspondence problem?
6.4.
What is silly post correspondence problem?
7.
Conclusion