上下文無關語言的幫浦引理（pumping lemma）

幫浦引理是鴿籠原理（pigeonhole principle）穿上剖析樹的戲服。核心想法：在任何上下文無關語言裡，每個夠長的字串都藏著一塊，你愛重複幾次就重複幾次，而結果「仍然」落在語言之內。正規語言的幫浦引理抽取一塊；上下文無關版本一次抽取「兩」塊、同步進行——這個怪癖直接源自剖析樹如何分岔。

精確地說：對每個上下文無關語言 L，存在一個常數 p（幫浦長度），使得 L 中每個長度至少為 p 的字串 z 都能切成「五」部分 z = 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。仔細讀條件 (3)——v 與 y 用「同一個」指數 i「一起」被抽取（取 i = 0 也可同時刪掉兩者）。為什麼是兩塊？把 L 的文法化為喬姆斯基正規形式（Chomsky normal form），其中每條規則都是二元的，所以剖析樹是二元樹。夠長的產出逼出一條夠長的「根到葉」路徑；由鴿籠原理，某個變數 A 在這條路徑上重複出現。上方那個 A 的子樹推導出 v x y，內側那個 A 推導出 x；把上方子樹接回它自己，就在左邊重複 v、右邊重複 y——同時抽取兩塊。

用得正確時，這個引理是單向的武器：它讓你「證明」一個語言「不」是上下文無關，做法是顯示沒有任何合法的五段切法能在抽取下存活。你「永遠」不會用它來證明某語言「是」上下文無關。和它的正規語言表親一樣，它只是必要條件，「永遠」不是充分條件：有些非上下文無關語言照樣滿足這個抽取條件，所以通過測試證明不了任何正面的結論。