有限自動機可以用狀態記住有否見過分隔符,但有限個狀態不能獨自記住任意大的開啟符號數目。下推自動機(PDA)增加了一個堆疊。重要的不只是「要推入甚麼」,而是每一步之後,堆疊證明了甚麼事實?不變式讓我們由幾次看似合理的操作,進一步證明對任意長度的輸入都成立。
我們先識別兩個等長區塊;由 a 轉到 b 會顯示何時開始配對。然後考慮沒有分隔符的偶數長度迴文:機器可能要猜測何處停止推入。我們會區分一次猜測失敗,與整個輸入被拒絕。
慣例:構型與接受
定義 9.1.1
(構型記錄甚麼)
構型寫成 ,依次記錄目前狀態、尚未讀取的輸入及堆疊。我們把堆疊頂寫在左邊。底部標記 起初已在堆疊中;下列機器都不會把它彈出。
一次轉移可讀取一個輸入符號,也可讀取 (不讀輸入);它查看堆疊頂,再用有限字串取代該頂部符號。例如以 取代 是推入 ;以 取代 是彈出 。
我們使用終止狀態且輸入讀盡的接受方式:只要存在至少一條有限執行路徑,到達終止狀態且沒有未讀輸入,便接受該單詞。到達終止狀態但仍有未讀輸入,並不構成接受。沒有適用轉移時,該路徑便停止;對非確定性機器,只有在不存在任何接受路徑時才拒絕單詞。
這只是本頁的慣例;其他教材可能把頂部寫在另一邊,或採用不同接受方式。堆疊沒有預先固定的長度上限,但每條有限執行路徑只使用有限個格子。
等長區塊:堆疊記錄未配對的前綴
令
使用推入狀態 、配對狀態 和終止狀態 ;起始構型是 。下表列出全部轉移,其他情況沒有轉移。表中 代表 或 。
| 狀態 | 讀取輸入 | 頂部 | 新狀態 | 以甚麼取代頂部 | 意義 |
|---|---|---|---|---|---|
記下一個未配對的 a | |||||
| 開始配對並彈出 | |||||
再配對一個 b | |||||
| 或 | 結束,保留底部標記 |
特別地, 沒有離開的轉移。即使 中的 非空,仍可提早取 轉移;但這樣有輸入未讀,不能接受。空字串則可直接被接受。
命題 9.1.2
(區塊機器恰好接受等長區塊)
上表的機器由 開始,當且僅當對某個 有 時,接受 。
證明
(堆疊不變式,再證兩個包含方向)
開始配對之前,讀入 個 a 後的堆疊是 。一旦讀入 b,機器便進入 ,不能再讀 a。一條路徑讀入 後,堆疊是 ;路徑存在時必有 。
證明不會多接受:接受路徑若從 進入終止狀態,尚未讀入字母,只得到 ;否則它在讀入 後到達 ,其中 。要進入 ,頂部必須是 ,所以 。接受又要求輸入全部讀盡,因此沒有被忽略的後綴。所接受的單詞必是 。
證明不會漏接受:給定 ,每讀一個 a 推入一次,每讀一個 b 彈出一次,最後取 轉移。 時直接取最後轉移。故 的每個單詞都有接受路徑;兩個方向合起來得到語言相等。
證明透視
機器每一部分的作用
證明依靠一個不變式:在狀態 讀入 後堆疊是 ,在 讀入 後堆疊是 。控制狀態與堆疊分工合作。由 到 的轉換發生在第一個 b,並且沒有回頭的路,所以控制狀態負責限制次序 ;堆疊負責計數,因為只有 時 才在頂部。 永遠不會被彈出,所以「頂部是 」可靠地表示沒有未配對的 a,結束轉移正是以此作為條件。結束轉移不讀入符號,所以接受還要求輸入讀盡,這就排除了在非空字串上提早結束。
每個部分都不可少。若結束轉移不看頂部符號,aab 就會被接受:路徑到達 後便可結束。若把 併入 ,讓 既可推入又可彈出,abab 就會被接受:堆疊依次是 。
常見錯誤
(終止狀態不等於接受)
到達 並不足夠,輸入還必須讀盡。由 取 轉移得到 ,這是終止狀態,但符號 b 仍未讀。若把它當作接受,就會接受不屬於 的 b。只有結束於 且輸入全部讀盡的路徑才算數。
例題 9.1.3
(一條完整路徑和三種失敗原因)
對 aabb,連同狀態及未讀後綴一起記錄:
aab 讀完後在 ,堆疊仍是 ,有一個 a 未配對。abb 的第二個 b 到達時頂部是 ,沒有讀取它的規則。aba 讀過 ab 後已在 ,沒有規則讀最後的 a。提早進入 也不能挽救這些輸入,因為仍有未讀符號。
反例模式
總數相等仍不足夠
斷言:每個 a 與 b 數目相等的單詞都屬於 。abab 有兩個 a 和兩個 b,但不是 的形式。機器拒絕它:,之後在 無法讀入 a;提早轉入 則留下未讀的 ab。堆疊核對數目,次序 則由 轉入 的狀態變化保證;單憑數目不能決定單詞是否屬於語言。
沒有分隔符:猜一個切分,再核對
定義 9.1.4
(倒序與偶數迴文)
對單詞 ,其倒序 是把 倒過來寫所得的單詞。 上的偶數迴文語言為
例如 0110 屬於 ,取 ;010 不屬於 ,因為 的所有單詞長度皆為偶數。空字串也在 中。
使用推入狀態 、配對狀態 和終止狀態 ,起初堆疊為 。 可讀取 0 或 1,並把相同符號推入;也可隨時以不改變堆疊的 轉移切換到 。在 ,只有頂部是 0 才可讀 0,只有頂部是 1 才可讀 1;配對後彈出頂部。最後,僅當頂部是 時,才可用 由 進入 ,並保留 。沒有轉移返回 ,沒有轉移消耗 , 亦沒有離開的轉移。
對固定有限輸入,可能猜的位置只有有限個:最多切換一次,可在單詞符號之間選擇位置。本機器沒有 迴圈。定義要求的是一條接受的有限路徑,不是假設機器能預知未來。
例題 9.1.5
(同一單詞的成功與失敗猜測)
對 0110,先推入頭兩個符號;堆疊成為 ,頂部是 1,未讀輸入為 10。切到 ,配對並彈出 1,再配對並彈出 0。輸入已空而堆疊是 ,進入 ,此路徑接受。
如果在第一個 0 之後便切換,堆疊頂是 0,下一個未讀符號卻是 1,該路徑沒有配對轉移而失敗。單詞仍被接受,因為讀完兩個符號後切換有成功路徑。
命題 9.1.6
(猜測機器恰好接受偶數迴文)
上文所述、含狀態 、、 的機器,當且僅當單詞屬於 時接受該單詞。
證明
(堆疊保存倒序的前綴)
假設一條路徑在讀過前綴 後切換。推入規則令堆疊成為 。配對階段每讀一個符號,都要與目前頂部相同並彈出它。進入 前, 上面的符號必須全部移除;接受又要求輸入全部讀盡。因此剩餘輸入恰好是 ,每個被接受的單詞都有 的形式。
反過來,對任意 ,在讀完 時選擇切換。此時堆疊是 ,第二半依序配對並移除堆疊符號;輸入讀盡並只餘 後,最後轉移便接受。 也適用。因此機器識別的正是 。
證明透視
為何一次成功的猜測就足夠
這個證明是不對稱的,而這種不對稱正是非確定性的意思。證明不會多接受時必須涵蓋每一條路徑,所以從任意切換位置 出發,證明單詞是 。證明不會漏接受時只需一條路徑,所以給出讀完 後的那一次切換即可。只要有某個切分成功,單詞就被接受;失敗的切分無關緊要。
不變式是:推入 後,由頂部往下讀,堆疊是 。堆疊以相反次序交還符號,這正是後半部必須被讀取的次序。轉入 時「頂部是 」的條件保證每個被推入的符號都已配對。若沒有它,路徑 便會接受 0,一個長度為奇數的單詞。切換只會發生一次,因為沒有轉移回到 。
例題 9.1.7
(兩部機器所接受的最短單詞)
對等長區塊機器,空字串只用結束轉移:;ab 的路徑是 。對迴文機器,空字串需要兩次 轉移:;00 在讀入一個符號後切換,路徑是 。每種情況下,堆疊最後都是 而輸入讀盡。空字串是邊界情況:從未推入任何符號。
反例模式
一條失敗路徑並非拒絕的證明
對 0110,在第一個符號後猜中點會失敗,但在第二個之後猜則成功。要證明拒絕,必須涵蓋所有切分。對 010,若一條路徑成功,推入與稍後彈出的輸入符號數必須相等,因此總長必須是偶數。它的長度是三,所以所有切分都失敗;不能只憑一條失敗軌跡作此結論。
常見錯誤
(堆疊會倒序,所以 不等於 )
這部機器識別的是 ,不是 。單詞 0101 等於 (),卻被拒絕:唯一前後等長的切分在兩個符號之後,此時堆疊是 、頂部為 1,而下一個輸入符號是 0;其他切分都因長度或不匹配而失敗。後半部必須是前半部的倒序。
若輸入改為含有單一分隔符的語言 ,階段邊界便可見:在 # 之前推入、讀到 # 時切換,然後配對後綴。例如 0#0 被接受。分隔符必須恰好出現一次,且後綴仍須完全配對。這個比較解釋了猜測的用途,本身並不證明其他語言的一般確定性或非確定性定理。
檢查理解
快速檢查
(追蹤等長區塊機器處理 aabb。第一個 b 之前及之後的堆疊分別是甚麼?)
解答 · 答案
第一個 b 前,狀態是 ,堆疊是 。讀取它時彈出一個 並進入 ,留下 。第二個 b 後剩下 ;此時輸入也已讀盡,最後轉移才可接受。
快速檢查
(等長區塊機器接受 abba 嗎?用未讀輸入解釋。)
解答 · 答案
不接受。讀過 ab 後,機器在 、堆疊為 ,未讀輸入是 ba,它不能讀下一個 b。雖然可用 進入 ,但 ba 仍未讀,而 沒有離開的轉移,因此不存在接受路徑。
快速檢查
(對 1001,給出迴文機器的一個成功切分,以及切分時的堆疊。)
解答 · 答案
取 。先後推入 1 和 0 後,堆疊是 ,頂部為 0。餘下 01 依次配對並彈出這兩個符號;輸入讀盡、堆疊為 ,轉入 後接受。
快速檢查
(迴文機器在 0011 的 00 之後切換會接受嗎?其他切分有幫助嗎?)
解答 · 答案
讀過 00 後頂部是 0,下一符號是 1,所以該切分失敗。每個推入的符號都必須由一個後來的符號配對並彈出,因此任何接受切分都必須把四個符號分成等長兩半。唯一可能成功的是兩個符號後切換;它失敗了,所以 0011 被拒絕。
兩個例子以相同的堆疊原則處理不同問題:等長區塊利用可見的輸入變化開始配對;偶數迴文則非確定地選擇切分。每次證明都指出不變式,證明接受的單詞必有指定形式,再為語言中的每個單詞構造成功路徑。