上下文無關語言空性與有限性的可判定性（emptiness and finiteness）

關於一個文法的兩個基本問題，每一次都能用演算法回答。空性問題問：這個上下文無關文法到底產不產生「任何」字串，還是它的語言為空？有限性問題問：它只產生有限多個字串，還是無限多個？兩者都是「可判定的」——存在一個程序，總會停機並給出正確的「是」或「否」。你不必煩惱；直接算就行。

空性問題由一個簡單的標記過程解決，這個過程找出「會產生（generating）」的變數。先把每個終端符號標記為「會產生」。然後反覆地：只要某條規則 A ->（右側）的右側符號全都已被標記，就把變數 A 標記為「會產生」。一直做到沒有新東西被標記為止——這會停止，因為變數只有有限多個。語言「非空」恰好當「起始符號」最後被標記（它能到達一個全是終端符號的字串）；語言為空則當它沒被標記。有限性則在修剪過的文法上判定（移除無用符號後）：建一張相依圖，若 A 的某條規則用到 B 就讓 A 指向 B，然後檢查是否有一個「真的能從起始到達、且真的能產出終端符號」的「環（cycle）」。一個可用的環表示某變數可以被重新進入以造出愈來愈長的字串，所以語言「無限」；沒有這種環就「有限」。

這些可判定的問題是文法工具的實用骨幹——剖析器產生器能警告你某個非終端符號什麼都不產生（多半是個錯誤），或某個子語言意外地無限。它們也標出分界線：空性、有限性與成員問題是上下文無關語言「可判定的三人組」，而越過它們一步，就是連這個樸素模型也逃不掉的不可判定問題（等價、歧義、通用性）。