從工具到食譜
在上一篇你遇到了上下文無關語言的幫浦引理，也看見了它的來歷：取上下文無關語言中任何夠長的字串，看它的剖析樹，由於文法只有有限多個變數，沿著某條夠長的「根到葉」路徑，某個變數必定重複。那個重複的變數就是一個你可以再跑一次（向上幫浦）或跳過（向下幫浦）的迴圈。它誠實的回報是同時對兩段被幫浦的片段給出保證。本篇不是新理論；它是揮舞那項保證、用以證明目標語言不是上下文無關的手藝。
回顧精確的敘述，好讓食譜有所依憑。若 L 是上下文無關的，存在一個常數 p（即 幫浦長度），使得 L 中每個長度至少為 p 的字串 s 都能切成五段，s = u v x y z，並滿足三個條件：(1) 兩段被幫浦的片段不同時為空，記為 |v y| 至少為 1；(2) 中間那束保持短小，|v x y| 至多為 p；(3) 對每個 i 大於或等於 0，被幫浦後的字串 u v^i x y^i z 仍屬於 L。與正規語言幫浦引理最關鍵的差別在於：v 與 y 兩者都被幫浦，且次數相同——是兩扇窗一起同步開合，而不是一扇。
把證明當成對抗對手的賽局
跑一個「非上下文無關」證明最乾淨的方式，就是把它想成一場兩人賽局，正如你對正規語言所做的那樣——只是棋子更多。你想證明 L 不是上下文無關的；對手堅持它是。引理裡的量詞決定了誰挑什麼。引理說「存在」的，由對手選（好讓你為難）；引理說「對所有」的，由你選（好揭出矛盾）。只要你贏下這場賽局的一局，就證明了 L 不是上下文無關的。
- 對手指定一個幫浦長度 p（某個正整數）。你看不到它的具體值，所以你的論證必須對每一個 p 都成立。
- 你挑一個特定的、屬於 L 且長度至少為 p 的字串 s——而且要挑得聰明，使得無論它之後被如何切割，幫浦都必然弄壞它。這個選擇正是整個證明的精髓。
- 對手把你的 s 切成 u v x y z，遵守 |v y| 至少為 1 與 |v x y| 至多為 p，但在這之外可以盡其所能地刁難你。
- 你挑一個幫浦次數 i，並證明被幫浦後的字串 u v^i x y^i z 不屬於 L。通常 i = 2（向上）或 i = 0（向下）就夠了。既然這與條件 (3) 矛盾，L 就不可能是上下文無關的。
讓第 4 步變得可行的唯一訣竅，就是條件 (2)：|v x y| 至多為 p。那個短窗保證意味著被幫浦的材料 v 與 y 合起來最多橫跨長度為 p 的一段，所以它們無法觸及整個字串。如果你把 s 造成三個或更多個又長又等長的區塊，那麼窗口 v x y 就太窄、無法一次碰到全部——這正是你要楔進去的縫。這跟支撐引理證明的鴿籠原理是同一個換了裝的把戲：空間太少，要覆蓋的東西太多。
經典範例：a^n b^n c^n 不是上下文無關
本階梯的招牌反例就是 a^n b^n c^n = { a^n b^n c^n : n 至少為 0 }——等量的一串 a、再一串 b、再一串 c。必須同時成立兩組配對（a 的個數 = b 的個數，且 b 的個數 = c 的個數），而這對單一一座堆疊來說，多了一個約束。我們來玩這場賽局。對手給出 p；你選 s = a^p b^p c^p，它的長度是 3p，舒舒服服地至少為 p，且屬於 L。現在對手必須把它切成 u v x y z，且窗口 v x y 的長度至多為 p。
致命一擊在此。由於窗口 v x y 長度至多為 p，它無法從 a 區塊一路伸進 c 區塊——中間卡著 p 個 b，所以 v 與 y 合起來最多碰到三種字母中的兩種。無論對手怎麼做，總有某個字母完全沒被任一段被幫浦的片段碰到。向上幫浦到 i = 2：被碰到的字母個數增加，而沒被碰到的那個維持不變，於是三者的個數再也無法相等，u v^2 x y^2 z 便掉出 L 之外。矛盾。所以 a^n b^n c^n 不是上下文無關的。
s = a a a ... a b b b ... b c c c ... c (p of each, length 3p)
\---- p ----/ \---- p ----/ \---- p ----/
The window v x y has length <= p, so it fits inside AT MOST
two neighbouring blocks -- it can never span a...c:
case A: v x y lies in the a's (and/or b's) -> c-count never changes
case B: v x y lies in the b's (and/or c's) -> a-count never changes
(it can never reach both an a and a c: the p b's block the way)
Pump i = 2: some letters grow, the untouched letter does not
=> counts no longer all equal => NOT in L. Contradiction.留意它與上一階梯的對比。a^n b^n 是上下文無關的——一座堆疊能為 a 推入、為 b 彈出。但 a^n b^n c^n 需要驗證兩個彼此獨立的計數，而一座為了配 b 已被掏空的堆疊，再也沒有東西可以拿來核對 c。那多出來的單一約束，正是從上下文無關往上、跨到需要更強機器的那一跳（一台下推自動機，連同它那一疊盤子，並不夠；你會想要一台圖靈機）。
兩記殺招：與正規語言交集
有時候，直接幫浦原始的目標語言很麻煩，但本階梯第一篇的一個封閉性事實提供了更乾淨的路徑。上下文無關語言對交集不封閉——兩個 CFL 的交集可能不是上下文無關的——然而它們對「與正規語言交集」封閉。這個不對稱性就是一件武器。若 L 是上下文無關的，那麼 L 與任意正規語言 R 的交集仍然是上下文無關的。所以只要你能挑出一個 R，把 L 過濾成一個你早已知道不是上下文無關的語言（比如 a^n b^n c^n），你就能不直接幫浦 L 而導出矛盾。
一個演練範例：令 L = { w : w 中 a、b、c 的個數相等 }。直接幫浦它很彆扭，因為字母可以任意打散排列。改而與正規語言 R = a* b* c*（一個正規表示式，要求字母按此順序出現）取交集。那麼 L 與 R 的交集恰好就是 { a^n b^n c^n }，而我們剛證明它不是上下文無關的。若 L 是上下文無關的，L 與 R 的交集也會是——矛盾。因此 L 不是上下文無關的。我們透過正規濾鏡借來了一個已知的非 CFL。
當幫浦太弱時：Ogden 引理
普通的幫浦引理必要但不充分，更糟的是，它有時甚至鈍到無法反駁一個如假包換的非 CFL。麻煩在於對手可以把 v x y 放在任何短處，有時就能把幫浦藏進一段無害的填充區裡，幫浦它也造不成傷害。對這類語言，基本引理根本無法逼出矛盾——儘管那語言確實不是上下文無關的。
Ogden 引理是修補這點的更鋒利工具。在切割之前，你可以把 s 中至少 p 個位置標記為「被指定」（把它們想成被螢光筆畫出來的字母）。引理接著保證幫浦能瞄準這些標記：在五段之中，窗口 v x y 至多含 p 個被標記的位置，而關鍵在於 v 與 y 合起來至少含一個被標記的位置。藉由選擇要標哪些字母，你把對手的幫浦引導到正好「幫浦必定弄壞字串」的那片區域——奪走它的藏身處。普通的幫浦引理，不過就是把每個位置都標記的 Ogden 引理。
感受一下它咬住哪裡：語言 { a^i b^j c^k : i, j, k 至少為 0 且（i = 0 或 j = k）} 不是上下文無關的，然而普通的幫浦引理證不出來，因為對手總能退進 i = 0 那一支、在那裡無害地幫浦。用 Ogden 引理把 b 與 c 標起來，幫浦就被逼進 j 對 k 的配對裡，破壞它的平衡就產出一個語言之外的字串。其機制——一條夠長的「根到葉」剖析樹路徑上某個重複的變數——完全相同；Ogden 引理只是去數被標記的葉子，把方向盤交到你手上。
陷阱，以及這把你帶到了哪裡
出發前三句誠實的告誡。第一，這個引理只能反駁——通過它什麼也確認不了，所以絕不要寫「這個字串能幫浦，所以語言是上下文無關的」。第二，你選字串 s，但對手選切割方式；若你的證明偷偷假設了一個方便的切割（譬如「v 全是 a」），它就破了——你必須擊敗每一種合法的切割。第三，長度要緊：s 的長度必須至少為 p，而你的論證必須對一個未知的 p 都成立，所以你要把 s 寫成 p 的函數（像 a^p b^p c^p），絕不寫死成一個固定數字。
退後一步，把這件事放上地圖。你現在能證明一個語言坐落在上下文無關類之外——這是高一層樓的、用正規語言幫浦引理證明非正規性的對應物。食譜形狀相同（對手賽局），引擎是同一個想法（鴿籠逼出重複），而封閉性工具箱則在每當有正規濾鏡能曝出一個已知非 CFL 時，給你一條更俐落的捷徑。普通幫浦太鈍之處，Ogden 引理讓你能瞄準。
而這裡有令人鼓舞的另一面，正是接下來兩篇的主題。即便我們無法辨識上下文無關語言的每一道極限，對於一個給定文法我們能回答的問題卻出奇地溫馴：「這個字串在語言裡嗎？」與「這個文法到底生不生成任何東西？」兩者都是可判定的——成員問題由 CYK 演算法在 O(n^3) 時間內解決，空性問題則由一個簡單的可達性檢查解決。困難的問題（一個文法是否等價於另一個？一個文法是否歧義？）則早已不可判定。正因你現在懂得什麼是不可能的，才使得那些可能的事格外值得慶賀。