動機
下推自動機可以利用堆疊記住無界的資訊。非確定性還容許它猜測應使用哪一條轉移,或在何處停機。確定性下推自動機取消了這種選擇,但其定義必須同時處理靜默轉移與讀入輸入的轉移:若在同一格局下兩者皆可用,機器仍然面對選擇。
對非確定性機器等價的各種接受約定,在這裏需要更加謹慎。在下面這種沒有結束標記的模型中,空堆疊接受會帶來前綴限制,而終態接受則不會。這一觀察是關於一個精確陳述的模型的定理;加入可見的結束標記會改變機器所能觀察到的內容,因而也會改變論證。
定義
格局是 ,其中 是狀態, 是尚未讀入的輸入, 是堆疊內容,書寫時堆疊頂在左。轉移 讀入 ,把堆疊頂符號 替換為 ,並把狀態改為 。每條轉移都要求存在堆疊頂符號;空堆疊不啟用任何轉移。初始堆疊只含一個符號 。
確定性下推自動機(DPDA)對每個三元組 至多有一條轉移;並且只要對 存在 轉移,則對同一個 就不存在對任何符號讀入輸入的轉移。轉移可以缺失。有限的運行可以停在任何格局。終態接受要求未讀入的輸入為空且當前狀態為終態;空堆疊接受要求未讀入的輸入為空且堆疊為空。輸入末尾不會自動附加任何特殊的結束標記。
若語言 中不存在兩個不同的詞 滿足 (其中 為非空詞),則稱 是無前綴的(prefix-free)。特別地,含有 的無前綴語言不能再含有任何其他詞。
定理
定理 2.9.1
(空堆疊接受的前綴限制)
在上述模型中,每個被 DPDA 以空堆疊方式接受的語言都是無前綴的。
定理 2.9.2
(一個確定性的匹配語言)
語言 在此模型中可被某個 DPDA 以終態方式接受。語言 可被某個 DPDA 以終態方式接受,但在此模型中不能被任何 DPDA 以空堆疊方式接受。
證明思路或證明
證明
(前綴限制、匹配機器與雙詞機器)
假設某個 DPDA 以空堆疊方式接受 ,並設 是另一個輸入,其中 非空。比較對 的接受性有限運行與對 的運行。當該運行讀入 的各個符號時,兩次運行的下一個輸入符號是相同的。若它走一條 轉移,確定性規則禁止在該狀態與堆疊頂符號下存在與之競爭的讀入輸入的轉移。因此較長的輸入會沿著 的接受性運行經過完全相同的轉移,當堆疊變空時 仍未被讀入。空堆疊下沒有任何轉移可用,所以較長的輸入無法被消耗完,也就不會被接受。這就證明了前綴限制。
對於 ,使用狀態 和堆疊符號 。終態為 。僅有的轉移是
轉移是 上唯一的轉移,所以該機器滿足所陳述的確定性條件。起始狀態接受空詞。對於 ,每個 壓入一個 ,其後每個 彈出一個。恰好在讀入了相匹配數目的 之後,標記 露出,靜默轉移到達 。 太少則停在非終態, 太多則在 留下未讀入的輸入,而在 階段之後再出現 則沒有轉移可用。因此所接受的語言恰好就是所述語言。
的 DPDA 如下:起始狀態為終態,第二個狀態也是終態,初始堆疊為 ,唯一的轉移是從第一個狀態讀入 到第二個狀態,同時保持 不變。它恰好接受這兩個詞。該語言不是無前綴的,所以由第一個定理可知,此模型中的任何 DPDA 都不可能以空堆疊方式接受它。
證明透視
為甚麼確定性把兩次運行耦合在一起
證明恰好各用一次下列四項事實。確定性使每個輸入上的運行唯一,所以 上的運行逐步被決定。靜默移動的無衝突規則表示:在 的接受運行的每個格局上,較長的輸入都只有同一個可用的移動,無論它是靜默的,還是讀入 的某個字母。接受運行是有限的,所以比較在有限步之後停止,停在 已全部讀入的格局。最後一項事實是空堆疊接受所特有的:堆疊為空時沒有任何轉移被啟用,所以尚未讀入的 永遠無法被消耗。去掉第二項事實,較長的運行就可能分岔;去掉第四項(改用終態接受),機器就可以繼續讀入,這正是下面的反例得以成立的原因。
例題詳解
例題 2.9.3
(一次成功的堆疊追蹤)
對於輸入 ,匹配機器依次經過
最後一個格局的輸入為空且處於終態。它的堆疊並不為空,而在所選定的接受約定下這是容許的。
例題 2.9.4
(右括號符號過多)
對於 ,機器壓入一次、彈出一次。露出的 迫使靜默轉移到 ,此時仍有一個 未讀入。由於 沒有任何轉移,該詞被拒絕。當仍有輸入剩餘時,僅僅到達終態並不構成接受。
例題 2.9.5
(在這裏,無前綴只是必要條件)
語言 不滿足空堆疊準則,因為 是 的真前綴。僅憑該準則並不能為每個無前綴語言給出空堆疊 DPDA:無前綴語言的數量遠多於可以有限描述的機器。該定理是必要條件,而不是針對任意語言的構造。
常見錯誤
反例模式
前綴限制對終態接受不成立
斷言:每個被 DPDA 以終態接受的語言都是無前綴的。取狀態 ,兩者皆為終態,起始狀態為 ,初始堆疊為 ,只有一條轉移 。這台機器是確定性的。在空輸入上它已處於終態且未讀入的輸入為空,所以 被接受。在 上它走 ,這是終態且沒有未讀入的輸入,所以 被接受。因此被接受的語言是 ,其中 是 的真前綴。前綴定理的證明恰好在最後一步失效:終態不會禁止後續的移動,而空堆疊會。正確的說法是針對空堆疊接受的那一條。
常見錯誤
(只檢查每組(狀態、字母、堆疊頂符號)至多一條轉移)
若某個狀態與堆疊頂符號既容許 轉移又容許 轉移,則在以 開頭的輸入上兩種移動都可用。例如 與 各佔一個不同的三元組,但格局 既可以走到 ,也可以走到 。即使每個單獨的轉移條目只含一個目標,該機器仍然是非確定性的。
常見錯誤
(在附加結束標記之後仍套用前綴定理)
設每個輸入後面附加一個標記 ,並以空堆疊接受。取狀態 ,初始堆疊 ,轉移 、、。沒有任何狀態有 轉移,而且 的兩條轉移讀入不同的字母,所以機器是確定性的。它接受 (讀入 後堆疊被清空)和 (在 讀入 後堆疊被清空),所以去掉標記後所接受的詞集 不是無前綴的。該定理針對的是本單元的無標記模型,不能原樣搬到有標記的模型。
前綴論證依賴於沒有結束標記。若在輸入之後附加一個不同的標記,機器就能分辨 的結尾與 的下一個符號之間的差別;該證明不能原樣套用。非確定性的接受方式轉換構造可能在清理與繼續模擬之間引入一個選擇,因此它不會自動保持確定性。
確定性作為對格局的條件
定義中的第一個條件排除了對同一狀態、堆疊頂符號與輸入標籤出現兩個不同目標的情形。第二個條件排除了靜默移動與輸入移動之間較為隱蔽的衝突。若兩條輸入轉移的標籤不同,則至多一條與下一個輸入符號匹配,因此它們不衝突。若輸入為空,則沒有讀入輸入的移動可用,但靜默移動仍可能可用。該規則是針對每個狀態與堆疊頂符號整體規定的,所以機器在較長輸入上的行為不會僅僅因為那個輸入還有下一個字母而出現分歧。
確定性並不意味著每個格局都有可用的轉移,也不意味著每次計算都會停機。缺失的轉移可以拒絕某個輸入。機器也可能有無限的靜默移動序列,例如在同一狀態下把 替換為 的轉移。按照接受的定義,只有存在有限的接受性運行時,詞才被接受。對於某個輸入上具有無限靜默迴圈的確定性機器,它在該輸入上不一定給出會終止的是或否的回答。關於算法判定某語言的論斷必須另行證明停機。
第一個定理並不假設機器在所有輸入上都停機。它從對 的一次有限接受性運行出發,證明較長的輸入被迫沿著這段有限的轉移前綴運行。隨後在此模型中,空堆疊使所有後續移動停止。即使其他輸入會導致無限的靜默迴圈,它們也不影響這個論證。
例題 2.9.6
(靜默轉移與輸入轉移的衝突)
假設 與 同時存在。在格局 下,機器既可以靜默地移到 ,也可以讀入 並移到 。因此按定義它不是確定性的。去掉其中一條轉移可以消除這一特定衝突,不過其餘每一個狀態與堆疊頂符號的組合仍須逐一檢查。
驗證匹配機器
用狀態不變式來檢查這個構造,比起非正式地說「堆疊在計數」要容易得多。在 中,讀入了 個連續的 且沒有 之後,堆疊為 。在 中,讀入了開頭的 個 與其後的 個 (其中 )之後,堆疊為 。所列出的每條轉移都保持相應的不變式:壓入使指數加一,彈出使指數減一。
進入 的唯一途徑要求在 中堆疊頂符號為 。此時不變式迫使 。由於 沒有任何出轉移,而接受要求輸入耗盡,所以在接受性運行中不可能再跟隨任何額外的符號。反過來,對每個 ,這些轉移恰好讀入 然後進入 。起始狀態單獨處理 。這就證明了兩個方向的包含關係;僅檢查成功的例子並不能排除多餘的被接受詞。
當堆疊頂為 時,機器在 上讀入 沒有轉移,但在第一次壓入之後該格局是不可達的。在這種部分機器模型中,要證明語言,形式的轉移表不必填滿不可達的條目。隨意添加轉移可能改變語言,或引入靜默與輸入的衝突,所以任何補全都必須明確規定並加以檢查,而不能想當然地認為無害。
無前綴性說明了甚麼、沒有說明甚麼
一個語言可以是無前綴的,卻沒有有限的機器描述。舉一個具體的族:詞 ()兩兩互不為前綴:對 ,較短的詞在某個位置是 ,而較長的詞在該位置仍是 。這個族的每個子集都是無前綴的。由對角線論證,這樣的子集有不可數多個,但在固定的有限編碼下,有限的 DPDA 描述只有可數多個。因此有些無前綴語言根本沒有 DPDA。這個計數論證證明的是存在性;它並未指出某個具體的自然語言,也沒有對確定性上下文無關語言這一類進行分類。
這一結論還依賴於堆疊的約定。在這裏,空堆疊使所有轉移都不可用,所以在以空堆疊方式接受了某個前綴之後,機器無法再讀入非空的後續部分。如果別的形式體系容許在沒有堆疊符號時進行轉移,則證明的最後一步必須重新考慮。定義不僅僅是記號:證明恰好用到了模型所容許的那些操作。
終態並不具有同樣的吸收性質。對於 的機器,容許在作為終態的起始狀態上、輸入為空時停機並接受,但在輸入為 時它可以讀入該符號並到達另一個終態。未讀入輸入必須為空的要求阻止了起始終態立即接受 。這個例子說明,確定性的終態機器可以既接受一個詞又接受它的擴展,而不產生任何矛盾。
結束標記與轉換論斷
假設在每個輸入之後附加一個新的符號 ,它不屬於原字母表。此時 與 的編碼在緊接 之後的位置出現差異:一個是 ,另一個是 的第一個符號。因此機器可以在此處作出不同的確定性決定。先前的前綴證明所比較的兩次運行,在較短詞的接受性運行的全程中看到相同的下一個輸入符號;當較短的運行還必須消耗一個標記時,這種比較就不能以同樣方式適用。
這一觀察並不是關於一般結束標記等價性定理的證明。要證明這樣的結果,必須規定標記何時被讀入、它是否屬於被識別的輸入,以及靜默轉移與堆疊操作如何運作。類似地,從終態接受到空堆疊接受的非確定性構造在終態處加入了一個清理選擇。若一條複製的輸入轉移同時可用,那麼這條額外的靜默移動就違反了 DPDA 的條件。對 NPDA 保持語言不變的轉換,不一定保持這裏所要求的語法上的確定性。
這一區分在閱讀其他教材時很有用。有些教材用終態與結束標記來定義確定性上下文無關語言;有些則採用不同的堆疊約定。在移植某個論斷之前,應當先翻譯定義並檢查其假設。上面證明的具體分離結果適用於本單元所規定的、無結束標記且採用空堆疊接受的模型,並不斷言所有約定下的確定性表達能力都相同。
總結
DPDA 必須像處理輸入移動那樣處理靜默移動。沒有結束標記時,空堆疊接受迫使語言無前綴,而終態接受可以識別非無前綴的語言。當從壓入到彈出的轉換由輸入來標示時,堆疊仍然支持確定性的匹配。
練習
快速檢查
(在 上追蹤匹配機器,並寫出它最終的堆疊。)
沿著證明中列出的轉移走。
解答 · 答案
把 壓入堆疊, 把它彈出,靜默轉移隨即進入 ,此時堆疊為 ,沒有未讀入的輸入。
快速檢查
(匹配機器接受 嗎?請說明。)
數一數 之後還剩下多少個 。
解答 · 答案
不接受。唯一的 之後還剩一個 ,機器停在非終態 ,而在該堆疊頂符號上沒有可用的靜默轉移。
快速檢查
(為甚麼在本模型中沒有任何空堆疊 DPDA 能同時接受 和 ?)
把兩個詞當作字串比較。
解答 · 答案
詞 是 的真前綴,而這類 DPDA 以空堆疊接受的語言都是無前綴的。
快速檢查
(為甚麼無前綴定理並不排除接受 的終態 DPDA?)
定理說的是哪一種接受方式?
解答 · 答案
該定理針對的是空堆疊接受。上面給出的兩狀態終態構造明確地接受這個語言。