一條畫過文法問題的分界線
上一篇把你留在堅實的地面上：給定一個上下文無關文法，你永遠能用演算法回答兩個問題。它生成這個特定字串嗎？只要文法先化為喬姆斯基範式，CYK 演算法就能在 O(n^3) 時間內給出是或否——這就是成員資格可判定。它到底生不生成任何東西？標出哪些變數能抵達某個終端字串，往上傳遞，再檢查起始符號——這就是空性可判定。兩者都不只是「原則上可解」；它們有真正會停機的程序，你今天下午就能把它寫成程式。
現在來個震撼。你對文法可能提出的兩個最自然的問題，竟然完全沒有演算法可解——不是慢的演算法，不是聰明的演算法，是一個都沒有，永遠沒有。給定兩個上下文無關文法，它們生成的語言完全一樣嗎？這是等價性，它是不可判定的。給定一個文法，它是具歧義的嗎——是否某個字串有兩棵不同的剖析樹？這是歧義性，同樣不可判定。可判定與不可判定之間的分界線，正好穿過上下文無關文法理論的正中央。
麻煩的種子：波斯特對應問題
文法的不可判定性從何而來？它是經由一次翻譯，從一個為字串量身打造的不可判定問題輸入進來的：波斯特對應問題，簡稱 PCP。想像一組有限的骨牌，每張上面都印著一條上方字串和一條下方字串，例如 [a / ab]、[b / a]、[aba / b]。你可以隨意重複使用每張骨牌，任意排序。謎題是：你能排出一個非空的骨牌序列，使得把所有上方串接起來讀，和把所有下方串接起來讀，得到完全相同的字串嗎？
Dominoes: 1:[ a / ab ] 2:[ b / a ] 3:[ aba / b ] Try sequence 3 , 2 , 3 , 1 : tops : aba b aba a = abababa bottoms : b a b ab = babbab ... (mismatch) Finding ANY matching sequence is the puzzle. PCP asks: does a match exist for THIS set of dominoes? That yes/no question has NO general algorithm.
PCP 看起來是個無辜的文字遊戲，然而判定一組給定骨牌是否有任何匹配卻是不可判定的——其證明是把停機問題歸約到它，使得一台假想的 PCP 解算器會偷偷地把停機問題也解掉。這正是你先前遇過的機制：一次歸約是一個翻譯者，把一個問題轉成另一個問題，而如果來源問題沒有演算法，目標問題也不可能有。PCP 是一座橋，把原始的圖靈機不可判定性帶進字串與串接的世界——而文法恰好就住在那個世界裡。
從骨牌到文法：建造兩個「匹配」的語言
這裡有個把 PCP 偷渡進文法理論的優雅花招。給定任意一組骨牌，你能機械地寫下兩個上下文無關文法。一個文法，稱它 G-上，生成所有形如「一串骨牌索引」後面接「對應的上方字串串接起來、反轉並加上標記」的字串。另一個 G-下，用下方字串做同樣的事。這個構造是照本宣科的——每張骨牌變成幾條產生規則——而關鍵在於，每一邊確實都是上下文無關的，因為把一個序列與它自己的反轉相配對，不過就是單一疊堆疊能處理的回文式堆疊。
現在看這兩個語言相撞。一個字串能同時被兩個文法生成——也就是落在它們的交集裡——恰恰當它的索引序列使上方的串接等於下方的串接時。換句話說，語言 L(G-上) 與 L(G-下) 共享一個字串，若且唯若該骨牌組存在一個 PCP 匹配。PCP 的整個不可判定性，已經被純粹用兩個上下文無關文法、以及它們的語言是否重疊重新表達出來了。
這正是本階梯稍早封閉性那一課的回報：上下文無關語言在交集下不封閉，而這裡正是那道缺口被武器化的地方。如果你擁有一個演算法能測試兩個 CFG 是否共享某字串，你就能拿它去跑 G-上與 G-下，從而判定 PCP——而那是不可能的。所以這樣的演算法並不存在。從這一顆種子，等價性、歧義性以及幾個表親問題的不可判定性，全都靠後續幾個簡短的歸約抽芽長出。
為什麼等價性與全集性會倒下
歸約的方向很重要，所以要細心追蹤它。一次歸約只有在從一個已知困難的問題、跑向目標時，才能證明目標問題困難。我們手上有個已知困難的字串問題（兩個 CFG 是否共享某字串？），而我們想給等價性定罪。等價性問的是：L(G1) = L(G2) 嗎？事實證明，與它密切相關的全集性問題——一個文法是否生成其字母表上的所有字串，亦即 L(G) = Sigma*（每一個可能字串的集合）——本身就是不可判定的，而等價性繼承了這個判決，因為問「L(G) 是不是全部？」不過就是問「L(G) 是否等價於一個生成 Sigma* 的文法？」。
全集性（從而等價性）之所以無望，深層原因要回扣到補集。辨認一個文法是否生成一切，實際上就是辨認它語言的補集是否為空。但 CFL 在補集下不封閉，所以一個 CFL 的補集未必是上下文無關的——你也無法直接對它跑那個可判定的空性測試，因為可能根本沒有文法可跑。那件曾拯救成員資格與空性的工具（把它變成文法，再標出可達符號）在這裡用不上，而且沒有替代品。
為什麼歧義性也不可判定
歧義性靠同一顆 PCP 種子被定罪，外加一個巧妙的轉折。回想一個文法是具歧義的，若某個單一字串有兩棵不同的剖析樹（兩種結構上不同的推導方式）。再次拿那個 PCP 構造：把 G-上 與 G-下 合併成一個文法，配上新的起始規則 S → S-上 | S-下。一個同時屬於兩個語言的字串——也就是一個 PCP 匹配——現在可以用兩種方式推導：一次走 S-上 那一支，一次走 S-下 那一支。那就是同一個字串的兩棵不同剖析樹。因此這個合併文法是具歧義的，若且唯若存在一個 PCP 匹配。
- 從任意一組骨牌出發——一個不可判定的波斯特對應問題的實例。
- 機械地建出 G-上 與 G-下，這兩個上下文無關文法，它們共享的字串恰好就是 PCP 匹配。
- 把它們黏在一個起始符號底下：S → S-上 | S-下。這個單一文法完全由一個有限的、照本宣科的程序建成。
- 觀察：這個文法具歧義，恰好當某個字串以兩種方式都能生成時——也就是恰好當該骨牌組有一個 PCP 匹配時。
- 結論：一台歧義測試器會判定 PCP，而那是不可能的。因此測試歧義性是不可判定的。
要小心這個結論宣稱了什麼、又沒宣稱什麼。它並不是說每個文法都難以審視——對任何特定文法，你大有可能親手抓出一個有歧義的字串，或靠論證證明它無歧義。不可判定性說的是：缺少一個對所有文法都管用的單一演算法。它也並不是說歧義性本身沒有意義：一個相關的概念，本質歧義語言，指的是每一個文法都具歧義的語言——那是語言的性質，不是某個文法的性質，而這類語言存在本身，是另一個同樣微妙的事實。
本階梯收尾時的地圖
退後一步，環視本階梯所繪製的整片地景。封閉性畫出了這個類的地圖；幫浦引理證明了哪些語言坐在它之外；CYK 與空性測試展示了哪些問題你能回答；而現在你精確地看見了哪些問題你不能回答。不可判定的文法問題這份清單，不只有等價性、歧義性與全集性——還包括一個 CFL 是否為正規、兩個 CFL 的交集是否為空，以及一個 CFL 是否包含另一個。那顆 PCP 種子與少數幾個歸約，幾乎可以解釋它們全部。
值得最後一次與正規世界對照，因為這個對照本身就是整個故事。對有限自動機，等價性是可判定的：把兩台 DFA 都最小化再比對，或測試它們的對稱差是否為空——這就是 DFA 那個可判定的等價性問題。從有限記憶躍升到一疊無界堆疊，正是那一躍把等價性從可判定變成不可判定。交集與補集下的封閉性失效，原來並非什麼稀奇玩意；它是個早期警訊，預告判定能力在這裡也會裂開。
這把你留在何處：手握一幅真正完整的上下文無關層級全圖。你認識它的文法與它的下推機器、它能表達之物的邊界，以及現在這道——它讓你能對自己計算什麼的——鋒利刃口。把一個大觀念帶著走：不可判定性不是個需要動用圖靈機全副力量才能召喚的遠方怪物；它早已端坐在一份有限的文法規則清單之內。當你攀進上方的可判定性與複雜度階梯，你會在它們的原生棲地遇見停機問題與驅動這些證明的歸約，並認出老朋友。