動機
有限自動機可以讀入任意長的輸入,但它只有有限多個狀態。在足夠長的輸入上,它必然會重新訪問某個狀態。夾在兩次訪問之間的那一段輸入可以被重複或刪除,而不會改變其餘計算的起點。這個簡單的循環觀察,成為證明某些語言不能被任何有限自動機識別的有力方法。
這一證明技巧是一場選擇的博弈。假想的自動機決定泵長度;我們選取一個足夠長的字;對手給出該字的一個合法分解;最後我們必須找到一個重複次數,使得該字落到語言之外。只用一個方便的分解是不夠的,因為未知的自動機可能給出不同的循環。我們還會看到一個通過了泵檢驗的非正則語言,可見該檢驗有明確的局限。
定義與定理
定義 1.4.1
(字的冪與長度)
固定有限字母表 。對於字 ,記 ,;當 為非負整數時, 表示 個 的連接。字 的長度記作 。
定理 1.4.2
(正則語言的泵引理)
若 是正則的,則存在整數 ,使得每個滿足 的 都有分解 ,滿足 、,並且對每個整數 都有 。
量詞的次序十分重要。同一個 必須對 中每個足夠長的字都適用。對每個這樣的字,合適的分解可以依賴於該字,而且之後每個重複次數都必須保持該字屬於語言。引理並沒有說每個分解都可行。它也容許刪除,因為 包括在內。
定理 1.4.3
(用於非正則性證明的逆否命題)
若對每個整數 ,都存在 且 ,使得每個滿足 且 的分解 都存在某個 使 ,則 不是正則的。
逆否命題中的重複次數可以依賴於分解。在特別簡潔的論證中,像 這樣的同一個次數對所有合法分解都有效。如果對手給出非法分解(例如 ),則無需考慮。
證明:重複的狀態產生循環
證明
(重複的狀態給出循環)
設 被一個有 個狀態的完全確定型有限自動機識別。令 。設 的長度至少為 。考慮讀完長度為 的各前綴之後所經過的 個狀態。由鴿籠原理,其中有兩個相同。選取出現這一重複的下標 。令 為前 個符號, 為接著的 個符號, 為餘下的後綴。
於是 ,且 。讀入 會使自動機回到讀完 後所處的同一狀態。對任意 ,恰好讀入 次 之後自動機仍停留在該狀態;隨後讀入 時,所走的路徑與原來的字一樣通向接受。因此對所有 都有 。
這一證明為每個正則語言給出了一個泵長度,但不一定是最小的。當 不含長度至少為 的字時它同樣成立:此時關於這類字的全稱命題是空真的。非確定型自動機也不構成問題,因為每個正則語言都有與之等價的有限確定型自動機。
證明透視
為甚麼鴿籠計數給出合法的循環
這個證明有一個不顯然的步驟:它數的是前綴,而不是狀態。長度為 的 個前綴經過 個狀態,比可用的 個狀態多一個,所以必有兩個相同;這正是循環落在前 個符號之內、從而 的原因。嚴格不等式 使 非空,循環才真的消耗輸入。重複循環用到確定性:從重複出現的狀態出發,讀入 總是沿同一條路徑回到該狀態,所以循環可以走任意多次,之後 再沿原來的路徑通向接受。最後, 是 的某個固定自動機的狀態數,因此不依賴於 ;這就是引理中量詞的次序。若狀態集不是有限的,鴿籠步驟就沒有可數的東西。
例題詳解
例題 1.4.4
(兩個區塊中的數目相等)
令 。假設它是正則的,並設 為其泵長度。選取 。每個合法分解都滿足 ,所以其非空的 只由符號 構成:對某個 有 。向下泵(取 )得到 ,兩個區塊的長度不同,它不屬於 ,與引理矛盾。因此 不是正則的。
這個字依賴於 ,但它是在分解之前選定的。論證一次過處理了每個合法的 ,並沒有假設循環的長度為一。
例題 1.4.5
(平方數長度的一元語言)
令 。給定任何假設的泵長度 ,選取 。合法的 長度為 ,其中 。再向上泵一次,取 。新的長度 嚴格大於 ,並嚴格小於 。因此它不是平方數。這證明了即使在只有一個符號的字母表上, 也是非正則的。
相鄰平方數之間的間隙是關鍵所在。僅僅說重複一個區塊會改變平方數的長度是不夠的,因為某些改變可能得到另一個平方數。
例題 1.4.6
(迴文需要匹配相距遙遠的符號)
令 為 上的全部迴文。對於泵長度 ,選取 。該字是迴文,且長度足夠。每個合法的非空 都落在前 個字母之中,且對某個 有 。向下泵得到 ,它不是迴文,因為唯一的 兩側的 的個數不同。因此 是非正則的。
例題 1.4.7
(正則語言也有不好的分解)
取 與字 。取 ,分解 、、 就長度限制而言是合法的,但 不在 中。這並不與正則性矛盾:一個好的分解是 、、,對它而言,對每個 , 都仍在 中。引理保證的是存在合適的分解,而不是原字中所有可能的循環都可行。
選取有效的字
第一次嘗試選取的見證字,可能給了對手過多自由。例如,為研究數目相等的條件而使用 ,會引入多個區塊,必須逐一追蹤它們的變化。較短的字 則把整個被容許的前綴都放在第一個區塊裏。這樣,證明在不確切知道 從哪裏開始、有多長的情況下,就知道了 的形式。相反,選取像 這樣固定的字,無法戰勝任意大的泵長度:它可能比 還短,此時引理對它甚麼也沒有說。
有時有用的重複次數是刪除,有時增長更清晰。在平方數的論證中,從 中刪去至多 個符號,對 恰好也避開了前一個平方數,但 的情形需要另外處理。向上泵則統一地使用簡單的不等式 。好的做法是寫出新的確切長度,找出相鄰的兩個容許長度,並證明嚴格不等式。如果泵後的字長度正確卻違反了次序條件,就應當給出關於次序的論證。
長度條件 是資訊的來源,而不是 從字的開頭開始的保證。前綴 的長度可以是從零到 的任何值。對於一元前綴,這種非確定性無關宏旨:每個非空的連續子串都由同一個字母構成。對於較複雜的前綴,證明必須既涵蓋跨越內部邊界的循環,也涵蓋位於單個區塊內的循環。
其他工具有時能更容易地得出同樣的結論。例如,若有一族前綴,它們兩兩要求不同的未來回應,就可以確立有無窮多個可區分的狀態。這種方法透過狀態數的下界來證明非正則性,而不是透過選取重複。泵引理依然有用,因為一個簡短而量詞正確的字論證,往往能揭示學生需要理解的具體記憶需求。
通過檢驗的非正則語言
反例模式
通過泵檢驗並不蘊涵正則
一個誘人的逆命題是:只要語言中每個足夠長的字都可以泵,語言就是正則的。泵引理是正則性的必要條件,而不是充分條件。考慮 上的語言
它在 時滿足泵結論。對於 中任意非空字串,取 ,並令 為其第一個符號。若字以 開頭,則泵只改變開頭 的個數。只要至少還剩一個 ,原有的等式 仍然成立;若一個 也不剩,則另一種情形 使結果無論如何都是語言的成員。若字以 或 開頭,則它已經有 ,重複或刪除這第一個符號既保持區塊的形式,也保持 這一情形。因此對所選的分解,所有重複次數都有效。
然而 是非正則的。若它是正則的,則它與正則語言 的交,由有限自動機的乘積構造,也是正則的。但這個交恰好是 。設該交集的泵長度為 ,選取 。合法的非空 包含在前 個符號之內,這些符號都位於 區塊之前。若 含有開頭的 ,向下泵就刪去了唯一的 ;否則它刪去一個或多個 ,而保留 個 。無論哪種情形,結果都在該交集之外。於是泵引理證明該交集是非正則的,矛盾。
這一構造展示了一個有用的證明策略:與一個簡單的正則語言取交,以暴露語言中困難的部分。它也恰好說明了,為甚麼僅僅在每個長字中找到可泵的片段,並不能構造出有限自動機。
常見錯誤
常見錯誤
(自行選定分解)
非正則性證明不能自行選定分解,再說明某一次泵失敗:自動機的循環可能對應另一個分解。正確的做法是選取一個字,使其前 個位置約束所有可能性,然後陳述每個合法的 必須是甚麼樣子。
常見錯誤
(先看到字才選 )
不要對調泵長度與字的角色。我們不能在看到有利的字之後才選擇 。在正則性的假設之下,我們接受任意一個有效的 ,並構造依賴於它的字。我們也不必指出實際的自動機或其狀態數;矛盾對每個正的 都成立。
常見錯誤
(未依語言定義就斷言泵出語言之外)
泵出語言之外必須依據語言的定義來論證。對於平方數長度的例子,間隙的計算說明不會落到另一個平方數。對於區塊語言,必須檢查區塊的次序以及各計數之間所需的關係。僅僅改變字本身,並不足以證明它不是成員。
文法可以同步重複兩段,有限狀態集卻做不到。
通往推廣的路徑
對上下文無關語言,甚麼改變了?
文法可以同步重複兩段,有限狀態集卻做不到。
對上下文無關語言,重複涉及兩段。存在 ,使每個 ()都可寫成 ,滿足 、,且對所有 有 。這與上下文無關的 並不矛盾,卻能推翻 :在 中,窗口 不可能同時碰到 和 ,因此泵動時某個字母的個數不變,而另一個改變。
總結
有限狀態的重複,使每個足夠長的被接受字的前 個符號之內都存在一個循環。要證明非正則性,就要迫使每個可能的循環落在這樣一個區域:改動它會破壞成員資格。保持量詞的原有次序,並使用像零或二這樣具體的次數。逆命題不成立:僅僅通過泵性質並不能保證正則性。
練習
快速檢查
(證明 是非正則的。)
選取一個前 個符號全是 的字。
解答 · 答案
假設存在泵長度 ,並選取 。每個合法的 都是 ,其中 。向下泵得到 。成員資格要求 ,而這對 不可能成立。這與引理矛盾。
快速檢查
(利用相鄰二的冪之間的間隙,證明 是非正則的。)
向上泵一次,並把新長度與 、 比較。
解答 · 答案
對任意假設的 ,選取 。因為 ,它的長度足夠。每個合法循環的長度 滿足 。取 來泵,得到長度 。由於 ,該長度嚴格介乎 與 之間,因而不是二的冪。該矛盾證明了非正則性。
快速檢查
(對於 ,給出一個泵長度,並為每個足夠長的字給出有效的分解。須處理以任一字母開頭的字。)
泵長度取 已經足夠;令 為第一個符號。
解答 · 答案
取 。對於以 開頭的非空字串,選取 與 ;重複或刪除這個開頭的 ,剩下的是一個 區塊後接一個 區塊。對於以 開頭的非空字串,該字不含 ,選取第一個 作為 ,剩下的是 中的字。每個所需的泵次數都保持成員資格。
快速檢查
(對於上面的語言 ,解釋為甚麼字 在刪去開頭的兩個 之後仍屬於 ,儘管它原本的成員資格也用到了 。)
回想 的定義是一個析取。
解答 · 答案
刪去兩個 得到 ,其開頭 的個數為零。 的定義使用的是包容的「或」,所以 這一情形就足夠了。在這個特定字中,等式 也仍然成立,但開頭 個數為零這一情形,即使在數目不等時也會使其成為成員。