不可判定的文法問題（undecidable grammar problems）

上下文無關文法夠友善，某些關於它們的問題「確實」可判定：語言是否為空、某給定字串是否在語言中、語言是否有限。但再往前推一點，你就撞上一堵不可能的牆。關於文法的若干自然、出於實務動機的問題，根本沒有任何演算法。令人意外的是「是哪些」，而證明它的工具幾乎總是波斯特對應問題。

以下是不可判定文法問題的長廊。歧義：給定一個上下文無關文法，是否有某字串擁有兩棵不同的剖析樹？等價：兩個給定文法是否產生完全相同的語言？全域性：某文法是否產生其字母表上的每個字串（其語言是否為整個 Sigma-star）？交集為空：兩個給定的上下文無關語言是否共有任何字串？以及包含：一個上下文無關語言是否被另一個包含？這些每一個都不可判定。標準證明把 PCP 歸約到文法問題：由一盒骨牌，你建造一些文法，其推導編碼了可能的上方序列與下方序列，並佈置成使得「擁有兩棵剖析樹的字串、共有的字串、或缺失的字串」恰好對應到一次骨牌配對。既然判定配對是不可能的，判定該文法性質也就不可能。

兩個誠實的對照能讓人不迷糊。其一，有限自動機與正規語言的對應問題「確實」可判定：DFA 的等價、空集、甚至全域性，都有演算法，因為正規語言在補集與交集下封閉，而 DFA 可被最小化。上下文無關語言在交集或補集下「不」封閉，而正是這個封閉性失效，開啟了不可判定性的大門。其二，單一上下文無關文法的成員問題與空集問題仍可判定；跨界的是那些比較性的與「對所有字串」的問題——歧義、等價與全域性。這就是為何真實的編譯器工具一般無法直接檢查「我的文法是否無歧義」，而改為依賴受限、可判定的文法類別，如 LL 與 LR。