Post Correspondence Problem - Automata Theory

What is Post Correspondence Problem?

The Post Correspondence Problem (PCP) was invented by Emil Post in 1946. It is called as an undecidable decision problem. The PCP problem rather than an alphabet ∑ is considered as follows −

As for the below mentioned two lists, M and N of non-empty strings over ∑ −

cv

Example 1

Let’s see if the lists

M = (abb, aa, aaa) and N = (bba, aaa, aa)

Include a Post Correspondence Solution?

Solution

x1 x2 x3
M Abb aa aaa
N Bba aaa aa

So,

ty

The final solution is i = 2, j = 1, and k = 3.

Example 2

Let’s explore that the lists M = (ab, bab, bbaaa) and N = (a, ba, bab) include a Post Correspondence Solution?

x1

x2

x3

M

ab

bab

bbaaa

N

a

ba

bab

So it doesn’t include a solution because −

cxq | (Lengths are not same)

Hence, it can be said that this Post Correspondence Problem is undecidable.

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics