Automata Theory 简明教程

Post Correspondence Problem

在1946年，Emil Post提出了邮递对应问题（PCP），这是一个不可判定性的判定问题。对于一个字母表∑，PCP问题的描述如下−

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 −

给定以下两个列表，在∑上的非空字符串的 M 和 N −

Given the following two lists, M and N of non-empty strings over ∑ −

M = (x1, x2, x3,………, xn)

N = (y1, y2, y3,………, yn)

我们可以说存在一个后缀对应解决方案，如果对于一些 i1,i2,………… ik，其中 1 ≤ ij ≤ n，条件 xi1 …….xik = yi1 …….yik 得到满足。

We can say that there is a Post Correspondence Solution, if for some i1,i2,………… ik, where 1 ≤ ij ≤ n, the condition xi1 …….xik = yi1 …….yik satisfies.

Example 1

找出列表

Find whether the lists

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

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

是否有后缀对应解？

have a Post Correspondence Solution?

Solution

Abb

aaa

Bba

aaa

在此，

Here,

x2x1x3 = ‘aaabbaaa’

及 y2y1y3 = ‘aaabbaaa’

and y2y1y3 = ‘aaabbaaa’

可以看出

We can see that

x2x1x3 = y2y1y3

因此，解为 i = 2, j = 1, and k = 3.

Hence, the solution is i = 2, j = 1, and k = 3.

Example 2

找出列表 M = (ab, bab, bbaaa) 和 N = (a, ba, bab) 是否有后缀对应解？

Find whether the lists M = (ab, bab, bbaaa) and N = (a, ba, bab) have a Post Correspondence Solution?

Solution

bab

bbaaa

bab

在这种情况下，没有解，因为 −

In this case, there is no solution because −

| x2x1x3 | ≠ | y2y1y3 | （长度不相同）

| x2x1x3 | ≠ | y2y1y3 | (Lengths are not same)

因此可以说，这个后缀对应问题是 undecidable 。

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