不可判定的文法問題

把波斯特對應問題兌現

本階第 3 篇交給你一個古怪的小獎品：波斯特對應問題（PCP）——給你一箱像骨牌的磚，每張有一個上方字串與一個下方字串，你能不能排出某些磚（可重複），使得沿上方串接出的字串，恰好等於沿下方串接出的字串？——是不可判定的。那感覺像個趣味玩意兒。本篇正是它兌現的地方。PCP 是完美的撬棍：它純粹講字串對齊，而那正是上下文無關文法擅長產生的東西。所以我們要拿 PCP 這個已知不可判定的問題，把它歸約到一連串看似無辜的文法問題——然後看著這些問題一個個繼承 PCP 的不可判定性。

把方向牢牢記住，因為這是初學者唯一會弄反、也是唯一讓論證成立的關鍵。我們不是要解 PCP。我們要證明某個文法問題很難，所以從已知很難的問題（PCP）歸約到那個文法問題。形狀永遠是：「如果我有一個能判定這個文法問題的魔法盒，我就能餵給它一些巧妙構造的文法，並從中讀出 PCP 的答案。」既然 PCP 沒有判定器，這個魔法盒就不可能存在，於是該文法問題也沒有判定器。若把方向反過來——構造 PCP 實例去回答文法問題——你什麼也證不出來，就像「一場難的考試可歸約到一場簡單的考試」這件事，對那場難考試什麼也沒說。

橋樑：把一箱磚變成兩個文法

底下幾乎一切的動力，都來自這一個巧妙的構造。拿任何一個 PCP 實例：第 i 張磚的上方字串為 t_i、下方字串為 b_i，在某個字母表上。我們從中造出兩個文法。「上方」文法 T_top 恰好產生你能從任何一串有效磚序列的上方讀出的字串，並把磚的索引序列當成標籤記在尾端；「下方」文法 T_bot 對下方字串做同樣的事，用相同的索引標籤。關鍵就在這個索引標籤——以反序寫下——這樣一來，兩個文法共有的字串就必須在上方與下方用上完全相同的磚序。兩個文法都確實是上下文無關的：各自不過是「挑一張磚、吐出它的字串、遞迴、再吐出索引」。

PCP instance:  tile 1 = (top "a", bot "ab"),  tile 2 = (top "b", bot "")

T_top:  S -> a S 1 | b S 2 | a 1 | b 2        (emit a top string, tag index)
T_bot:  S -> ab S 1 |  S 2 | ab 1 | 2         (emit the bottom string, same tag)

A string in BOTH languages, e.g.  "ab" + reversed-index "21":
   top reading  a , b   uses tiles 1,2 -> tops "a"+"b" = "ab"   tag 2 1
   bot reading ab , (eps) uses tiles 1,2 -> bots "ab"+"" = "ab"  tag 2 1
=> a shared string EXISTS  <=>  the PCP match (tiles 1,2) EXISTS

一個迷你 PCP 磚箱變成兩個上下文無關文法。它們共有的字串就編碼了一個 PCP 解：索引標籤逼使上方與下方用上相同的磚序。

盯著那張圖的笑點：兩個語言共有一個字串，當且僅當 PCP 實例有匹配。所以一個能回答「這兩個上下文無關文法產生任何共同字串嗎？」——也就是「兩個上下文無關語言的交集非空嗎？」——的魔法盒，就能讓我們判定 PCP。它並不存在，所以我們剛剛證明了：測試兩個 CFG 是否共有一個字串，不可判定。（留意這個質地：單獨的 CFL 很乖巧，但上下文無關語言在交集下不封閉，而這個構造正好住在那道裂縫裡。這就是我們接下來會帶著變化、反覆用於歧義性、全集性與等價性的那個歸約。）

一系列不可判定的文法問題

從那一道橋，一整列不可判定的文法問題紛紛掉落，各自只需一點小調整。首先是歧義性。一個文法若有某字串擁有兩棵不同的剖析樹，就是有歧義的。拿我們的兩個文法 T_top 與 T_bot，把它們的起始符號改名，再用一條全新的起始規則 S -> S_top | S_bot 把它們黏起來。這個合併文法有歧義，恰好當某個字串被兩半都產生時——而那（由橋）恰好當 PCP 實例有匹配時發生。所以一個判定歧義性的判定器，就能判定 PCP。結論：不存在任何演算法，能拿一個上下文無關文法、總是告訴你它有沒有歧義。剖析器產生器關於歧義性的警告都是啟發式的，永遠不是完整的檢查。

接著是全集性與等價性——這裡有個漂亮的轉折。你也許會猜我們會去測試兩個文法是否共有一個字串，但結果翻到補集反而更容易。對單一個 PCP 實例，我們可以造一個文法，其語言是有效匹配集合的補集（每一個不是「上等於下」之解的字串；這個補集恰好是上下文無關的，即使匹配本身未必如此）。這個文法產生其字母表上的每一個字串——也就是它是全集的，L(G) = Σ（Σ 是 Σ 上所有字串的集合）——恰好當根本沒有匹配時。所以「這個文法產生所有字串嗎？」不可判定。而一旦全集性不可判定，等價性（兩個文法產生相同語言嗎？）也就不可判定了：只要問你的文法，是否等價於一個顯然產生 Σ* 的固定瑣碎文法即可。同一份不可能性，一行就借了過來。

界線：哪些文法問題仍然可判定

我們很容易帶著「關於文法的一切都沒救了」的想法離開，但那是錯的，而這份對比很有啟發性。好幾個基本的文法問題完全可判定。成員性——「文法 G 產生字串 w 嗎？」——可判定：把 G 轉成正規形式，再跑一個像 CYK 的剖析演算法，時間 O(n^3)，其中 n 是 w 的長度（這個三次方是最壞情況的上界，不是承諾每個輸入都會慢）。空性——「G 究竟產不產生任何字串？」——也可判定：標出哪些非終端符最終能產出一串終端符，由下而上傳播這些標記，再檢查起始符號有沒有被標到。有限性——「L(G) 有限嗎？」——可由在有用的非終端符中尋找一個「可幫浦」的循環來判定。這些都沒碰到 PCP，所以都沒被毒害。

那麼，可判定與不可判定的問題之間，差別在哪？仔細看：可判定的那些（成員性、空性、有限性）談的是單一個文法的語言、自成一體。不可判定的那些（等價性、全集性、歧義性、共有字串）全都偷偷在比較兩個語言，或要求語言填滿整個 Σ——而那正是「在交集與補集下不封閉」這件事讓 PCP 得以偷渡進來的位置。作為一個健全性檢查，對照你先前見過的 DFA 等價問題，它是*可判定的：正規語言在所有運算下都封閉，你可以最小化再比較，而且 DFA 是個有限、可完全攤開描繪的物件。文法能以 DFA 辦不到的方式編碼任意計算，而那份多出來的能力，正是讓你賠掉可判定性的東西。

沿層級往上：圖靈機的空性與等價

同一份歸約的肌肉能往上搆到一階，搆到圖靈機，而那裡情況更糟。對一台圖靈機 M，問：「L(M) 是空的嗎？」——M 什麼都不接受嗎？這個 E_TM 問題不可判定，而歸約很直接：從接受問題 A_TM（「M 接受 w 嗎？」）的一個實例，造一台機器，它無視自己的輸入、單純在 w 上模擬 M，當 M 接受時就接受。這台造出的機器，其語言為空，恰好當 M 不接受 w 時。因此一個判定空性的判定器就能判定 A_TM——而那我們已經證明不可能。圖靈機的等價（「M1 與 M2 接受相同的語言嗎？」）則至少一樣難：拿任一台 M 去和一台什麼都不接受的固定機器比較，等價就塌縮成空性問題了。

還有一個值得誠實點名的進一步刺痛。圖靈機空性不只不可判定，它甚至不可識別——而它的姊妹「等價問題」更難，落在可識別與餘可識別兩類之外（這暗示了在單純的不可判定性之上，還有一座無窮的不可解性階梯）。「不可判定」不是只有一層的地下室底；它是一整座高塔的地板。第 2 篇的工具映射歸約，傳遞的不只是不可判定性，而是一般意義下的難度，這正是為何 PCP 或 A_TM 這樣單一個來源問題，能扳倒這麼多目標。機制從不改變——改變的只是目標問題的戲服，而方向永遠從已知很難的來源，指向你的新目標。

挑一個你懷疑不可判定的目標問題（例如「這個文法有歧義嗎？」、「L(M) 是空的嗎？」）。
選一個已知不可判定的來源——對字串／文法謎題用 PCP，對機器行為用 A_TM 或停機問題。
造一個可計算的翻譯器：從任一個來源實例，構造一個目標實例，使其「是／否」答案與來源一致。（這個構造本身必須總會停機——它只是改寫，從不去跑那台危險的機器。）
下結論：一個判定目標的判定器，透過翻譯器，就能判定來源。來源沒有判定器，所以目標也沒有。完成——不需要對角線論證。