CFG 空語言問題（the CFG emptiness problem）
往喬姆斯基階層上爬一階，來到上下文無關文法。文法是一組改寫規則——像 S -> aSb 或 S -> ε（epsilon）——你從起始符號出發、套用它們來生出終端符號串。空語言問題問的是：給定的文法究竟能不能產生『任何』終端字串，還是每次嘗試都在抵達完成的字串前就熄火了？寫成語言，E_CFG = {G : G 是一個 CFG 且 G 的語言為空}。和 DFA 一樣，你不必測試無窮多次推導；你去分析文法的符號。
判定程序是一個標記過程，用來找出哪些符號是「可生成的」（最終能被改寫成『只含終端符號』的字串）。先把每個終端符號標記為可生成（一個終端本身就是一個完成的字串）。然後反覆：對任何規則 A -> X1 X2 ... Xk，若其整個右手邊都已被標記為可生成，就把左手邊的變數 A 也標記為可生成。持續掃過規則清單，直到某一整輪都標不出新東西為止。這一定會終止，因為要標記的符號只有有限多個。最後，文法的語言非空，若且唯若起始符號被標記為可生成。所以恰好在起始符號『沒有』被標記時，把 G 接受進 E_CFG。
因此 E_CFG 是『可判定』的。這延續了「階層的較低幾階在演算法上很溫馴」的故事：正如 DFA 空語言化約成有限狀態圖上的可達性，CFG 空語言化約成對文法符號的有限不動點標記。同一套「可生成／可達」的標記機制，正是文法化簡用來剔除無用符號的工具；空語言測試也是判定其他文法性質時的一塊積木。為後文誠實地對比一下：空語言對 CFG 可判定，但兩個 CFG 的『等價性』則不可判定。
文法 S -> AS, A -> aA 什麼都產生不出來：A 永遠只能變成 a...aA，從不會變成『只含終端』的字串，所以 A 不可生成；於是 S -> AS 也永遠無法完成，S 不可生成。標記結束時 S 未被標記，所以語言為空。相對地，S -> aS | a 能產生 a, aa, aaa, ...——S 經由規則 S -> a 被標記為可生成。
由下而上標記可生成的符號；語言非空，若且唯若起始符號被標記。
空語言對 CFG 可判定，但兩個 CFG 的『等價性』不可判定。別因為某個文法問題很溫馴，就假定全部都溫馴。