波斯特对应问题

[拼音]：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有匹配。判定同一字符集上的任意两个相同长度的表有没有匹配的问题称为波斯特对应问题。

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

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

参考书目
  1. J. Hopcroft and J. Ullman， Introduction to Automata Theory， Languages， and Computation，Addison-Wesleg，Reading，Mass，1979.
阅读全文