Automata Theory 简明教程

Post Correspondence Problem

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

给定以下两个列表,在∑上的非空字符串的 MN

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

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

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

Example 1

找出列表

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

是否有后缀对应解?

Solution

x1

x2

x3

M

Abb

aa

aaa

N

Bba

aaa

aa

在此,

x2x1x3 = ‘aaabbaaa’

y2y1y3 = ‘aaabbaaa’

可以看出

x2x1x3 = y2y1y3

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

Example 2

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

Solution

x1

x2

x3

M

ab

bab

bbaaa

N

a

ba

bab

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

| x2x1x3 | ≠ | y2y1y3 | (长度不相同)

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