上下文無關文法等價性的不可判定性（undecidability of equivalence）
這裡是尾巴上的第一根刺。你能判定單一文法的語言是否為空、是否有限、是否含某個字串。但問一個看似無害的比較——這「兩個」上下文無關文法是否產生「完全相同」的語言？——卻「沒有」任何演算法總能正確回答。上下文無關文法的等價問題是「不可判定的」（undecidable）。這是一道硬牆，不是等更快的電腦或更聰明的把戲就能解決的事。
這裡「不可判定」的意思很嚴格：對每一個聲稱能比較任何兩個文法的擬議程序，都存在某些文法，使它要嘛給出錯誤答案、要嘛永遠跑下去而不回答。不可能存在通用的判定器。這個事實由一個歸約（在理論的不可判定性部分推導，不在此處）證明，從一個已知不可判定的問題出發，例如波斯特對應問題（Post correspondence problem, PCP）：由任意一個 PCP 實例，可建出兩個文法，它們等價「若且唯若」該 PCP 實例「無解」。既然判定 PCP 不可能，判定文法等價也必不可能。
這個對比正是重點。對正規語言，等價「是」可判定的——把兩台 DFA 都最小化再比較，或取對稱差再測空性。讓上下文無關文法能計數與巢狀的那份額外能力，正是讓比較它們變得不可判定的那份能力。連這個樸素、日常的模型——程式語言背後的文法——都已經一頭撞上不可判定性。（注意：「確定型」上下文無關語言的等價「是」可判定的，這是一個深刻而著名的結果，但一般的上下文無關情形並非如此。）
兩個文法可能用全然不同的規則產生同一個語言——一個寫 S -> a S b | ε，另一個透過額外的中間變數寫出相同的字串。一般而言你無法判定它們的語言是否一致。相比之下，對兩台 DFA，你只要把兩者都最小化、再看最小機器是否相符即可。
對 DFA 可判定、對 CFG 不可判定：同一個問題，相反的判決。
等價對「一般」上下文無關文法不可判定；「確定型」CFL 的特例「是」可判定的（一個著名定理）。別把確定型的結果推廣到所有 CFG。