動機
有限自動機讀入一個足夠長的單詞時,必然會重複某個狀態。上下文無關文法擁有另一種有限記憶:在語法分析樹的足夠長的分支上,非終結符可以重複出現。非終結符的重複產生兩段互相嵌套的推導,它們可以被同時插入。上下文無關泵引理正是把這個觀察精確化。
該引理是語言為上下文無關的必要條件,因此它的逆否命題可以用來證明某個語言不是上下文無關的。它不是定義,也不是充分的判別法。在證明非上下文無關性時,我們必須擊敗引理所容許的每一種分解,儘管我們可以自行選擇單詞與泵取指數。
定義
定義 2.7.1
(分解與泵取)
設 是有限字母表上的語言。單詞 的一個分解,是由五個連續字串 構成的列表,滿足 。除非所述條件排除,否則這些字串可以為空。泵取是指把 與 同時替換為相同數目的副本,而中間的 保持不動。例如,指數為零的泵取同時刪去 與 ,而指數為一則還原原單詞。
定義 2.7.2
(帶受保護起始規則的喬姆斯基範式)
我們使用喬姆斯基(Chomsky)範式的上下文無關文法,其規則為 或 ,並可能帶有一條受保護的起始規則 。對於一個所生成的非空單詞,其語法分析樹具有二元的變元節點與終結符葉子。範式轉換是前面已有的標準結果;下面的論證也說明了為甚麼空單詞這個例外不會造成問題。
定理
定理 2.7.3
(上下文無關泵引理)
若 是上下文無關語言,則存在整數 ,使得每個滿足 的 都有一個分解 ,滿足 、,並且對每個整數 都有 。
定理 2.7.4
(一個非上下文無關語言)
語言 不是上下文無關的。
證明
證明:語法分析樹路徑上的重複變元
證明
(由最長路徑上重複的變元得到泵取)
取 的一個範式文法,設其有 個變元,並令 。一棵二叉樹若其每條路徑至多含有 個二元變元節點,則它至多有 個葉子。因此,長度至少為 的單詞的語法分析樹中,有一條從根到終結符的路徑含有多於 個變元出現。選取一條最長的這樣的路徑。在它最低的 個變元出現中,有兩個帶有相同的變元標號;把較高的出現記為 ,較低的出現也記為 。
把較高子樹的終結符產出寫成 ,其中 是較低子樹的終結符產出。該子樹之前的周圍部分產出 ,之後的部分產出 。於是文法有如下形式的推導:
所顯示的字串 是相關兄弟子樹的終結符產出,不一定是單一文法步驟所產生的符號。把較低的 子樹替換為較高 子樹的一個副本,就重複了外層推導;把較高子樹直接替換為較低子樹,則將其刪去。因此對每個 , 都被生成。
上方的出現位於最長路徑上最低的 個變元出現之內。它下面的所有路徑都不長於該最長路徑的相應後綴,所以它的子樹至多有 個終結符葉子。故 。由於這兩個出現是不同的,從上方 到下方 的路徑含有一條二元規則。其兄弟子樹至少產生一個終結符:在這棵非空單詞的分析樹上,受保護的起始符之下沒有變元使用空規則。因此 。這也說明了為甚麼 變化時,泵取確實會改變單詞的長度。可能存在的規則 只處理空單詞,而空單詞短於 ,且不在這棵樹中使用。
證明透視
為甚麼最長路徑很重要
樹的深處某處出現的重複變元會給出可泵取的分解,但其本身並不能限制整個子樹的大小。選取最長的根到葉路徑底部附近的重複出現,可以控制上方出現之下的每一個分支,並得到 。
證明三個相等的塊不是上下文無關的
證明
(三個相等的塊擊敗每一個分解)
假設 是上下文無關的,用反證法,並設 為其泵取長度。選取 。它屬於 ,且長度至少為 。引理保證存在某個滿足其條件的分解。我們並不選擇該分解,而是考慮任意一個滿足條件的分解。
連續子字串 的長度至多為 。它不可能同時含有 與 ,因為這樣的子字串必然也包含中間全部 個 ,長度至少為 。因此 與 合起來至多含有三種塊類型中兩種的符號,至少有一種類型未被觸及。由於 ,取 時,另外兩種類型中至少有一個的計數減少。
刪去 與 會保持其餘字母的次序。未被觸及的類型仍出現 次,而被觸及的某個類型出現次數少於 。三個計數不再相等,所以 。這與引理對所保證的分解的結論相矛盾。由於該論證涵蓋每一個容許的分解,這一矛盾是有效的。
例題詳解
例題 2.7.5
(上下文無關語言的一個容許分解)
文法 生成 。對於 ,取 、、、。泵取得到 ,它仍在該語言中。這說明了兩個同步的片段;它並不證明該語言中每個單詞都滿足泵引理。
例題 2.7.6
(較短的中間部分可能跨越邊界)
對於 ,所設想的子字串 可能完全位於一個塊內,也可能跨越 邊界或 邊界。在長度至多為四的條件下,它不可能從一個 延伸到一個 。計數論證並不枚舉 與 的確切位置,而是觀察到整整一種符號類型未被觸及,而刪除會改變至少另一個計數。
例題 2.7.7
(同時泵取很重要)
對於 ,取 、、、。取 時結果為 。若只泵取 ,則得到 ,但引理並不斷言這種單邊操作仍留在語言中。兩個片段使用的是同一個指數。
常見錯誤
選擇的順序
泵引理陳述的是一連串的選擇與義務。首先,上下文無關語言提供一個對所有足夠長的單詞都適用的 。然後,任何符合條件的單詞都必須至少有一個良好的分解。最後,對該分解,每個非負指數都必須成立。
在反證法的證明中,可以設想一個對手宣布 。你依據 選擇一個單詞。對手可以選取任何滿足長度與非空條件的分解。然後你必須給出一個指數(可以依賴於該分解),使得泵取後的單詞離開該語言。上面選用的 是統一適用的,但並非每個證明都有這樣方便的統一指數。
僅有一個壞的分解甚麼也證明不了:上下文無關語言也可能有許多無法泵取的分解。僅檢查塊與塊之間明顯的分割也是不夠的。論證必須考慮位於某個塊內部的片段、跨越邊界的片段,以及 之一為空的情形。
反例模式
一個壞的分解並不構成矛盾
斷言:要否證上下文無關性,只需找出某個長單詞的一個不能泵取的分解。在上下文無關的語言 中,取 和分解 、、、、,此時 ,。向下泵取得到 ,它不在該語言中,所以這個分解失敗。然而該語言是上下文無關的,而且前面的例題給出了一個對每個指數都能泵取的分解(、)。引理要求的是存在一個好的分解,所以否證必須擊敗每一個容許的分解。
常見錯誤
(單詞必須依賴於泵長度)
在反證法中,泵長度 由假設存在的文法給出,而且是未知的。固定的單詞(例如 )不可行:若 ,引理對長度為 的單詞甚麼也沒有說。應當用 來選取單詞,例如 。
常見錯誤
(把引理讀反了)
引理的形式是:上下文無關蘊涵可泵取。證明所用的是它的逆否命題:不可泵取蘊涵不是上下文無關。其逆命題,即可泵取蘊涵上下文無關,並沒有被斷言,所以找到某個能泵取的分解絕不能證明一個語言是上下文無關的。
該引理能說明甚麼與不能說明甚麼
對於 ,障礙在於兩個短的可泵取片段無法改變全部三個分隔開的塊,而等式要求它們的計數一同變化。固定的中間塊迫使短子字串至少錯過一種符號類型。該論證同時用到了 的局部界與 的非空性。
該引理並不意味著每個非上下文無關語言都能用這一特定方法證否。即使某個語言滿足泵性質,僅憑這一事實也不能給出上下文無關文法。可能需要封閉性質、更強的泵引理陳述或其他方法。反過來,在排除所有容許的分解之前,未能找到良好分解並不構成證明。
把該引理應用於新的語言時,首先要檢查,對每個宣布的 ,所選取的單詞都屬於該語言。然後確定短的連續區間無法覆蓋甚麼。最後計算一個具體的泵取結果,並準確說明哪一條成員資格要求不成立。若泵取既改變了計數又改變了次序,則任何一種失敗都已足夠,但應當明確陳述,而不是想當然。
第二種障礙:交叉的等式
考慮 。這裏有兩個等式,而不是要求四個計數全部一致。我們仍然可以利用兩個被泵取片段的局部跨度。假設 是上下文無關的,取其泵取長度 ,並選取 。長度至多為 的子字串不可能同時含有 與 :整整一個含 個符號的中間塊位於二者之間。類似地,它也不可能同時含有 與 。
對任何容許的分解,四種類型中至少有一種出現在 中。若被改變的類型是 或 ,則等式 中與之配對的另一方不在整個跨度 中。若是 或 ,則等式 中與之配對的另一方不在其中。向下泵取會減少被改變類型的計數,而其配對方仍為 。因此無論刪去了其他哪些符號,至少有一個所需的等式不成立。這證明了 不是上下文無關的。
等式的次序很重要。相比之下, 是上下文無關的:一個文法生成相等的 對,另一個生成相等的 對,再由新的起始符號把它們的輸出連接起來。一個具體的文法是 ,,。給出文法並追蹤其兩個獨立的選擇,可以避免依賴對堆疊能記住甚麼、不能記住甚麼的直觀圖像。
該語言的證明不需要文法的實際變元個數,也不需要顯式的 值。它對引理可能給出的每個正整數都成立。這很有用,因為在反證法中所假設的文法可能完全未知。若不參照 而選取一個固定的單詞,一般來說是不夠的:未知的泵取閾值可能比該單詞更大。
總結
沿著語法分析樹長路徑出現的重複變元,提供了兩個同步的可泵取片段。子樹大小的界使它們合起來的跨度是局部的。在非上下文無關性的證明中,單詞是在泵取長度之後選取的,但論證必須擊敗每一個被容許的分解。
練習
快速檢查
(對於 與 ,給出一個 與 均非空、且在 內可泵取的分解,並計算其 與 的結果。)
解答 · 答案
取 、、、。向下泵取得到 ,泵取兩次得到 。每個指數都產生 。
快速檢查
(證明: 中同時含有 與 的子字串,其長度至少為 。)
解答 · 答案
該子字串始於最後一個 或其之前,止於第一個 或其之後。它含有這兩個端點符號以及中間全部 個 ,共至少 個位置。
快速檢查
(在 的證明中,設 為空,而 含有一個或多個 且沒有其他符號。解釋向下泵取之後出現的矛盾。)
解答 · 答案
向下泵取至少刪去一個 ,而不刪去任何 或 。所得的計數分別為 、少於 、,因此即使一個被泵取的片段為空,結果仍在 之外。
快速檢查
(某學生選取 的單一分解,證明它在 時失敗,並由此斷言語言非上下文無關。指出缺失的量詞,並修補該論證提綱。)
解答 · 答案
引理容許文法提供任何合適的分解,而不一定是該學生所選的那個。固定任意一個滿足 與 的分解。其跨度至少錯過三種符號類型之一;刪去這對非空片段會改變另一個計數,而被錯過的類型的計數仍為 。因此每個容許的分解在指數為零時都失敗。