个性化阅读
专注于IT技术分析

自动机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


赞(0) 打赏
未经允许不得转载:srcmini » 自动机Post通信问题
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏