可判定，意思是一個總會停下來的演算法
在三篇壞消息之後——上下文無關語言對交集與補集都不封閉，而幫浦引理又遞給你一份「證明 a^n b^n c^n 這類語言搆不著」的食譜——很容易覺得文法滑溜溜、難以推理。所以這裡有個讓人安心的反向砝碼。關於一個上下文無關文法的某些問題，不只是原則上有答案；它們可以被一個演算法回答，而那個演算法保證會停下來、印出正確的是或否，對每一個輸入、每一次都如此。這個性質有個名字，我們在這座階梯的餘下篇幅都會倚靠它：這個問題是可判定的。
要精確地把握「可判定」所要求的是什麼，因為這道差別在前方的圖靈機階梯裡關係重大。一個判定器是一個對每個輸入都會停下來的演算法——絕不無限迴圈——並給出正確答案。光是「答案為是時遲早會說是」還不夠；你還必須在有限時間內，於答案為否時也可靠地說否。本篇的兩個文法問題都跨過了這道門檻。稍後你會遇到跨不過的問題——在那裡，最好的可行程序也可能永遠跑下去，而你永遠無法確定它是快要回答了，還是只是卡住了。
空性：在文法上玩的標記遊戲
空性問題問的是：給定一個文法 G，語言 L(G) 是不是空的？換句話說，起始符號能不能推導出任何一個終端字串，還是說它是一台什麼都生不出來的死機器？你的第一直覺也許是開始生成字串、看會不會掉出來——但文法可以生成無限多個字串，所以「全部試一遍」永遠跑不完，而一個空文法更會永遠迴圈著去找一個根本不在的字串。我們需要一個會停的測試。關鍵的重新表述是：一個字串存在，當且僅當起始符號是可生成的（generating）——意思是它能抵達一個純由終端符號構成的字串。
於是我們不去追字串，而去獵捕可生成的符號，並且由下往上地做——這恰好是你在文法化簡時見過的不可生成符號清理的對偶。一旦你能證明某個變數推導得出某個終端字串，就把它標記為「可生成」。從顯而易見的勝利開始，往上傳播，直到再也標不出新東西為止。這是一個不動點計算：每一輪只會加上標記，而變數的個數有限，所以標記必然會停。當它停下來，你只要檢查起始符號有沒有被標記到。
- 播下種子。把每個終端標記為可生成（一個終端理所當然地產出它自己）。把任何擁有規則 A -> w 的變數 A 也標記起來——只要右邊的 w 完全由終端構成（包括 A -> epsilon）。
- 傳播。掃過所有規則。若某條規則 A -> X1 X2 ... Xk 右邊的每個符號都已被標記為可生成，那就也把 A 標記為可生成。只要有一個符號還沒被標記，這條規則此刻就幫不了 A。
- 重複掃描，直到某一整輪都加不出新標記為止。因為每一輪只增不減，而變數個數有限，所以這個不動點至多在（變數個數）輪之後就會抵達。
- 讀出答案。L(G) 非空，當且僅當起始符號 S 最終被標記為可生成。若 S 未被標記，則 L(G) 為空——這個文法一個字串都生不出來。
看它在一個迷你文法上運作。取 S -> A B | a，A -> A a，B -> b。播種：`a` 與 `b` 是終端；S 因為規則 S -> a（右邊全是終端）而立刻被標記，B 也因 B -> b 而被標記。下一輪掃描：A 只有規則 A -> A a，而 A 此刻尚未被標記，於是 A 將永遠不被標記——它永遠抵達不了純終端字串，只會不斷地再生自己。最終標記：S、B（以及那些終端）。既然 S 被標記了，L(G) 非空——而 S 確實推導得出 `a`。注意，A 是個無用的不可生成符號，這個測試順手就把它揭了出來。
成員資格：這個文法生得出這個字串嗎？
成員資格問題是日常的那一個：給定一個文法 G 與一個特定字串 w，w 是否在 L(G) 中？這正是編譯器對你的原始碼所提的問題——這個檔案，依照語言的文法，是不是一個合法的程式？第一個念頭是搜尋所有推導，在每一步都試遍每條規則。陷阱在於推導可以先長後縮（一個 epsilon 產生式或單位產生式，可以在一個句型崩縮之前先把它拉長），所以天真的搜尋可能永遠遊蕩、卻始終無法確定 w 不可推導。要得到一個真正的判定器，我們得把搜尋圈起來。
乾淨的修法，是先把 G 轉成喬姆斯基範式（CNF）——你在範式那一階梯見過它。在 CNF 中，每條規則要麼是 A -> BC（恰好兩個變數），要麼是 A -> a（單一終端），而 epsilon 只允許給起始符號用。回報是一個緊緻的長度界限：任何長度為 n 的非空字串，都恰由 2n - 1 次規則套用所推導出來——其中 n 次生出那 n 個終端，另外 n - 1 次把變數拆成成對。再也沒有「先長後縮」的遊蕩了。一旦推導有了固定長度，搜尋空間就是有限的，而有限搜尋總會停下來。光是這一點，就讓成員資格成為可判定的；下一個想法則讓它變快。
CYK：填滿一張子字串的三角表
那個界限化的暴力搜尋雖然正確，卻很慢。CYK 演算法（Cocke–Younger–Kasami）用 CNF 文法上的動態規劃取代它，對長度為 n 的字串，在 O(n^3) 時間內判定成員資格（還有一個來自文法大小的隱藏係數）。這個想法是由下往上的，就跟空性標記一樣：與其由上往下問「S 能造出整個字串嗎？」，不如從最小的零件把答案堆起來。對 w 的每一個子字串，算出能恰好推導出該子字串的變數集合。從單一字元開始，逐步長到越來越長的子字串，並重用你已經算過的答案。
- 長度為 1 的格子。對每個單一字元 w[i]，找出所有擁有規則 A -> w[i] 的變數 A。那個集合填入三角表的最底列——每個字元一格。
- 用拆分填較長的格子。要填一個長度為 L 的子字串的格子，就試遍所有把它拆成左半與右半的方式。若某條規則 A -> BC 中，B 能推導左半、C 能推導右半，就把 A 放進這格。
- 往表上爬。依長度遞增處理子字串，這樣你需要的每個拆分，在你下方都已經算好了。格子大約有 n^2 / 2 個，每個至多做 n 次拆分——O(n^3) 就是這麼來的。
- 下判定。字串 w 在 L(G) 中，當且僅當起始符號 S 出現在那唯一的頂格裡——也就是代表整個字串 w[1..n] 的那一格。
Grammar (Chomsky normal form):
S -> A B | B C A -> B A | a
B -> C C | b C -> A B | a
Decide membership of w = b a a b a (n = 5).
cell[i][L] = variables that derive the substring w[i..i+L-1].
Fill bottom (length 1) first, climb to the top (length 5).
position: 1=b 2=a 3=a 4=b 5=a
-------------------------------------------------------
L=1 {B} {A,C} {A,C} {B} {A,C}
L=2 {S,A} {B} {S,C} {S,A}
L=3 { } {B} {B}
L=4 { } {S,A,C}
L=5 {S,A,C} <-- whole string w[1..5]
S is in the top cell ==> b a a b a IS in L(G).
Each L>1 cell unions, over every split point k, the rules
A -> B C with B in the left sub-cell and C in the right one.注意這兩個演算法共享同一份 DNA：在有限結構上由下往上工作，讓答案不斷累積直到再也長不大，這就保證了終止。這正是為什麼這些問題是關於自動機與文法的可判定問題，而非僅僅可辨識。兩者也都能推廣：DFA 的空性是同一套「可達性」想法，而 CYK 是你在剖析那一階梯會再次研究的通用剖析器。誠實說，O(n^3) 對理論而言沒問題，但真正的編譯器會避開它——它們把文法限制在 LL 或 LR 類，以線性時間剖析，用通用性換取速度。CYK 是那個證明「對每一個上下文無關文法」成員資格都可判定的演算法。
好消息止步之處
別從兩場勝利過度推廣。可判定性是逐問題而定的，並非文法的一張通行證：我們剛剛解決了其成員資格與空性的這同一批上下文無關文法，關於它們的另一些問題卻被證明是不可判定的——沒有任何演算法能在所有輸入上回答它們，永遠不能。問「兩個文法是否生成同一個語言」，或「一個文法是否歧義」，或「它是否生成所有字串」，每一個都不可判定。本階梯的下一篇、也是最後一篇，將細細走過：為何歧義與等價，恰恰落在那條線的錯誤一側。
把這道界線記得清清楚楚，因為它會在這座階梯的餘下篇幅反覆出現。對上下文無關文法而言，成員資格與空性是可判定的；這是一項真實、有用、你可以據以建造的能力。但「上下文無關」不是一個能讓一切都好對付的咒語——而且就算可判定，也不代表廉價，因為像 O(n^3) 這樣的多項式，在巨大輸入上仍可能很慢。你開始看見的這個樣式——有些問題可判定、有些不可，沿著鋒利且可證明的界線劃分——正是整個計算理論的核心戲碼，在前方的階梯上等著你。