正規語言的幫浦引理（pumping lemma for regular languages）

幫浦引理是「鴿籠原理」的喬裝。DFA 只有有限多個狀態，所以當它讀夠長的字串時，必定造訪某個狀態「兩次」——就像走一條門比步數還少的走廊，你注定會再經過同一扇門。這兩次造訪之間的路徑是一個迴圈，而迴圈可以走零次、一次、甚至一百次。因此每個正規語言都必須容忍這種迴圈：語言中夠長的字串，有一段中間區塊可以自由重複（「幫浦」）並仍留在語言內。

精確的敘述：對每個正規語言 L，都存在一個數 p（幫浦長度），使得 L 中長度至少為 p 的每個字串 w 都能切成三段 w ＝ xyz，滿足三個條件：(1) |y| ≥ 1（中段 y 非空）；(2) |xy| ≤ p（x 與 y 合起來落在前 p 個符號內）；(3) 對每個 i ≥ 0，幫浦後的字串 x y^i z 也屬於 L（所以 xz、xyz、xyyz、xyyyz、… 全都屬於 L）。這裡 y 是自動機被迫進入的那個迴圈，把 y 重複 i 次對應於繞那個迴圈走 i 圈。

請仔細讀這條引理：它是「關於正規語言」的一個保證，而我們用它的「逆否命題」（contrapositive）來證明某語言「不是」正規。它對「如何辨識」一個語言隻字未提，而且是一道單向門——通過幫浦條件並不會讓語言變成正規。它誠實的職責雖窄卻有力：它證實了有限記憶所「強迫」出現的、無可避免的重複。