動機
對於上下文無關文法,可以透過標記可產生(productive)變元來檢驗其語言是否為空。我們自然會問:它是否生成其終結符字母表上的全部詞?或者兩個這樣的文法是否生成相同的語言?這些問題的答案截然不同。我們將把 Post 對應問題歸約到文法普遍性問題,並明確說明歸約的方向。
該構造使用一個分隔符和一個反向排列的骨牌編號列表。下推自動機可以把一個詞與這些編號所指定的連接結果由右至左進行比較。更微妙的是,它還可以接受每一個格式錯誤或不匹配的字串。這兩種不匹配語言的聯集恰好在不存在對應匹配時是普遍的。
定義
定義 5.5.1
(Post 對應問題實例與解)
一個 Post 對應問題實例含有有限多塊骨牌 ,,其上、下詞都是有限字母表 上的非空詞。一個解是一個非空序列 ,使得 。配套的不可判定性一章證明了:在這種詞非空的約定下,判定解是否存在仍然是不可能的。
定義 5.5.2
(編碼的匹配語言)
設 為一個與 不相交的編號符號字母表,設 為一個全新的分隔符,並令 。定義
編號符號是終結符,即使它們顯示的名稱看起來像整數。各字母表互不相交,因此當一個字串具有預期的語法時,其分隔符位置和編號後綴是唯一確定的。
定理
定理 5.5.3
(普遍性的不可判定性)
不存在這樣的算法:給定一個上下文無關文法及其所述的有限終結符字母表,判定其語言是否為該字母表上全部詞的集合。
定理 5.5.4
(可有效構造的不匹配語言)
由這些骨牌可以有效地構造出 與 的上下文無關文法。因此可以構造出 的文法。
我們使用配套的「下推自動機到文法」的有效構造,以及上下文無關語言對聯集運算的封閉性。我們把不匹配下推自動機描述得足夠明確,以便證明它的行為;不假定上下文無關語言對補運算封閉。
證明
檢測不匹配的堆疊機
下面證明「可有效構造的不匹配語言」這一定理。
證明
(不匹配語言的確定性堆疊機)
對於上方詞 ,構造一個帶有永久堆疊底部標記的確定性下推自動機。在讀到分隔符之前,它把 中的每個符號壓入堆疊。輸入在此前綴模式下結束時為接受:不含分隔符的字串不屬於 。在該模式下遇到編號符號或任何其他語法違規,則進入一個接受陷阱狀態,並消耗餘下的全部輸入。
讀到第一個 時,轉入一個就緒狀態;若此時輸入結束,該狀態也是接受的:因為尚未出現任何編號,而 要求至少有一個編號。讀到編號 時,開始一串有限的 轉移,把 逆序地與堆疊頂部比較。有限控制部件記錄當前在固定詞 中的位置。對每個期望的符號,彈出一個匹配的堆疊符號;若發生不匹配,或過早到達堆疊底部標記,則進入接受陷阱狀態。每個骨牌詞都是有限的,因此這個比較階段總會結束。
比較成功後,一次對堆疊的 檢查會選擇兩個就緒狀態之一。若堆疊底部標記已暴露,則剛讀入的編號後綴恰好描述了到目前為止壓入的詞;若此時輸入結束,這個就緒狀態是拒絕的。再讀入任何編號都會進入接受陷阱狀態,因為每個骨牌詞都非空,而堆疊中已無剩餘符號。若堆疊底部標記未暴露,則該就緒狀態在輸入結束時是接受的,因為仍有未匹配的前綴。它可以讀入另一個編號並開始下一個有限的比較階段。編號後綴中出現分隔符或 的符號則屬格式錯誤,進入接受陷阱狀態。
所有臨時的比較狀態與堆疊檢查狀態都是非接受狀態。這在剛消耗完最後一個輸入符號時十分重要:是否接受由有界的 階段穩定之後決定,而不是由某個中間狀態決定。每個就緒狀態只有消耗輸入的轉移,每個臨時狀態只有針對當前堆疊符號的指定 轉移,因此不存在非確定性選擇或衝突的轉移。如通常那樣,接受意味著在全部輸入被消耗之後到達一個接受狀態。
如果輸入具有預期語法且等於 的某個元素,則每次比較都匹配,並且堆疊恰好在最後一個編號之後變空,使機器處於拒絕的就緒狀態。如果某個字母不同、堆疊過短、輸入結束時堆疊過長,或者在堆疊恰好耗盡之後又來了更多編號符號,機器就接受。缺少分隔符、缺少編號以及格式錯誤的符號同樣被接受。因此它恰好接受 。
對 採用同樣的構造,則接受 。這是一個可有效構造的有限下推自動機:其比較狀態由有限的骨牌詞所決定。配套的構造把它轉換為上下文無關文法。再添加一個全新的聯集起始符號來合併這兩個文法,得到文法 ,其語言為
證明透視
從右側比較連接結果
分隔符之後的第一個編號是 ,所以機器逆序彈出 ;然後逆序彈出 ,如此類推。在非空編號後綴之後堆疊恰好被耗盡,等價於原來由左至右的前綴就是 。此處默默用到的唯一假設是每個骨牌詞都非空:一旦堆疊只剩底部標記,再讀入任何編號都必須彈出一個不存在的符號,所以只能進入接受陷阱狀態,不可能出現第二個拒絕的格局。
從對應問題的歸約
普遍性的不可判定性由下面的歸約得出。
證明
(從 Post 對應問題的歸約)
如果 Post 實例有解 ,則其公共詞後接 同時屬於 和 。它不在 中,所以 不是普遍的。反過來, 中的字串在兩側具有相同的顯式反向編號後綴。把該後綴反轉即確定了同一個非空編號序列,而兩個前綴相等就是一個 Post 解。因此
該構造是有效且有限的。若存在普遍性判定器,則把它應用於 ,並把它的是/否答案取反,就能判定該 Post 實例是否有解。這與所述的不可判定性前提相矛盾。對判定問題的歸約而言,答案取反是無害的,但必須明確說明:存在匹配使文法非普遍。
包含與等價的推論
推論 5.5.5
(包含與等價的不可判定性)
不存在這樣的算法:給定同一終結符字母表上的兩個上下文無關文法,判定第一個的語言是否包含於第二個的語言;也不存在判定兩個語言是否相等的算法。即使要求其中一個文法生成該字母表上的全部詞,這兩個問題仍然不可判定。
證明
(把普遍性歸約到包含與等價)
的文法可以有效構造,例如用一條起始規則,它要麼停止,要麼產生一個終結符再接起始符號。如果一個上下文無關文法的語言是否包含於另一個上下文無關文法的語言是可判定的,那麼檢驗 就能判定普遍性。同樣,若兩個上下文無關文法的等價性可判定,就能判定 是否成立。因此一般的上下文無關文法包含問題與等價問題都是不可判定的。
第一個論證在包含關係的左側使用的是一個正則語言。它並不蘊含相反方向的包含問題(左側為任意上下文無關語言、右側為正則語言)也不可判定。後一問題可以藉助正則語言的補運算、上下文無關語言與正則語言的交運算,以及上下文無關語言的空性判定來處理。
例題詳解
例題 5.5.6
(一塊相匹配的單骨牌)
取一塊骨牌 。詞 同時屬於 和 ,因此被排除在所構造的不匹配語言之聯集之外。該文法不是普遍的,這與單骨牌解的存在性相符。
例題 5.5.7
(僅在一側不匹配)
對於單骨牌 ,字串 屬於 但不屬於 。下方的不匹配機接受它,所以聯集文法包含它。這個字串不能見證非普遍性。
例題 5.5.8
(反向的編號順序)
設上方詞為 與 。編號序列 給出 。壓入 之後,機器讀到 並彈出 ,再讀到 並依次彈出 和 。堆疊恰好在末尾變空。
例題 5.5.9
(不完整的前綴)
只有一塊上方骨牌 時,字串 在唯一的編號之後仍在堆疊中留下一個 。它不屬於 ,非堆疊底部的就緒狀態在輸入結束時接受這個不匹配。相比之下, 以堆疊底部標記結束,被該不匹配機拒絕。
常見錯誤
反例模式
取補運算不保持上下文無關性
也許有人會想:上下文無關語言的補集仍是上下文無關語言,因此直接對 的文法取補即可。這在一般情況下是錯的。在 上取上下文無關語言 與 。詞 同時屬於兩者,當且僅當 且 ,所以 ;由上下文無關語言的泵引理可知它不是上下文無關語言。若取補運算保持上下文無關性,而聯集運算也保持,則 (補集在 中取)就會是上下文無關語言,這是矛盾。因此,這裏的證明是為這兩個特定的編碼語言構造專門的不匹配機,並且只在確認兩個不匹配語言都是上下文無關之後才使用聯集。
常見錯誤
(按原來的順序讀取編號後綴)
編號後綴必須反轉。堆疊先暴露最後壓入的符號,所以分隔符之後的第一次比較必須是與最後一塊骨牌的詞作逆序比較。若按原來的順序讀取編號,一般會把錯誤的骨牌與前綴的末端比較。
常見錯誤
(讓臨時狀態決定是否接受)
按所述約定,在仍有輸入未讀時到達某個狀態,本身並不構成接受。這就是為甚麼帶有未匹配堆疊符號的接受就緒狀態之後還可以讀入另一個編號,並可能轉入拒絕的精確匹配狀態。反過來,臨時的 比較狀態也決不能在比較完成之前誤接受一個有效的字串。
兩個包含方向的比較
不可判定的方向是:一個正則語言是否包含於某個上下文無關語言之中。普遍性問題問的是 中的每個詞是否都屬於該文法的語言。相反的方向結構不同。若 是正則語言而 是上下文無關語言,則 恰好當 為空。有限自動機經確定化之後可以取補;它與下推自動機的乘積仍是下推自動機。由此得到的上下文無關語言空性問題,可由配套的可產生性構造判定。
這一比較說明了為甚麼歸約應當明確指出輸入的順序。只寫「包含問題不可判定」會掩蓋一個有用的不對稱性,並可能使讀者推斷每個受限的包含問題都是困難的。上面的證明對一般的文法包含問題建立了不可判定性,即使左側是實例字母表上固定的正則語言 也是如此。
有限控制的實現不需要把骨牌詞存放在堆疊上。每塊骨牌都屬於用來構造機器的固定輸入實例,所以它的符號與當前位置可以編碼在有限多個狀態之中。堆疊中存放的是任意長度的詞前綴。正是這種分工使構造是有效的,同時又容許輸入詞具有無界的長度。一塊骨牌可以含有多個字母,但它的比較階段有固定的有限最大長度。因此在消耗完最後一個編號之後,它不可能永遠停留在僅含 轉移的階段;它要麼檢測到不匹配,要麼到達兩個就緒狀態之一。
總結
一個編碼後的 Post 解恰好就是 中的一個詞。專門的堆疊機透過把反向編號後綴與已壓入的前綴比較,來識別這兩個語言的補集。它們的聯集恰好在不存在匹配時是普遍的。因此,普遍性判定器就能判定 Post 對應問題,而一般的包含問題與等價問題也繼承了這種不可能性。
練習
快速檢查
(對於上方骨牌 ,,編號序列 對應的編碼字串是甚麼?)
先按編號的順序連接上方詞,再把編號按相反順序寫出。
解答 · 答案
連接後的上方詞是 ,反向的編號後綴是 ,得到 。
快速檢查
(為甚麼要求 是一個全新的、既不在詞字母表也不在編號字母表中的符號?)
想一想在編碼字串中,詞的部分在哪裏結束、編號的部分在哪裏開始。
解答 · 答案
它標出詞前綴與編號後綴之間唯一的邊界。各字母表互不相交,使得歸約兩個方向所用的解碼都沒有歧義。
快速檢查
(如果 Post 實例有解,所構造的聯集文法是普遍的還是非普遍的?請解釋。)
看看公共詞後接其反向編號序列,相對於 、 及該文法的語言處於甚麼位置。
解答 · 答案
非普遍。公共詞後接其反向的非空編號序列,同時屬於兩個編碼語言,因此位於它們補集之聯集的外部。
快速檢查
(文法等價性判定器如何能判定 上的普遍性?)
應該把輸入文法與哪一個固定的文法比較?
解答 · 答案
構造 的文法,並檢驗它是否與輸入文法等價。相等恰好發生在普遍的情形。