正規語言的幫浦引理

有限的記憶會露出馬腳

在封閉性那一階梯，你學到了正規語言能做什麼——你可以對它們取聯集、取交集、取補集、取反轉，而這一家族永遠跳不出盒子。這篇指南把問題反過來，問正規語言做不到什麼，以及你究竟要怎麼證明這種事。你沒辦法靠試遍每一台自動機、看著它們全部失敗來證明一個語言非正規；自動機有無窮多台。你該做的，是找出每一個正規語言都被迫具備的某個性質，再證明你懷疑的那個語言並不具備它。幫浦引理正是這樣一個性質。

這個性質從哪來？回想一下，DFA 就像一道旋轉閘門，只記得自己目前所在的狀態，而這種狀態只有有限多個——就說是 p 個吧。現在餵給它一個長度至少為 p 的字串。讀進 p 個符號，意味著機器會依序待過 p+1 個狀態（起始狀態，再加上每讀一個符號後的一個狀態）。但它名下只有 p 個相異的狀態。於是根據鴿籠原理——p+1 隻鴿子硬塞進 p 個籠子——這些走過的狀態裡，至少有兩個一定是同一個狀態。機器在無意間，回到了它先前已經待過的地方。

把引理小心地寫出來

以下是精確的主張。幫浦引理說：對每一個正規語言 L，都存在一個數 p，稱為幫浦長度，使得 L 中每一個長度至少為 p 的字串 w，都能被切成三段 w = x y z，並滿足三個條件。（1）中段非空：|y| >= 1。（2）前兩段落在前 p 個符號之內：|x y| <= p。（3）對每一個 i >= 0，被幫浦過的字串 x y^i z 也在 L 中。第三個條件就是那記重拳：x z、x y z、x y y z、x y y y z 等等全都在 L 中。

把每一段對回旋轉閘門的故事，引理就不再是一串符號了。那一段 y，是字串長到一定程度時、自動機被迫進入的那個迴圈；把 y 幫浦成 i 份，不過就是繞那個迴圈 i 圈。因為被迫的重複發生在前 p 個符號之內（這又是鴿籠原理），所以 x 與 y 合起來落在開頭那一段裡——這就是條件（2），|x y| <= p。而迴圈至少吃掉一個符號，所以 y 非空——這是條件（1）。這三個條件並非隨意定下的規矩；它們恰恰是迴圈論證交到你手上的東西。

p 有多大？你永遠可以把 p 取成任何一台辨識 L 的 DFA 的狀態數目——這正好就是鴿籠論證裡有幾個籠子。但這裡有個幾乎每個人第一次都會踩到的紀律重點：當你運用這個引理去證明非正規性時，你不能自己挑 p。引理只保證存在某個 p；它不告訴你是哪一個。所以在證明裡，你必須把 p 當成一個別人交給你的任意未知數，無論它最後是什麼值，你都要打贏它。

把它讀成一場遊戲

這個引理的形狀是「對所有 p，存在一種切法，對所有……」，外面再包一層「每一個字串」。這種順序的量詞，最容易當成一場兩人遊戲來處理：一方是你（挑戰者，想證明 L 不是正規的），另一方是對手（捍衛「它是正規的」這個說法）。要贏，你需要的是無論對手怎麼出招、你都有的必勝法。這場遊戲的劇情會準確告訴你每一步由誰掌控——而把這弄反，正是幫浦證明出錯的頭號原因。

對手挑出幫浦長度 p。你必須打敗任何 p，所以把它當成一個任意的未知數——絕不是你自己挑的某個數。
你挑出 L 中一個 |w| >= p 的字串 w，挑得讓它的結構盡可能僵硬（對 a^n b^n，那個致命的選擇是 w = a^p b^p）。
對手把你的 w 切成 x y z，並遵守 |y| >= 1 與 |x y| <= p。你必須挺過他們所有合法的切法。
你挑出一個幫浦次數 i，並證明 x y^i z 跑出了 L。這一個反例就違反了條件（3），證明大功告成。

注意這乾淨的掌控分工：對手選 p 和切法；你選字串 w 和幫浦次數 i。所以輪到你出招時，你的任務是盡可能地聰明又受限；輪到對手出招時，你的任務則是讓你的論證挺過他們所有可能的選擇。自己挑 p，或自己揀那個方便的切法，都是作弊——而這正是製造出「什麼也沒證明的證明」的那個錯誤。

把 a^n b^n 幫浦到死

我們來對那隻經典的礦坑金絲雀玩這場遊戲，a^n b^n——就是「若干個 a，後面接恰好同樣多個 b」的字串所成的集合（epsilon、ab、aabb、aaabbb、……）。直覺上，這個語言要求你數出 a 的個數，再檢查 b 的個數是否相符，而無上限的計數，正是有限記憶辦不到的事。幫浦引理把這個直覺化成滴水不漏的步驟。

Goal: prove L = { a^n b^n : n >= 0 } is NOT regular.

Adversary gives you some pumping length  p   (unknown).
You choose the string                   w = a^p b^p   (length 2p >= p).

Adversary must split  w = x y z   with |y| >= 1 and |x y| <= p.
Since the first p symbols are all a's, x and y live entirely
in that a-block, so:
        x = a^s ,  y = a^t ,  z = a^(p - s - t) b^p ,   with t >= 1.

You pump with  i = 2  (go around the loop one extra time):
        x y^2 z = a^(p + t) b^p .

Now there are  p + t  a's but only  p  b's, and  t >= 1,
so the counts differ  ==>  a^(p+t) b^p is NOT in L.

Contradiction: a regular language MUST pump, but L does not.
Therefore L is not regular.

對 a^n b^n 完整的幫浦引理遊戲。必勝來自 |x y| <= p 把 y 困在 a 群裡，於是一幫浦就讓 a、b 的個數失衡。

整個論證的關鍵樞紐，是條件（2），|x y| <= p。因為 w 以 p 個 a 開頭，這個條件迫使迴圈 y 整段都待在 a 群裡——對手沒有任何餘地能把一個 b 偷塞進 y。接著一幫浦，就只加 a 不加 b，那個微妙的「個數相等」平衡便應聲崩裂。這就是為什麼選 w = a^p b^p 如此高明：它恰好在引理所約束的那個位置上是僵硬的。隨便一點的選擇（比方說 a^p b）就會讓對手有空子可鑽，脫身而去。

讓你免於假證明的那個警告

現在來談整篇指南最重要的那個誠實重點。幫浦引理是正規性的一個必要條件，但它並不充分。「每個正規語言都能幫浦」是真的；「每個能幫浦的語言都是正規的」則是假的。確實存在一些非正規語言，能完美地滿足整個幫浦條件。所以，若你試著去幫浦一個語言，而它頑強地一直能被幫浦，你什麼也沒學到——你並沒有證明它是正規的，你只是沒能證明它不是。

為什麼會有這個落差？因為幫浦只捕捉了有限記憶的一個後果——長字串上存在一個可重複的迴圈。一個狡猾的語言，可以遞給你一個輕易就能幫浦的結構，卻仍偷偷藏著一個有限記憶無法執行的限制。（教科書上的反例就是這樣造出來的：每個長字串總能在某個無傷大雅的區域被幫浦，但這語言確實非正規。）於是，實用的規矩既嚴格又單向：*只有幫浦引理的失敗*才證明得了什麼，而它證明的是非正規性。** 「通過」永遠不是正規性的證書。

再帶走兩個誠實的提醒。第一，「非正規」不等於「不可能」——a^n b^n 雖非正規，卻完完全全是上下文無關的：一台下推自動機接受它的方式，是每讀一個 a 就往堆疊上推一個盤子、每讀一個 b 就彈掉一個，最後當輸入恰好結束時堆疊也恰好清空，才接受。是有限記憶這道牆，而不是計算本身擋住了路。第二，這個單向的警告，稍後同樣適用於上下文無關語言的幫浦引理：在那裡，「通過」也照樣什麼都不證明。接下來的第三篇，會把這裡的一切付諸實用，把這場遊戲變成一份乾淨、可反覆套用的非正規性證明食譜。