我們總能判定的問題

從嚇人的抽象回到習題裡的問題

前四篇活在稀薄的空氣裡：一個可判定語言，是某台判定器對每個輸入都能了結、從不掉進那個漏洞的語言；可判定性可拆成可辨識加上可餘辨識；而交織讓你平行地跑搜尋。全都對、全都重要——但你或許在想，你真正在乎的東西裡，有沒有哪個是可判定的。這一篇是故事裡令人安心的那一半。關於 DFA、NFA 與文法的一整櫃完全自然的問題，都是關於自動機的可判定問題，而我們能親手把判定器造出來。

首先是一個整階都倚賴的關鍵改寫。當我們問「這台 DFA 的語言是空的嗎？」，餵給判定器的輸入並不是一個字串——而是一台 DFA 的描述，以文字寫在紙帶上：它的狀態、字母表、轉移表、起始與接受狀態。我們約定一套固定、合理的辦法，把任何自動機或文法寫成一條有限的符號串（叫做編碼，以角括號寫出，所以 <D> 代表「被編碼的 DFA D」）。一旦一台機器或一個文法只是一條字串，關於它的問題就變成了一個語言：所有滿足該性質的編碼所成的集合。判定那個問題，就是判定在那個語言裡的成員資格。這一步——把「這個物件好不好？」變成「這條字串在不在這個語言裡？」——正是從抽象理論通往具體習題的橋。

DFA 的語言空不空？散個步就知道

從最乾淨的情況開始：DFA 的空性問題——給定 <D>，D 是不是一個字串都不接受？你的第一直覺也許是「試遍每個字串，看有沒有被接受的」，但字串有無窮多個，這場搜尋可能永遠繞圈，只給得出辨識器、永遠給不出判定器。訣竅是別再想字串，改把狀態圖當成一張樸素的有向圖。被 D 接受的字串，恰恰就是一條從起始狀態走到某個接受狀態的路徑。所以 D 接受某個東西，當且僅當在那張圖裡，至少有一個接受狀態從起始狀態可達。

在一張有限圖裡的可達性，是一個有限、必定終止的計算——它不過是一次廣度優先的淹沒填色。先標記起始狀態。然後反覆地，把每個從已標記狀態經一步轉移可達的狀態也標記起來，直到沒有新狀態被標記為止。因為狀態只有有限多個，這最多經過「狀態個數」這麼多輪就會停；它保證停機。停下來時，看那組被標記的狀態：若其中含有任何一個接受狀態，語言非空；若一個都沒有，語言為空。哪裡都沒有漏洞——搜尋被物件自身的大小所限，而這正是把辨識器變成判定器的那條紀律。

DECIDER E_DFA, on input <D>:
  1. mark the start state of D
  2. repeat until no new state gets marked this round:
        for each marked state q and each input symbol a:
             mark the state delta(q, a)
  3. if any ACCEPT state of D is marked:  reject   (language is non-empty)
     else:                                accept   (language is empty)

Why it always halts: D has finitely many states, so step 2
adds at least one new mark per round and runs out of states fast.

完整的空性判定器。它從不拿任何輸入去跑 D；它只是把標記沿著 D 的轉移圖淹過去，再檢查是否到達了某個接受狀態。

兩台自動機意見一致嗎？對稱差的把戲

接著是等價問題：給定兩台 DFA A 與 B，它們接受的語言完全相同嗎？這個感覺更難——要比較的字串有無窮多——但它能漂亮地折疊到你剛造好的空性判定器上，靠的只是正規語言的封閉性。關鍵想法是兩個語言的對稱差：恰好被 A 與 B 其中一台接受的那些字串所成的集合。兩個語言相等，恰恰當它們的對稱差為空——沒有任何一個字串能讓它們意見相左。

把對稱差寫成一條式子：（A 且非 B）或（非 A 且 B）。用白話說，就是 A 接受但 B 不接受的字串，連同 B 接受但 A 不接受的字串。
因為正規語言在補集（把接受狀態翻過來）、交集，以及聯集（正規那一階的乘積構造）之下都封閉，你可以機械化地造出單獨一台 DFA C，使它的語言恰好就是那個對稱差。每一步都是對有限機器的有限構造。
現在把上一節的空性判定器跑在 <C> 上。若對稱差為空，A 與 B 等價——接受。否則就有某個字串把它們分開——拒絕。

細品這是怎麼運作的：一個看來很難的問題（比較兩個無窮語言）變成了一個容易的問題（一張有限圖的接受集可不可達），靠的是把它歸約到一個我們已經解決過的問題。這正是你在後面幾階用來證明事情不可判定的那塊歸約肌肉——只不過這裡它流向友善的方向，把可判定性從空性帶到了等價性。成員資格與接受問題也一起搭便車：DFA 的接受問題——D 接不接受這個特定字串 w？——是其中最容易的。只要把 D 在 w 上一步步模擬就好。DFA 把 w 的每個符號恰好讀一次，w 一用完就停機，所以模擬總會在恰好「w 的長度」這麼多步之後終止。一個旋轉閘門無法繞圈。

文法也比照辦理

上面講的全是正規語言；同樣的精神能沿著喬姆斯基階層往上爬一層，抵達上下文無關文法。先談空性：給定一個 CFG G，它生不生成任何字串？同樣地，別去枚舉字串。改去判定哪些非終端符是可生成的——一個非終端符能產出一串終端符——做法是一場由下而上、與可達性淹沒填色相仿的標記。先標記每個有某條規則右側全是終端符（或為空）的非終端符。然後反覆地，標記任何擁有某條規則、其右側只含已標記的非終端符與終端符的非終端符。當沒有新東西被標記，就停。文法的語言非空，恰恰當起始符號最終被標記。非終端符只有有限多個，意味著這會停機——所以 CFG 的空性是可判定的。

成員資格才是壓軸。給定一個 CFG G 與一個字串 w，G 能不能導出 w？最天真的想法——試遍每一條推導——可能永遠跑下去，因為帶有 epsilon 產生式或迴圈的文法，能造出時而膨脹、時而縮小、毫無界限的推導，所以「就搜推導吧」又只是一個辨識器。修補的辦法是先把 G 轉成喬姆斯基正規形式，其中每條規則要嘛是 A -> BC（兩個非終端符），要嘛是 A -> a（一個終端符）。在那種形式下，一個長度為 n 的字串，其推導有著嚴格受限的形狀：恰好 2n - 1 次規則套用。受限的搜尋就是可判定的搜尋，而 CYK 演算法以動態規劃高效地辦到，對固定文法在 O(n^3) 時間內判定成員資格。

CYK on G (in Chomsky normal form) and w = a1 a2 ... an:

  table[i][i] = { A : G has rule A -> a_i }          (length-1 spans)
  for span length L = 2 .. n:
    for each start i, let j = i + L - 1:
      for each split point k in i .. j-1:
        if A -> BC,  B in table[i][k],  C in table[k+1][j]:
          add A to table[i][j]

  ACCEPT if the start symbol S is in table[1][n], else REJECT.

The table has about n^2 cells, each filled by scanning n splits: O(n^3).

CYK 成員判定器：從長度為 1 的區段往外，逐步建出哪些非終端符能產出 w 的每個子字串。起始符號蓋住整個字串，就代表 w 在語言裡。

簡單答案在哪裡戛然而止

若你帶著「關於機器的每個問題都可判定」走開，那就讀錯了。這條界線很銳利，而且很要緊。對 DFA 而言，幾乎一切都可判定——空性、等價、成員資格、有限性——因為一台 DFA 的行為被一張你能窮盡分析的有限圖完整刻畫。往上爬一階到上下文無關文法，可判定性就開始磨損了：成員資格與空性仍可判定（你剛看過為什麼），但兩個 CFG 的等價卻不可判定，問一個 CFG 是否有歧義也不可判定。同一個對 DFA 易如反掌的等價問題，到了文法身上變成了不可能。能力與不可判定性是一起攀升的。

所以這就是這一階靜默的勝利。你在圖靈機這段旅程的起點，是害怕那個漏洞——一台可能永遠跑下去、永不作答的機器——而你在終點手裡握著一把問題，漏洞在那裡根本不會打開，因為每場搜尋都被「被分析物件的有限性」圍了起來。這就是「可判定」一路以來的意思，被具體化了：不只是原則上答案存在，而是單獨一道程序對每一個輸入吐出正確的是或不是，而且總會停下。把這幅圖帶著走，因為下一階要給你看的，正是第一批真正把它打破的問題。