自动机Post通信问题

在本节中，我们将讨论字符串的不确定性，而不是图灵机的不确定性。字符串的不确定性借助Post的对应问题（PCP）来确定。让我们定义PCP。

“该帖子的对应问题由两个在输入上长度相等的字符串列表组成。这两个列表分别是A = w1，w2，w3，…，wn和B = x1，x2，x3，… 。xn，则存在一个非空的整数集i1，i2，i3，…，这样w1，w2，w3，… wn = x1，x2，x3，…. xn”

为了解决岗位对应问题，我们尝试将i1，i2，i3，…的所有组合找出w1 = x1，然后说PCP有解决方案。

范例1：

考虑如下所示的通信系统

A =（b，bab3，ba）和B =（b3，ba，a）。输入集为∑ = {0，1}。找到解决方案。

解：

解为2、1、1、3。这意味着w2w1w1w3 = x2x1x1x3

这两个列表中构造的字符串都是bab3b3a。

范例2：

具有两个列表x =（b，a，aba，bb）和y =（ba，ba，ab，b）的PCP是否有解决方案？

解决方案：现在我们必须找出一个序列，使得由x和y组成的字符串相同。这样的序列是1、2、1、3、3、4。因此从x和y列表

范例3：

为以下系统的帖子对应问题获取解决方案。 A = {100，0，1}，B = {1，100，00}

解决方案：考虑序列1、3、2。从A = babababb获得的字符串。从B = bababbbb获得的字符串。这两个字符串不相等。因此，如果我们尝试从这两个集合中进行各种组合以找到唯一的序列，则无法获得这样的序列。因此，该系统没有解决方案。

范例4：

获得以下帖子对应问题系统的解决方案，X = {100，0，1}，Y = {1，100，00}。

解决方案：解决方案为1、3、1、1、3、2、2。字符串为

X1X3X1X1X3X2X2 = 100 1 100 100 1 0 0 = 1001100100100 Y1Y3Y1Y1Y3Y2Y2 = 1 00 1 1 00 100 100 = 1001100100100