不對稱：要肯定很容易，要否定很難
證明一個語言「是」正規的，精神上是一擊就中的事：建一台 DFA、或寫一個正規表示式，指著它，就完工了。證明一個語言「不是」正規的卻是完全不同的怪獸。你拿不出一台機器，也無法把所有可能的機器一台一台地試遍——自動機有無窮多台，看著每一台失敗會花上永恆的時間。所以你翻轉策略：與其去獵捕一台機器，不如從「每個正規語言都被迫具備」的某個性質出發，再指出你懷疑的語言根本不具備它。
這些論證每一個都追溯到你在這架階梯上稍早遇過的同一個根本事實——DFA 的有限記憶極限。確定型有限自動機就像一道旋轉門，它永遠只記得自己目前停在哪個狀態，而狀態只有有限多個。所以任何要求你記住「無界」資訊的語言——無上限地計數，或把任意長的前半段拿去和後半段比對——都不可能是正規的，因為沒有固定大小的記憶能裝下它需要追蹤的那個無界之物。把這一句話記在心裡，下面每個證明都只是把它說精確的方法。
你來到這篇導覽時，三件標準武器中已握有兩件。上一篇導覽建立了幫浦引理與它的攻防賽局；本單元第一篇則把封閉性變成了一把證明的武器。這篇導覽就是那份食譜——你究竟如何挑一件武器、瞄準它、並把證明收尾——而它的結尾會誠實地說明：幫浦引理究竟在什麼時候會悄悄地讓你失手，而這正是下一篇導覽裡 Myhill-Nerode 定理的動機所在。
食譜：從頭到尾走一遍幫浦引理賽局
要記住幫浦引理證明，最乾淨的方式是把它想成一場兩人賽局：你是想揭穿這個語言的挑戰者，而一個隱形的對手則為「這個語言是正規的」這個主張辯護。初學者最常絆倒的地方在於「誰選什麼」。引理讀作「『存在』一個幫浦長度 p，使得對『所有』長字串，都『存在』一種切法，使得對『所有』幫浦次數……」。這種「存在」與「對所有」的交替，正是這場賽局的規則書，而把出手順序弄對，就是全部的技巧。
- 對手挑出幫浦長度 p。你「無權」選它——所以你必須擊敗「每一個」可能的 p。把 p 當成一個任意未知的正整數，絕不要假設某個特定值。
- 「你」挑一個屬於語言、長度至少為 p 的字串 w。這是你唯一的重大決定：挑你能挑到最僵硬、最受限的字串，讓對手沒有閃躲的空間。整個證明的成敗就繫於這個選擇。
- 對手把 w 切成 xyz，且須遵守引理強加的兩條規則：|y| >= 1（中段非空）與 |xy| <= p（x 與 y 合起來落在前 p 個符號之內）。一個巧妙的 w 形狀會把 y 釘死在一個狹窄的區域裡——這正是步驟 2 重要的原因。
- 「你」挑一個幫浦次數 i，並證明 x y^i z「不」屬於該語言，這就與引理矛盾。通常 i = 2（往上幫浦）或 i = 0（往下幫浦，刪掉 y）就能成事。因為這對每一種合法切法、每一個 p 都成立，所以該語言不可能是正規的。
範例一：a^n b^n
讓我們把食譜套用到教科書裡的金絲雀，語言 a^n b^n = { a^n b^n : n >= 0 }——若干個 a 後面接上「完全相同數目」的 b。步驟 1：對手交給我們一個未知的幫浦長度 p。步驟 2 是贏下賽局的一手：我們挑 w = a^p b^p。它是語言的成員（有 p 個 a 與 p 個 b），長度為 2p，輕鬆地大於等於 p，而且——關鍵在於——它的前 p 個符號「全都是」a。最後這個事實，就是我們布下的陷阱。
步驟 3：對手把 w 切成 xyz，且 |y| >= 1、|xy| <= p。我們的選擇就在這裡得到回報。因為 xy 必須塞進前 p 個符號裡，而前 p 個符號全是 a，所以中段 y 只能由 a 組成——就說 y = a^k（某個介於 1 與 p 之間的 k）。對手被逼到牆角：沒辦法讓 y 跨越 a/b 的交界、也沒辦法讓它落在 b 群裡。步驟 4：我們幫浦。取 i = 2，等於把 y 多讀一次：x y^2 z = a^{p+k} b^p。現在有 p+k 個 a 卻仍只有 p 個 b，而因為 k >= 1，個數不再相符——所以 x y^2 z「不」屬於 a^n b^n。但引理保證它應該屬於。矛盾。
Target string : w = a^p b^p (our choice, length 2p)
positions 1..p are all 'a' <-- |xy| <= p forces y in here
positions p+1..2p are all 'b'
Forced split : x = a^(p-k), y = a^k (k>=1), z = b^p
Pump up (i=2) : x y y z = a^(p-k) a^k a^k b^p = a^(p+k) b^p
#a = p+k , #b = p , and k >= 1 => #a > #b
==> NOT of the form a^n b^n ==> NOT in the language
Lemma said it MUST be in the language. Contradiction => not regular.範例二：ww，以及封閉性的捷徑
一個感覺更難的語言是 ww = { ww : w 屬於 {a,b}* }——每個由某個區塊重複兩次而成的字串，例如 abab（w = ab）或 aabaab（w = aab）。要接受它，你得記住「整個前半段」才能拿去和後半段比對，而對任意長的 w，那就是無界記憶。直接幫浦它，在挑 w 時需要一點小心（天真地挑 a^p a^p = a^{2p} 是可以被幫浦的，什麼也證明不了）。行得通的字串是 w = a^p b a^p b：它的前 p 個符號是 a，所以切法會逼出落在這個開頭區塊裡的 y = a^k，而幫浦到 i = 2 得到 a^{p+k} b a^p b，這已不再是兩個相等的半段。矛盾。
但還有一條更俐落的路，能完全跳過那種磨人的選字串：封閉性捷徑。回想第一篇導覽：正規語言對交集封閉——所以如果你能把你懷疑的語言和一個「已知是正規」的語言取交集，結果落到某個「已知非正規」的語言上，那這個懷疑對象一開始就不可能是正規的。這是一招邏輯柔道：你向一個你已信任其地位的語言（通常是 a^n b^n）借來那個矛盾。
下面是這個捷徑套在另一個語言上的經典範例。主張：在 {a,b} 上「a 與 b 個數相等」的字串所成的語言 L 不是正規的。為了反證，假設它是。正規語言對交集封閉，所以 L 與正規語言 a* b*（先全是 a、再全是 b）的交集也會是正規的。但這個交集「恰好」是 { a^n b^n : n >= 0 }——既是「先全 a 再全 b」、又是「個數相等」的字串。我們已經證過 a^n b^n 不是正規的，所以這個交集不是正規的——與封閉性矛盾。因此 L 一開始就不是正規的。沒有幫浦、沒有磨人的選字串；一個典範的事實就完成了全部的工作。
誠實的警語：通過測試什麼也證明不了
現在來談整個主題裡最重要的誠實要點。幫浦引理是正規性的「必要」條件，但「不是」「充分」條件。白話說：「每個正規語言都能被幫浦」為真，但「每個能被幫浦的語言都是正規的」則「為假」。只有引理的「失敗」才能證明事情，而它證明的是非正規性。如果你試著幫浦一個語言，它卻不管你怎麼做都頑固地一直能幫浦，那麼你對「它是否正規」一無所獲。你可能只是挑了個太弱的字串——也可能這個語言正是那種反例：通過了幫浦測試，卻不是正規的。
這個差距為何存在，值得一看。幫浦引理只捕捉到有限記憶的「一個」後果——長字串必含一個可重複的迴圈。一個狡猾的語言可以遞給你一個「輕易就能幫浦」的結構，同時仍暗藏一個有限記憶無法維持的限制。標準反例是 L = { a^i b^j c^k : 若 i = 1 則 j = k }（連同所有 i 不為 1 的字串）。它裡頭每個長字串都能被幫浦——當 i 不為 1 時你在 a 區段幫浦並留在語言內；當 i = 1 時，可用的切法並不威脅 j = k 的限制——然而 L 確確實實不是正規的。所以寫下「L 滿足幫浦引理，因此 L 是正規的」是一個徹底的邏輯錯誤，永遠無效。
這正是接下來兩件工具重要的原因。當某次特定的幫浦嘗試卡住時，封閉性論證有時能從不同角度（交集、補集、反轉，或同態）出擊而成功。而下一篇導覽要建立的 Myhill-Nerode 定理，則「既必要又充分」——它「恰好」刻畫了正規性，所以永不給出假的「通過」，也永不漏掉一個確實非正規的語言。當幫浦引理讓你拿不定主意時，Myhill-Nerode 就是那把把問題一勞永逸定案的決定性器械。
挑選你的武器，以及常見陷阱
實務上，先抓起對眼前這個語言來說最短的那件工具。如果語言有明顯的「拿這個對那個計數」的形狀（a^n b^n、回文、成對括號），那麼搭配一個挑得好的字串的幫浦引理賽局，又快又直接。如果你的語言是個雜亂的混合物、但過濾之後含有一個乾淨的非正規核心，那麼封閉性捷徑——與一個簡單的正規語言取交集以逼出 a^n b^n——往往是一行的證明。而如果兩者都讓你覺得滑溜難抓，就直接跳到 Myhill-Nerode：拿出一個「兩兩可區分」的無窮字串族，你就確定無疑地完工了。
三個陷阱起初幾乎逮住每一個人。(1) 自己選 p——p 是對手選的，而你的論證必須撐過每一個 p，所以把它當成任意未知數。(2) 在步驟 2 挑了個軟趴趴的字串——對 a^n b^n 挑 w = a^{2p}，會讓對手在 a 群裡幫浦並仍然合法，於是證明失敗了，但這不是引理的錯；永遠挑最「受限」的字串，那種前 p 個符號就把 y 釘死的字串。(3) 從一次成功的幫浦推出正規性——根本沒有「用幫浦來證明正規」這回事；只有「幫浦不掉」才能證明非正規性，而一個總能幫浦的字串只代表你挑得不好、或需要動用 Myhill-Nerode。
退一步，貫穿全文的主線很簡單：每個非正規性證明，都是當場逮住一個語言「需要無界記憶」的方法。有限記憶極限是那樁罪行，幫浦引理與封閉性論證是兩位不同的偵探，而 Myhill-Nerode 則是那個永不產生偽陰性的鑑識測試。把「挑對字串」與「尊重誰選什麼」練到精熟，對「必要但不充分」的警語保持誠實，你就能有信心地證明正規語言的那條邊界。