動機
下推自動機可以這樣描述:當輸入被讀完並且到達某個終結狀態時接受。另一種常見約定是:當輸入被讀完並且堆疊為空時接受。這兩種定義看似要求不同的東西:終結狀態不必對應空堆疊,而空堆疊也未必能揭示控制狀態。對於非確定性的機器,這兩種約定所識別的語言類是相同的。下面的轉換說明了額外的非確定性選擇究竟用在何處,以及為何必須引入一個全新的堆疊底部標記。
這個等價性討論的是由可能不同的非確定性機器所識別的語言,而不是把兩種接受判定應用於同一部機器。它亦並不斷言確定性下推自動機在這兩種約定下具有相同的表達能力。我們首先固定一個精確的模型,使各個構造可以被逐一檢驗,而不必依賴非形式化的堆疊示意圖。
定義
定義 2.1.1
(非確定性下推自動機及其轉移)
一部非確定性下推自動機具有有限的狀態集 、有限的輸入字母表 、有限的堆疊字母表 、起始狀態 以及初始堆疊符號 。一條轉移 讀入 ,彈出堆疊頂部符號 ,壓入字 (其最左端符號位於堆疊頂部),並將狀態由 改變為 。只要輸入符號與堆疊頂部符號相符,就可以選擇該轉移。一次計算是有限的;即使仍有可用的轉移,計算也可以停止。
定義 2.1.2
(格局與兩種接受約定)
格局 由當前狀態、尚未讀入的輸入以及堆疊組成,堆疊內容由頂部寫起。標記為 的轉移不消耗輸入。在此模型下,堆疊為空時沒有任何轉移可用,因為每條轉移都需要一個堆疊頂部符號。若存在某個有限計算到達 且 為終結狀態(無論 為何),則稱機器按終結狀態接受。若存在某個有限計算到達 (無論 為何),則稱機器按空堆疊接受。兩種情形下,整個輸入都必須被讀完。
定理
定理 2.1.3
(終結狀態到空堆疊)
對於每部按終結狀態接受的非確定性下推自動機 ,都存在一部按空堆疊接受的非確定性下推自動機 ,它們的輸入語言相同。
定理 2.1.4
(空堆疊到終結狀態)
對於每部按空堆疊接受的非確定性下推自動機 ,都存在一部按終結狀態接受的非確定性下推自動機 ,它們的輸入語言相同。
證明思路
證明
(由終結狀態到空堆疊:先複製,再清理)
兩種構造都先引入一個不屬於 的堆疊符號 以及一個全新的起始狀態。在 且堆疊頂部為 時,新機器把它替換為 並進入 。新機器的初始堆疊只含 。在模擬過程中,每條原有轉移都作用於 之上的原堆疊部分,既不能檢查也不能移除該標記。因此,被模擬的堆疊恰好是原堆疊後面接上 。
對於由終結狀態到空堆疊的構造,複製每條原有轉移,並增加一個全新的清理狀態 。對於每個原終結狀態以及 中每個可能的堆疊頂部符號,增加一條進入 的 轉移,並移除該堆疊頂部符號。在 中,對每個可能的堆疊頂部符號增加一條移除它的 轉移。清理階段不消耗輸入,並且可以把整個堆疊清空。若 接受某個字,則 模擬其接受計算,隨後進行清理,因此 按空堆疊接受該字。
反過來, 移除 的唯一途徑是清理,所以一個按空堆疊接受的計算必定是從某個原終結狀態進入了清理。進入清理之前的部分都是原機器的計算。清理階段不讀入輸入,而接受要求輸入已讀完;因此原計算在到達該終結狀態時已經消耗了全部輸入。在輸入尚未讀完時過早地猜測進入清理,不會造成錯誤的接受。這一論證同樣容許原堆疊在終結狀態時為空:此時新標記位於堆疊頂部,清理將其移除。
證明
(由空堆疊到終結狀態:偵測標記)
對於由空堆疊到終結狀態的構造,在 之上模擬 ,並增加一個全新的、唯一的接受狀態 。從每個原狀態出發,增加一條在堆疊頂部為 時進入 的 轉移,例如把 替換為其自身。若 在讀完輸入後清空了堆疊,則 看到標記並進入 。反過來,進入 意味著被模擬的原堆疊為空。由於到達 不消耗輸入,而終結狀態接受要求沒有剩餘輸入,所以一次接受運行對應於 的一次有效的空堆疊接受運行。新機器可能過早地猜測進入 ,但這樣的分支在仍有未讀輸入時無法接受。從 出發不需要任何轉移。
證明透視
標記是一個不變式
在每個被模擬的格局中,新堆疊就是舊堆疊再附上全新的標記。因此,看到標記意味著舊堆疊為空;看到舊符號則意味著舊堆疊非空。標記是全新的,所以永遠不會與原有符號混淆。
例題詳解
例題 2.1.5
(終結狀態下堆疊中仍有剩餘)
設原機器讀入 後到達終結狀態 ,此時堆疊為 。在終結狀態接受的約定下,它接受 ,儘管堆疊中還剩兩個符號。所構造的空堆疊機器到達對應的堆疊 ,進入清理,依次彈出 、、。只有在輸入已被讀完且這三個符號都已消失之後,它才接受。
例題 2.1.6
(過早猜測清理會失敗)
設對於輸入 ,在讀入第一個符號之後到達了同一個終結狀態,此時 尚未讀入。清理可以移除堆疊中所有符號,但它無法讀入 。所得格局堆疊為空而輸入未讀完,因此不接受。原機器的另一個分支仍可能接受 ;單憑這個失敗的清理分支,無法對這種可能性作出任何判斷。
例題 2.1.7
(偵測最後一次彈出)
設某部原空堆疊機器在讀入 之後到達 。模擬器則到達 。它通向全新終結狀態的特殊轉移證明了 被按終結狀態接受。若標記出現時仍有剩餘輸入,同一條轉移雖然可以執行,但所得分支無法通過輸入讀完的檢驗。
常見錯誤
反例模式
同一部機器可以給出不同的答案
斷言:下推自動機按終結狀態接受某個單詞,當且僅當它按空堆疊接受該單詞。取一部起始狀態為終結狀態、初始堆疊為 且沒有任何轉移的機器。空單詞被按終結狀態接受,因為 的未讀入輸入為空且狀態是終結狀態。它卻被按空堆疊拒絕,因為堆疊 非空,而且沒有任何轉移能把它移除。定理構造的是另一部機器,並沒有把這部機器上的兩種接受檢驗等同起來。
常見錯誤
(把原有的堆疊符號當作標記)
取一個狀態 、初始堆疊符號 ,以及唯一的轉移 。堆疊永遠不會變空,所以空堆疊語言為空。假設某個轉換把「堆疊頂部符號是 」當作「原堆疊為空」,並在這項檢驗成立時進入終結狀態 。那麼新機器立刻接受 ,並且在壓入一次之後也接受 ,但這兩個單詞都不在該語言中。標記必須是全新的,即任何原有轉移都不會提及的符號,這樣它就永遠不可能在原堆疊底部之上再次出現。此外,帶著未讀入的輸入而到達終結狀態或清空堆疊,並不滿足本節所定義的任何一種約定。
常見錯誤
(清理階段不得讀入輸入)
取一部起始狀態為終結狀態、初始堆疊為 且沒有任何轉移的機器,其按終結狀態接受的語言為 。若容許清理狀態在彈出的同時讀入字母,則構造出的機器可以從終結的起始狀態以 移動彈出 ,再一邊讀入 一邊彈出 ,在輸入耗盡時堆疊為空。它會接受 ,而 並不在該語言中。清理轉移不讀入輸入,也不能回到模擬階段;正是這一點防止了這種情形。
解讀模擬不變式
模擬證明比較的是兩個格局,而不僅僅是兩張轉移圖。這裏的關係是:舊機器處於狀態 、未讀輸入為 、堆疊為 ,當且僅當模擬器可以處於同一個原狀態 、同一個未讀輸入 、堆疊為 ,並且遵循相同的轉移選擇。初始化對 、完整輸入和 建立了該關係。每條原有轉移都保持該關係,因為它只移除並替換堆疊頂部的原符號。保持不變的後綴包含標記。對原有轉移的次數進行歸納,即可證明該關係對每個有限的模擬運行都成立。
反方向則需要排除新增的轉移。在第一個構造中,進入清理之前,模擬器只用到被複製的轉移,因此從該前綴中擦去標記便得到一個有效的原計算。進入清理之後,它無法回到任何原狀態。在第二個構造中,進入全新終結狀態之前,模擬器只用到被複製的轉移,而對標記的偵測證明了對應的舊堆疊為空。把兩個方向都陳述清楚,就排除了意外引入舊機器所沒有的接受運行的可能。
即使舊機器有無窮多個可用的移動,或者其有限轉移圖中含有環,這一論證仍然成立。接受是按存在一個有限接受計算來定義的。證明複製的是這一有限序列,再加上有限多個準備或清理步驟。它既不聲稱每個非確定性分支都會終止,也不聲稱可以透過等待所有分支來判定不接受。語言等價是關於存在接受分支的陳述。
例題 2.1.8
(一次壓入後接兩次彈出)
設 在輸入 時把 替換為 ,然後一條在輸入 時彈出 的轉移,接著一條彈出 的 轉移。沿這次特定運行,舊堆疊依次為 、、、空。模擬器的堆疊依次為 、、、。只有在最後一次原有彈出之後,才可能進行對標記的最終偵測。若這些轉移在讀入 之後導致空堆疊接受,則新的終結狀態構造同樣接受 。
為甚麼非確定性選擇很重要
在第一個構造中,原終結狀態可能帶有繼續模擬的轉移。新機器既要有繼續模擬的選項,也要有進入清理的選項。即使還有可用的轉移,一次原接受計算也可以在終結狀態處停止;模擬器猜測此刻就是恰當的時機。其他的猜測可能失敗,但非確定性接受只要求有一個分支成功。這是一個存在性的斷言,而不是保證每個分支都能選對時機。
第二個構造同樣是在其餘位置保留被複製轉移的同時,增加一條針對標記的轉移。標記具有特殊含義,因為原轉移關係無法提及它。這條額外轉移是否可用,取決於模型的堆疊約定,這正是我們明確規定轉移必須有堆疊頂部符號的原因。在容許轉移不檢查堆疊的表述中,這一構造需要相應的調整;證明不能簡單地假定看到標記就會阻止所有原有轉移。
有些表述容許轉移壓入一個字,並令其最右端符號位於堆疊頂部。在這種約定下,所給出的初始化字必須反轉,使原初始符號位於標記之上。這只是記號上的改變,而不是新的數學定理。重要的是關於堆疊中相對次序的不變式,而不是某本教科書所選擇的書寫次序。
檢驗一個轉換
要驗證一個給定的構造,首先檢查新的起始狀態是否只有預期的準備轉移,且標記是否不同於任何原有堆疊符號。接著驗證每條被複製的轉移都不觸及標記。然後準確找出哪些新狀態與新轉移可以導致接受,並分別證明兩個方向:把任何舊的接受運行加以擴展,並把任何新的接受運行追溯回舊的接受運行。最後檢查輸入是否讀完。這些步驟可以暴露常見的錯誤,例如容許清理讀入輸入、容許清理返回到模擬階段,或者用舊的堆疊符號充當標記。
對於同一個字,轉移系統可以有多條接受運行。這些轉換保持的是成員關係,而不是運行的條數、運行的長度或堆疊的形態。特別地,舊的終結狀態接受運行可能在多個時刻訪問終結狀態,新機器可以在每一個時刻嘗試清理。即使原機器是無歧義的或確定性的,也不能斷言所構造的機器具有這些性質。
總結
全新的堆疊底部標記使模擬器能夠識別原堆疊何時變空。非確定性地切換到清理,把終結狀態轉化為空堆疊接受;對標記的偵測則把空堆疊轉化為終結狀態。兩個方向的等價性都依賴於讀完整個輸入。
練習
快速檢查
(一部機器從終結狀態出發,堆疊為 ,且沒有任何轉移。它在兩種約定下各接受甚麼?)
解答 · 答案
按終結狀態,它恰好接受 。按空堆疊,它甚麼也不接受:其初始堆疊非空,且沒有任何轉移可以彈出它。
快速檢查
(為甚麼在第一個構造中,帶著未讀輸入進入的清理分支不能接受?)
解答 · 答案
清理只有 轉移。它無法消耗剩餘的輸入,而空堆疊接受要求輸入已被讀完。
快速檢查
(在第二個構造中,模擬期間 位於堆疊頂部意味著甚麼?)
解答 · 答案
被模擬的原堆疊為空。原堆疊的每個符號都應位於全新標記之上,而模擬保持這一不變式。
快速檢查
(若原機器按終結狀態接受,且堆疊已經為空,說明第一個構造為何仍然接受。)
解答 · 答案
模擬計算結束後,新堆疊只含 。進入清理的轉移彈出該標記,在整個輸入被讀完之後留下空堆疊。