為什麼要問一個語言類在哪些運算下封閉
你抵達這一階梯時，對上下文無關語言已經相當熟稔：你能為 a^n b^n 寫出像 S → a S b 的文法，也認得與之匹配的機器——一台下推自動機，一台帶著一疊盤子的有限狀態控制器，而你永遠只能碰最上面那個盤子。接下來一個自然的問題不是關於任何單一語言，而是結構性的：如果我拿兩個上下文無關語言把它們組合起來——首尾相黏、彼此重疊、反覆重複——結果還是上下文無關的嗎？問哪些運算能讓你留在類之內，就是問它的封閉性質。
封閉性事實不是冷知識，而是工具。正如你曾把正規語言的補集封閉性當捷徑——靠把較簡單的正規片段組裝起來，來證明一個複雜語言是正規的——CFL 的封閉性事實讓你不必親手寫出文法，就能推理一個龐大的語言。而封閉性的失效是更鋒利的工具：知道上下文無關語言在交集下不封閉，正是讓我們得以鎖定一個恰好落在觸及範圍之外的語言（如 a^n b^n c^n）的關鍵。我們會雙向使用封閉性：拿來建造，也拿來證明不可能。
三個能留在類內的運算：聯集、串接、星號
好消息很慷慨，而且證明全是純粹的文法管線工程。上下文無關語言在聯集、串接與 Kleene 星號之下封閉。每一次的訣竅都是：拿各片段的文法，把它們的變數改名分開以免互相干擾，再加上一條新的起始規則把它們接起來。因為每條規則的左側仍只有單一變數，結果就是一個道地的上下文無關文法。
- 聯集 (L1 ∪ L2)：取兩個文法，起始符號分別為 S1 與 S2（變數已改名分開），再加一個全新的起始符號 S 與規則 S → S1 | S2。一次推導只會選一邊；生成的語言恰好是 L1 ∪ L2。
- 串接 (L1 · L2)：同樣先改名分開，加上 S → S1 S2。每個生成的字串都是 L1 的一段，後面緊接 L2 的一段——正是串接。
- Kleene 星號 (L1*)：加上 S → S1 S | epsilon，其中 epsilon 是空字串。S → epsilon 這一支提供零份副本；遞迴那一支每次再黏上一份 L1 的副本，從而得到任意多次的重複。
Say L1 = { a^n b^n } with grammar A -> a A b | epsilon
L2 = { c^m } with grammar B -> c B | epsilon
Union S -> A | B
Concat S -> A B
Star of L1 S -> A S | epsilon
Every new rule still has ONE variable on the left,
so the combined grammar is still context-free.兩個會逃出去的運算：交集與補集
現在來個急轉彎。上下文無關語言在交集下不封閉，在補集下也不封閉。這和正規語言的世界是個真正的決裂——在那裡交集與補集兩者都安全。原因可以直接追溯到機器：一台下推自動機只有一疊堆疊。把兩個 CFL 取交集，精神上等於要求兩疊各自獨立的堆疊同時運轉——一疊用來執行每個語言的約束——而單一疊堆疊無法同時服務兩個無界的計數器。
這裡是交集那個著名的反例。令 L1 = { a^i b^i c^j：i, j ≥ 0 }——a 與 b 數量相等，後面接任意多個 c。它是上下文無關的：一疊堆疊把 a 對著 b 計數，c 則直接放行。令 L2 = { a^i b^j c^j：i, j ≥ 0 }——任意多個 a，後面接數量相等的 b 與 c。用同樣的招式也是上下文無關的，這次把 b 對著 c 配對。每個語言都只管一組配對，這是單一疊堆疊能應付的。但它們的交集卻同時逼出兩組配對。
把它們取交集，你得到 L1 ∩ L2 = { a^n b^n c^n：n ≥ 0 }——三個字母按順序、數量全部相等。這個語言正是經典的 可被證明不是上下文無關的 a^n b^n c^n（你下一篇就會用上下文無關幫浦引理證明它）。於是兩個上下文無關語言取交集後，產生了類之外的東西：交集讓你逃得出去，因此 CFL 在交集下不封閉。補集則靠一個集合恆等式，作為免費的推論隨之而來。
救援：與正規語言取交集
有一個漂亮的例外，你絕不能把它和上面混為一談。雖然 CFL ∩ CFL 會逃出去，但一個上下文無關語言與一個正規語言的交集永遠是上下文無關的。這個不對稱正是重點：把一個 CFL 與另一個同樣苛刻的 CFL 取交集需要第二疊堆疊，但把它與一個區區正規語言取交集只需要有限的額外記憶——而下推自動機本來就有用不完的有限狀態控制。
這個構造是一台乘積機。取一台辨識該上下文無關語言的 PDA P，以及一台辨識該正規語言的 DFA D。建一台新的 PDA，讓它在同一份輸入上把 P 與 D 並排跑：它的狀態是一個配對（P 的狀態、D 的狀態），它原封不動地保留 P 那一疊堆疊，且只在兩個分量都接受時才接受。因為 D 只貢獻有限多個狀態，乘積機仍有有限控制、仍只有一疊堆疊——所以它仍是一台合法的 PDA，而 PDA 恰好辨識上下文無關語言。
這個救援是接下來不可能性證明的主力。假設有人遞給你一個糾結的語言，你懷疑它不是上下文無關的，但直接進攻很麻煩。常常你可以把它與一個精心挑選的正規語言取交集，剝掉雜訊，露出像 a^n b^n c^n 這樣乾淨的核心。如果原語言是上下文無關的，那交集（正由這條定理）也必須是上下文無關的——所以若核心被證明不是上下文無關的，原語言也不可能是。這個逆否的招式，正是用封閉性證明某語言不是上下文無關的脊梁。
這個不對稱真正在告訴你的事
退後一步看整張表，因為這個模式本身就是教訓。正規語言在一切運算下封閉——聯集、串接、星號、交集，以及補集——因為一台 DFA 的有限記憶與另一台 DFA 的有限記憶可以自由地組合。上下文無關語言保住了聯集、串接與星號，卻失去交集與補集。分界線在於無界記憶：一疊堆疊可以為聯集而複製（你一次只需要一疊），卻不能為交集而加倍（你會同時需要兩疊）。封閉性表，就是這台機器記憶體的指紋。
離開前兩句誠實的提醒。第一，別把補集的失效讀過頭：它並不是說每個 CFL 的補集都不是上下文無關的——許多補集恰好是上下文無關的；定理只說這個類不封閉，也就是至少存在一個 CFL，其補集逃了出去。第二，一個更窄的家族表現得更好：確定型上下文無關語言——也就是確定型 PDA 所辨識的那些——確實在補集下封閉，這是確定性在這裡買到的少數真本事之一。但回想本階梯的一個關鍵事實：確定型與非確定型 PDA*不*等價（不像有限自動機，那裡兩者等價），所以確定型 CFL 是一個嚴格的、行為更乖巧的子集，並非整個類。
這條路要通往哪裡：你現在握有一份對上下文無關之邊界的精確感覺，以及一個演練過的目標——a^n b^n c^n——就坐在邊界之外。下一篇將鍛造那件證明一個語言越過該邊界的工具，也就是上下文無關幫浦引理，它那兩段被幫浦的片段與剖析樹的來歷，會讓無界計數的論證變得嚴謹。第三篇把它變成一份可重複的食譜；第四、五篇則接著問：關於 CFL 我們還能判定什麼（成員資格與空性，可以）、又不能判定什麼（等價與歧義，不行）。封閉性是地圖；幫浦引理是證明。