上下文無關語言是否等於 Sigma-星的不可判定性（universality）
/ Sigma: SIG-muh /
這裡又有一個聽起來幾乎瑣碎、卻不可能判定的問題。給定字母表 Σ（Sigma）上的一個上下文無關文法，它是否產生「絕對每一個」字串——它的語言是否等於 Σ*（Sigma-星），也就是字母表上所有字串的集合？這是「通用性」（universality）問題，對上下文無關語言而言它是「不可判定的」。沒有演算法能總是正確回答「是，它什麼都產生」或「否，它漏了某些東西」。
為什麼「什麼都不漏」這麼難，而空性（什麼都不產生）卻容易？空性問的是是否「存在」一個被產生的字串，這由一個有限的標記過程就能了結。通用性問的是是否「所有」字串都被產生，這暗地裡逼你去推理每一個「沒」被產生的字串——也就是語言的「補集」。而上下文無關語言對補集不封閉，所以補集甚至可能不是上下文無關；那些友善的工具（CYK、空性檢查）就不再適用了。這個不可能性靠編碼圖靈機的停機計算來證明：可建出一個文法，其語言恰好是那些「不」是合法接受計算歷史的字串，於是該文法產生 Σ*「若且唯若」該機器什麼都不接受——而這個問題已知是不可判定的。
這個問題是好幾個相關不可判定問題的樞紐：兩個上下文無關語言是否交集為空、一個上下文無關語言是否等於某個給定的正規語言、以及一個上下文無關語言是否其實是正規的，全都不可判定，而其中數個能歸約到通用性或從它歸約而來。要記住的模式：對上下文無關語言，「它是否產生「某些」東西」可判定，但「它是否產生「全部」」不可判定——從存在跨到通用，正是跨入不可判定性的那一步。
對 DFA，通用性很容易：取補集（翻轉接受狀態）再測空性。對上下文無關文法這個把戲失敗，因為補集可能離開家族。所以一般而言你無法判定一個 CFG 是否產生整個 Σ*——也無法判定兩個 CFL 是否相交、或某個 CFL 是否為正規語言；這些全是不可判定的。
存在性（空性）可判定；通用性（產生全部）不可判定——失去的工具正是補集。
與正規語言對照，其通用性「是」可判定的（取補集再測空性）。CFL 的情形之所以失敗，正是因為 CFL 對補集不封閉。