上下文無關語言成員問題的可判定性（decidability of membership）

給定一個上下文無關文法 G 與一個字串 w，演算法是否總能判定 G 是否產生 w——w 是否屬於該語言？是的。這是上下文無關語言的成員問題（或稱字問題），而它是「可判定的」（decidable）：存在一個程序，對每一個文法與每一個輸入都會停機並正確回答「是」或「否」。更棒的是，它在多項式時間內完成，所以剖析程式語言與自然語言文法都有穩固的演算法基礎。

標準方法是 CYK 演算法（Cocke-Younger-Kasami）。先把 G 轉成喬姆斯基正規形式（Chomsky normal form），其中每條規則是 A -> B C（兩個變數）或 A -> a（一個終端符號）。然後用動態規劃填一張三角形的表。最底列為 w 的每個單一符號記錄哪些變數能推導它。每個較高的格子（涵蓋 w 的一段子字串）記錄哪些變數能藉由把該子字串切成兩段相鄰部分、再用二元規則組合下方格子裡的變數，來推導出它。填完表後，w 屬於語言「恰好」當「起始符號」出現在涵蓋整個字串的頂端格子裡。對長度為 n 的字串，這大約花 O(n^3) 時間。

為什麼這要緊？它顯示上下文無關文法是真正可用的：編譯器能判定你的原始碼是否剖析得過，而答案有保證。它和接下來的壞消息之間的對比，正是這個領域的全部戲劇性——成員問題容易又可判定，然而關於「同一批」文法的其他問題（兩個文法等價嗎？某文法歧義嗎？）卻是不可判定的。可判定性是一題一題地論斷，不是模型的一概而論的性質。