美籍波蘭數學傢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使li1li2…lin＝mi1mi2…min，則稱表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.