[拼音]：Bosite duiying wenti

[外文]：Post correspondence problem

美籍波兰数学家E.L.波斯特于1944年提出的一个重要的判定问题。字符集A是字符的非空有限 ，A中字符的有限序列称为A上的字符串。设u1，u2，…，um是A上的字符串，用u1u2…um表示把这字符串中的m个字符连接在一起所得到的字符串。A上的表是A上的字符串的有限序列，序列的长度称为表的长度。例如，ab，∧，aa是字符集｛a，b｝上的长度为3的表，其中∧表示不含任何字符的空字符串。

设l1，l2，…，lk和m1，m2，…，mk是同一字符集A上的两个相同长度的表，如果存在小于或等于k的正整数i1，i2，…，in使l彨l彸…l拠＝m彨m彸…m拠，则称表l1，l2，…，lk和m1，m2，…，mk有匹配。例如，A＝｛0，1｝，l1＝1，l2＝10111，l3＝10，m1＝111，m2＝10，m3＝0，因l2l1l1l3＝m2m1m1m3＝101111110，因此，l1，l2，l3和m1，m2，m3有匹配。判定同一字符集上的任意两个相同长度的表有没有匹配的问题称为波斯特对应问题。

由于图灵机的停机问题是不可判定的，可以推出波斯特对应问题也是不可判定的，即不可能找到一个算法来判定同一字符集上的任意两个相同长度的表是否有匹配。

波斯特对应问题在形式语言理论和程序设计理论中有重要应用。由于波斯特对应问题是不可判定的，可推出形式语言理论和程序设计理论中的许多问题是不可判定的。例如，任意上下文无关语言是否有歧义，这个问题就是不可判定的。

参考书目

J. Hopcroft and J. Ullman， Introduction to Automata Theory， Languages， and Computation，Addison-Wesleg，Reading，Mass，1979.

严正声明：本文由历史百科网注册或游客用户昊磊自行上传发布关于» 波斯特对应问题的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：昊磊；本文链接：https://www.freedefine.cn/wenzhan/49105.html