幫浦引理的賽局(pumping lemma game)
用幫浦引理證明非正規性,最好想成一場兩人賽局,因為這條引理是一串「對所有…存在…對所有」的量詞,而證明它的逆否命題,就是以「挑戰者」身分贏下這場賽局。你要證明「沒有任何」幫浦長度行得通;一個假想的對手則為「該語言是正規的」這個主張辯護。如果對手怎麼選你都有必勝走法,那麼該語言就不是正規的。
依序的走法:(1) 對手挑一個幫浦長度 p——你必須擊敗「任何」p,所以把 p 當成任意未知數。(2) 「你」挑一個長度 |w| ≥ p、屬於語言的字串 w,要挑得巧妙,使其結構僵硬(對 a^n b^n,致命選擇是 w = a^p b^p)。(3) 對手把 w 切成 xyz,須滿足 |y| ≥ 1 與 |xy| ≤ p——但因為 |xy| ≤ p 而 w 開頭是 p 個 a,y 只能由 a 組成,所以對手沒有好選項。(4) 「你」挑一個幫浦次數 i 來破壞成員資格:幫浦 i = 2 把 a^p b^p 變成 a^{p+|y|} b^p,a 比 b 多,因此「不」屬於該語言。矛盾;該語言不是正規的。
兩個關鍵紀律是:你「不」選 p(對手選,所以你的論證必須撐過每一個 p),而你「要」選 w 與 i(所以挑你能挑到最受限的字串、以及最明顯能破壞它的幫浦次數)。把這些搞混——自己選 p,或讓對手選 w——正是幫浦引理證明最常出錯的單一原因。
證明 a^n b^n 不是正規的。對手給出 p。你挑 w = a^p b^p。任何滿足 |xy| ≤ p 的切法都使 y = a^k(某個 k ≥ 1)。你幫浦到 i = 0(或 i = 2):x y^0 z = a^{p-k} b^p 的 a 比 b 少,因此不屬於該語言。對每個 p 你都贏,所以它不是正規的。
對手選 p 與切法;你選字串與幫浦次數。
贏下賽局只能證明「非」正規性;你無法藉「輸掉」來證明某語言「是」正規的。如果你選的字串怎麼幫浦都可以,那只代表你挑了個太弱的字串——換一個更受限的,或改用 Myhill-Nerode。