動機
正則約束可以檢查有限狀態資訊,而下推自動機負責處理嵌套或配對。讓兩部機器並行運作,就得到它們交集的上下文無關語言。這個有用的封閉性質不能與兩個上下文無關語言的交運算封閉性混為一談:兩個互相獨立的無界配對要求,可能超出單一堆疊所能強制執行的範圍。
下面的乘積構造在全部輸入被消耗完之後按終結狀態接受。靜默的下推移動使有限自動機的狀態保持不變。隨後我們證明,上下文無關語言在交運算與補運算下不封閉,並給出具體反例。
定義
定義 2.8.1
(下推自動機與 DFA 的乘積)
設 是有限字母表 上按終結狀態接受的非確定性下推自動機(PDA),設 為完全 DFA。乘積格局記錄下推自動機的狀態與堆疊,以及 DFA 的當前狀態。若 讀入 ,則乘積使 按 前進;若 執行 轉移,則乘積保持 DFA 狀態不變。當且僅當兩個分量狀態都是終結狀態時,乘積狀態才是終結狀態。
定義 2.8.2
(上下文無關語言)
若一個語言被某個遵循此約定的非確定性 PDA 接受,則稱其為上下文無關語言。此處使用它與上下文無關文法之間的標準等價性。補集是相對於固定的全集 而取的。
定理
定理 2.8.3
(與正則語言的交)
若 是上下文無關語言, 是同一有限字母表上的正則語言,則 是上下文無關語言。若 的 PDA 在通常的「無互相衝突的靜默移動」定義下是確定性的,則乘積仍然是確定性的。
定理 2.8.4
(兩個上下文無關語言的交可以不是上下文無關語言)
上下文無關語言
的交為 ,而它不是上下文無關語言。因此,上下文無關語言在交運算與補運算下均不封閉。
證明思路或證明
證明
(乘積自動機識別交集)
在乘積中,一次運行可投影為 的一次運行,以及 DFA 在迄今已消耗符號上的唯一運行。對乘積轉移作歸納可證明:DFA 分量恰好是讀完已消耗前綴後所到達的狀態——輸入移動使兩個分量同時前進,靜默移動只使 前進。到結束時,兩部機器讀過的是同一個完整的詞。當且僅當 PDA 與 DFA 都接受該詞時,乘積才接受它。乘積只有有限多個控制狀態對,並沿用原來的堆疊字母表,因此它是一個 PDA。
若 是確定性的,則將其狀態與 DFA 狀態配對並不增加轉移的選擇。對每個輸入符號,DFA 的轉移是唯一的;而對同一個下推狀態與堆疊頂端符號,PDA 的 移動仍然排斥讀入輸入的移動。因此乘積保持確定性條件。這證明了對與正則語言的交運算封閉;它並沒有證明任意兩個確定性下推語言的交運算封閉。
證明
(兩個配對約束不能共用一個堆疊)
文法 ,, 生成 。類似地,,, 生成 。同時屬於兩者的詞具有有序形式 ,並滿足 且 ,由此得到上面所示的交。
要證明該交不是上下文無關語言,假設上下文無關泵引理成立,泵長度為 ,並將其作用於 。在每一個滿足 且 的允許分解 中,段 至多與三個連續符號塊中的兩個相交。向下泵(刪去 與 )會從 或 中至少移除一個符號,同時至少一個完整符號塊的個數保持不變。從 刪去若干符號後仍是形如 的詞,所以只需看計數,而三個計數不可能全部保持相等。這與泵引理矛盾。
證明透視
泵論證在何處用到它的假設
選取詞 ,是為了使界 迫使被泵的段錯過一整個符號塊:單是 塊的長度就是 。這是泵長度唯一發揮作用之處。選擇向下泵,是因為刪去符號不改變符號塊的次序,只改變計數。假設 保證某個計數確實改變。不明顯的一步是去數 碰不到的符號塊,而不是追蹤它碰到的符號。論證之所以封閉,是因為未被觸及的符號塊保持計數 ,而被觸及的符號塊降到 以下,所以不論引理給出哪種允許的分解,三個計數都不可能相等。
證明
(補運算封閉會推出交運算封閉)
上下文無關語言對並運算封閉:用一個新的起始符號來選擇任一文法的起始符號即可。若它們在 上對補運算也封閉,則德摩根(De Morgan)恆等式 將推出對交運算封閉。上述反例排除了這一點,所以對補運算的封閉性同樣不成立。
例題詳解
例題 2.8.5
(配對加上奇偶條件)
將 與含有偶數個 的詞所構成的正則語言相交。DFA 記錄奇偶性,PDA 檢查配對。乘積恰好接受 。
例題 2.8.6
(兩種不同的配對要求)
詞 屬於 ,因為 與 的個數相等;但它不屬於 ,因為 與 的個數不同。詞 同時屬於兩者。交運算同時強制兩個等式成立。
例題 2.8.7
(一個被泵的見證)
取 與詞 ,並假設被泵的部分完全落在 塊內,且向下泵時至少移除了一個 。此時 與 的個數仍為三,而 的個數減少。所得的詞不在 中。一般性的證明涵蓋了所有允許的位置,包括跨越某一個邊界的片段。
常見錯誤
反例模式
正則是一個真正的限制
一個誘人的論證是:PDA 可以與 DFA 並行運行,所以兩個 PDA 也可以並行運行,因此兩個上下文無關語言的交仍是上下文無關語言。 與 駁倒了這個說法。兩者都是上下文無關語言(見上面明確給出的文法),並且 同時屬於兩者,但它們的交 卻不是上下文無關語言。與 DFA 的乘積只額外儲存有限個狀態,而兩個 PDA 需要兩個無界的堆疊,一個比較 與 的個數,另一個比較 與 的個數,而第二個堆疊並不屬於 PDA 模型。
常見錯誤
(不封閉不等於每個交都不是上下文無關語言)
不封閉的含義是:至少存在一對語言,其交落在該類之外;上下文無關語言的許多具體的交仍然是上下文無關的。同樣,補運算的論證是相對於共同字母表進行的,並且用到了並運算的封閉性。它並不表示每一個上下文無關語言的補集都不是上下文無關的。
逐個轉移地構造乘積
設 PDA 的控制狀態集為 ,其轉移關係包含形如 的移動,其中 為輸入符號或 。乘積的控制狀態是 中的對 。對讀入輸入的移動,加入
對靜默移動,加入
起始狀態由兩個起始狀態配對而成,初始堆疊保持不變。當且僅當 是 PDA 的終結狀態且 是 DFA 的終結狀態時,乘積狀態才是終結狀態。這些規則複製了 PDA 的每一個選擇,並加上由所消耗符號唯一決定的 DFA 更新。
乘積的證明分兩個方向。給定 PDA 在某個詞上的一次運行,DFA 在該詞上的唯一運行決定了每一步的第二個分量,從而得到一次乘積運行。反過來,把任何乘積運行投影到其 PDA 分量上,得到一次有效的 PDA 運行,並且透過歸納可知其 DFA 分量遵循正確的輸入前綴。因此兩個包含關係都不是預先假定的:交中的每個詞都有一次接受的乘積運行,而每一次接受的乘積運行都見證了該詞同時屬於兩個語言。
例題 2.8.8
(靜默移動不改變奇偶性)
設 DFA 記錄已消耗的 的個數是偶數還是奇數。若 PDA 在其 DFA 分量為奇時執行一次彈出堆疊符號的靜默轉移,則乘積仍保持為奇。只有讀入 才會翻轉奇偶性;讀入 或執行靜默移動都使其不變。若在靜默移動上推進 DFA,就等於給一個從未被讀入的符號賦予了奇偶性。
DFA 必須是完全的,上面所示的轉移規則才對每個輸入符號都有定義。部分 DFA 可以先用一個非接受的陷阱狀態補全;在「缺失的轉移即拒絕」的通常約定下,這樣做保持其語言不變。如果兩部機器是在不同的字母表上給出的,應先確定一個共同的字母表,並一致地解釋缺失的符號。否則,連補集的全集或所要的交都可能不明確。
泵引理中的量詞
上下文無關泵引理指出:若一個語言是上下文無關的,則存在泵長度 ,使得該語言中每個足夠長的詞都有某個允許的分解,使所有被泵出的詞仍留在該語言中。要導出矛盾,須選取一個合適的長詞,並證明每一個允許的分解都至少對某個泵指數失效。只挑選一個方便的分解並說明它失效,並不與引理的存在性結論相矛盾。
對 ,長度至多為 的片段不可能同時含有 與 :任何這樣的片段都包含中間整個由 個 構成的塊,以及兩側相鄰塊各至少一個符號。因此在刪去 與 時,三個符號計數中至少有一個不受影響。由於 ,其餘計數中至少有一個減少。未受影響的計數仍為 ,所以三個計數不可能全部相等。這一論證涵蓋了被泵的部分落在一個塊內或跨越單個邊界的各種情形;它不需要對每個位置逐一列出單獨的分解。
常見錯誤
(泵引理是必要條件,而不是刻畫)
泵引理給出的是上下文無關性的必要條件,而不是完整的刻畫。一個語言對某個特定分解、甚至對某個擬定的泵長度滿足泵性質,並不自動意味著它是上下文無關的。在本證明中,矛盾來自對所選的詞、引理所允許的全部分解所作的全稱分析。
交與補
對固定的有限字母表,上下文無關語言類包含空語言與 ,且對有限並封閉。要把兩個文法合併為並,先重新命名變元使兩者不相交,再引入一個全新的起始變元,讓它選擇任一舊的起始符號。變元重新命名可防止一個文法的產生式意外地展開屬於另一個文法的變元。這一構造接受的是並而不是交:最初的選擇每次只沿著一個文法進行。
德摩根這一步是關於類性質的反證法。如果每個上下文無關語言的補集都是上下文無關的,那麼公式中的兩個補集都是上下文無關的。並運算封閉性使它們的並是上下文無關的,再次使用補運算封閉性就使交是上下文無關的。由於那個明確給出的交不是上下文無關的,所假定的普遍補運算封閉性不可能成立。該論證保證存在某個上下文無關語言,其補集不是上下文無關的,但它本身並不能確定兩個中間補集中究竟哪一個提供了具體的見證。
例題 2.8.9
(正則過濾器可以保持較簡單的交)
設 ,這是一個正則語言。 與 都已是 的子集,所以分別將其中任一個與 相交,都使它保持不變,仍然是上下文無關的。但這並不意味著它們彼此的交是上下文無關的。乘積定理一次只允許一個上下文無關語言與一個正則過濾器;除非已知第二個語言是正則的,否則無法對它應用該定理。
接受方式與確定性的適用範圍
該構造保持了終結狀態接受,因為它在整個輸入讀完之後檢查兩個終結控制狀態。如果 PDA 原來是以空堆疊接受給出的,應先使用有效的轉換化為所採用的約定,或者針對該約定重新陳述並證明乘積構造。對確定性機器而言,接受方式的轉換須格外小心:額外加入的非確定性清理選擇可能破壞確定性。這裏關於確定性乘積的斷言從一個確定性的終結狀態接受機器出發,不依賴這樣的轉換。
DFA 分量不增加無界的儲存:只有 個控制狀態對,而乘積只有 PDA 堆疊的一份副本。這就是該構造保持在 PDA 模型之內的原因。第二個任意的堆疊將是另一種機器模型,所以「可以直接把兩個 PDA 並行運行」這種直覺性的說法,並不構成上下文無關語言對交運算封閉的證明。
常見錯誤
(反例中的兩個運算元都是上下文無關語言)
不封閉的見證並沒有斷言 或 不是上下文無關語言;明確的文法顯示情形恰好相反。產生非上下文無關語言的,是它們的交需要同時滿足兩個配對約束。這一區分在設計歸約時很有用:在利用運算對象的組合去反駁某個全稱的封閉性質之前,應先證明這些運算對象確屬所聲稱的類。
總結
DFA 可以與 PDA 結合:把它的有限狀態存放在控制部分中,並且只在消耗符號時更新它。兩個上下文無關的配對語言的交可以是 ,這證明無限制的上下文無關語言交運算封閉與補運算封閉都不成立。
練習
快速檢查
(在乘積構造中,PDA 執行靜默移動時,DFA 的狀態會怎樣?)
比較靜默移動消耗了甚麼,以及甚麼會令 DFA 前進。
解答 · 答案
它保持不變,因為沒有消耗任何輸入符號。
快速檢查
( 是否屬於 ?是否屬於 ?)
對照 與 的定義,數一數 、、 的個數。
解答 · 答案
它不屬於 :有兩個 而有三個 。它也不屬於 :三個 與零個 的個數不同。
快速檢查
(為甚麼長度至多為 的片段不可能與 的三個塊都相交?)
塊與 塊之間是哪一塊?
解答 · 答案
要同時與 塊和 塊相交,必須跨越中間整個 塊,並在兩側各至少包含一個符號,其長度大於 。
快速檢查
(除補運算之外,德摩根論證中還用到了哪一個封閉性質?)
哪種運算能把兩個文法合成一個?
解答 · 答案
並運算的封閉性,加上共同的補集全集,藉德摩根恆等式得出交運算的封閉性。