動機
有限自動機所描述的語言可能是無窮的,但關於該語言的許多問題,只需檢視一個有限圖便能回答。可達性判定是否存在被接受的單詞;乘積圖用於比較兩部機器;而有用環則區分有限語言與無窮語言。這些算法還會給出證書:一個被接受的單詞、一個區分單詞,或一條可以重複的經過環的路徑。
這裏的機器都是定義在同一有限字母表上的完全確定有限自動機。自動機的底層圖保留帶標號的轉移。搜尋時,可達性不考慮標號,但要把一條路徑還原成單詞,則需要用到標號。
定義
定義 1.3.1
(確定有限自動機與接受)
一個 DFA 是 ,其中 為有限狀態集, 為起始狀態, 為接受狀態集, 為全轉移函數。擴展轉移 透過依次沿 的各個字母轉移來定義。一個單詞被接受,是指從 出發讀完該單詞後停在 中。
定義 1.3.2
(可達、可共達與有用環)
若存在從 出發的路徑到達某狀態,則稱該狀態可達。若從某狀態出發存在路徑到達接受狀態,則稱該狀態可共達。若一個有向環位於某條從起始狀態到接受狀態的路徑上,則稱它是有用的;等價地說,它的各頂點既可達又可共達。環必須至少包含一條轉移。空單詞標記一條長度為零的路徑,但在此處不算作環。
定義 1.3.3
(三個判定問題)
- 空性。輸入:DFA 。輸出: 是否成立;若語言不為空,同時給出一個被接受的單詞。
- 等價性。輸入:同一字母表上的兩部完全 DFA 。輸出: 是否成立;若不成立,同時給出恰被其中一部接受的單詞。
- 無窮性。輸入:DFA 。輸出: 是否無窮;若是,同時給出帶標號的進入路徑、環與離開路徑。
定理
定理 1.3.4
(空性與等價性)
一個 DFA 的語言為空,當且僅當沒有接受狀態可達。定義在同一字母表上的兩個完全 DFA 等價,當且僅當它們的乘積中沒有恰好含一個接受分量的可達狀態。廣度優先搜尋或者判定相應的性質,或者返回一個最短的見證單詞。
證明
(搜尋次序與乘積狀態)
每個單詞標記一條從起始狀態出發的路徑,而每條路徑上的標號也構成一個單詞。該單詞被接受,當且僅當路徑的終點是接受狀態,這便證明了空性判據。廣度優先搜尋按路徑長度非遞減的順序探索狀態;若存在到達接受狀態的路徑,則沿前驅邊可以還原出一條最短路徑。
對於等價性,讀入 之後的乘積狀態為 ,這可對 的長度歸納得到。在區分檢驗中,當一個狀態對恰好有一個分量為接受時,將其標記。若一個被標記的狀態對可達,則到達它的單詞恰好被其中一部機器接受;反之,每個區分單詞都會到達這樣的狀態對。因此,搜尋有限的乘積圖即可判定等價性,並且在不等價時返回一個最短的區分單詞。
證明思路
定理 1.3.5
(無窮性判據)
一個 DFA 的語言是無窮的,當且僅當其轉移圖中存在有用的有向環。若該自動機有 個狀態且其語言是有限的,則每個被接受的單詞的長度都小於 。
證明
(重複有用環,以及鴿巢原理)
若存在有用環,則取一條從起始狀態到環上某頂點的路徑,將環繞行 次,再沿一條路徑走到接受狀態。環的標號長度為正,所以 對應的被接受單詞長度互不相同,語言因此是無窮的。反之,長度至少為 的被接受單詞,其運行過程(包括起始狀態)訪問 個狀態。由鴿巢原理,其中有兩個被訪問的狀態相同。選擇運行過程中首次重複的狀態,從其先前出現處到這次重複之間的轉移構成接受路徑上的非空環,且內部沒有重複狀態。若語言是無窮的,則存在長度至少為 的被接受單詞,因為在有限字母表上,長度更小的單詞只有有限多個。這便證明了逆命題以及有限語言的長度界。
證明透視
環必須是有用的
一個可達的環可以被重複,但僅憑這一點並不能得到被接受的單詞。證明依次用到三個部分:通向環的進入路徑、非空的環,以及通向接受狀態的離開路徑。「有用」正是要求離開路徑能從環自身的頂點出發;下面反例中的拒絕陷阱狀態就不滿足這一點。
還有三項假設在起作用。環必須含有轉移:不同重複次數 對應的單詞互不相同,因為它們的長度相差環標號正長度的倍數。 的有限性推動逆命題:長度至少為 的接受運行訪問 個狀態,鴿巢原理迫使某個狀態重複;選取首次重複,使環落在接受運行之上,所以由此得到的環自動是有用的。最後,長度界用到字母表的有限性,因為比 短的單詞只有有限多個。
例題詳解
例題 1.3.6
(含可達環的空語言)
考慮只有一個狀態的 DFA,該狀態不是接受狀態,並在每個字母上都自環。它有一個可達的環,卻不接受任何單詞。它的環無法共達到接受狀態。由於沒有接受狀態可達,其語言為空,因而是有限的。
例題 1.3.7
(一個最短的區分單詞)
比較接受含偶數個 1 的單詞的二進制 DFA,與接受以 0 結尾的單詞的 DFA。空單詞被奇偶性機器接受,卻被以 0 結尾的機器拒絕。乘積的起始狀態本身已被標記,所以廣度優先搜尋返回 作為一個最短的區分單詞。
例題 1.3.8
(有用環給出無窮多個單詞)
在 上,令起始狀態在 上自環,在 上轉移到一個接受狀態,其餘任何輸入都轉入一個拒絕陷阱狀態。該語言為 。起始狀態處的自環是有用的,因為 轉移可到達接受狀態,重複該自環便產生無窮多個被接受的單詞。
常見錯誤
反例模式
位於所有接受路徑之外的環
一個可達的拒絕陷阱狀態永遠自環,但從它出發無法到達任何接受狀態。重複該自環得到的是無窮多個被拒絕的單詞,而不是無窮多個被接受的單詞。可共達性是必不可少的。
常見錯誤
(狀態數與圖形都不能決定等價性)
兩部自動機的狀態數可以不同,卻識別同一種語言。圖形相同或狀態數相同都不是等價性的檢驗方法。例如,在 上接受所有單詞的單狀態 DFA,與兩個狀態都是接受狀態、並在 上互相轉移的雙狀態 DFA,識別同一種語言 。
常見錯誤
(很長的被接受單詞不代表語言無窮)
有限語言也可以包含很長的單詞:長度界取決於具體那部 DFA 的狀態數,並且只有在已排除無窮性之後才適用。在 上,取鏈 ,後接一個拒絕陷阱狀態,只有 接受,它只接受 。這部自動機有六個狀態,而唯一被接受的單詞比六短。
圖的搜尋
對於空性,從 開始做廣度優先搜尋,沿著每個已發現狀態的每條出邊繼續。每個狀態在首次被發現時標記,並記錄其前驅狀態與轉移標號。若到達某個接受狀態,則沿前驅指標回溯到 並將標號反轉,便得到一個見證單詞。若起始狀態本身就是接受狀態,則見證單詞的長度為零。若搜尋結束時沒有發現接受狀態,則沒有任何單詞能被接受,因為從起始狀態出發的每條轉移路徑都已被探索。
對於無窮性,先標記從起始狀態可達的狀態。然後將每條轉移邊反向,並同時從所有接受狀態出發搜尋。這次反向搜尋所到達的狀態,恰好就是在原圖中能夠到達接受狀態的那些狀態。只考慮被兩次搜尋都標記的狀態,並檢驗由它們導出的有向圖是否有環。深度優先搜尋或強連通分量算法都可以完成這一檢驗。只含一個頂點的分量僅當它有自環時才含環;含至少兩個頂點的分量必含有向環。
如果在該受限圖中找到了環,則兩次可達性搜尋可以提供進入路徑與離開路徑,環的搜尋則提供被重複的片段。它們的標號給出一族具體的無窮多個單詞。進入路徑與離開路徑不必是簡單路徑,儘管可以選取簡單路徑。環每重複一次,單詞長度就增加該環標號的正長度,所以不同的重複次數不可能對應同一個單詞。
例題 1.3.9
(有限語言與無關的環)
在一元字母表 上,令 ,其中 在 上自環,且只有 是接受狀態。該語言為 。三個狀態都可達,但 無法到達接受狀態,所以它的自環不是有用的。既可達又可共達的狀態是 ,它們的導出圖無環。
乘積機與見證單詞的長度
定義 1.3.10
(乘積自動機與被標記的狀態對)
設兩部 DFA 的狀態集為 ,則乘積至多有 個狀態,其轉移為
對於等價性,當且僅當一個分量接受而另一個分量拒絕時,標記該狀態對。乘積本身不必先最小化。不可達的狀態對可以忽略,因為沒有任何輸入能從乘積的起始狀態走到它們。
定理 1.3.11
(最短區分單詞的長度)
若同一字母表上兩部完全 DFA 的語言不同,則存在恰被其中一部接受、長度至多為 的單詞,而且對乘積作廣度優先搜尋會返回一個最短的這類單詞。
證明
(刪去重複的乘積狀態)
若兩種語言不同,則一條最短的區分路徑絕不會重複某個乘積狀態。若重複了,刪去該狀態兩次出現之間的那一段,剩下的帶標號路徑會以更短的單詞到達同一個被標記的終點。因此,最短區分單詞的長度至多為 。
這是乘積構造的一個有限界,並不要求枚舉不超過該長度的每個單詞。廣度優先搜尋訪問的是狀態與轉移,而不是顯式生成所有可能的單詞。
同一個乘積圖只需改變被標記的狀態對,就能支援其他比較。要檢驗 ,標記第一個分量接受、第二個分量拒絕的狀態對。一個可達的被標記狀態對就是包含關係的反例。要檢驗不相交性,標記兩個分量都接受的狀態對,一個可達的被標記狀態對就提供一個公共單詞。正確性論證仍然是對兩個同時進行的運行做歸納;改變的只是對接受條件的詮釋,取決於所問的問題。
完全性與字母表
定義在固定字母表上的完全 DFA 的補,可透過交換接受狀態與非接受狀態得到。完全性很重要:對每個單詞,必須恰好有一條以某個狀態結束的運行。在部分轉移圖中,缺失的轉移通常被理解為拒絕。僅僅交換接受標記,並不能把這種缺失的運行變成接受,因此可能得到錯誤的補。應先加入一個拒絕陷阱狀態並補全所有缺失的轉移,再交換標記。
反例模式
交換標記需要完全 DFA
斷言:交換接受狀態與非接受狀態,總能得到補語言。在 上,取只有一個接受狀態 和轉移 的部分轉移圖,它的語言是 。交換標記後沒有任何接受狀態,新機器甚麼也不接受,而 的補含有 。應先補全轉移圖:加入拒絕陷阱狀態 ,以及 和 ;交換後 成為唯一的接受狀態,機器恰好接受含有 的單詞,這正是補語言。
比較自動機時,應指明共同的字母表。若某部機器對該字母表中的某個符號缺少轉移,則按需用拒絕陷阱狀態將其補全。環境字母表的選擇是問題的一部分:補集是指該字母表上所有不屬於該語言的單詞。如果在一處把某個符號視為字母表之外,而在另一處又把它視為被自動拒絕的輸入,就會在沒有明言的情況下改變問題本身。
複雜度與證書
命題 1.3.12
(圖搜尋的運行時間)
對於 個狀態、字母表大小為 的完全 DFA,圖搜尋需要 時間和 個搜尋標記,儲存輸入的轉移表以及任何反向邊除外。空性需要一次這樣的搜尋;無窮性需要兩次可達性搜尋,以及對導出圖的一次環檢驗,每一步都是這個量級。對等價性所作的乘積搜尋至多訪問 個狀態和 條轉移。
證明
(狀態與轉移的計數)
完全轉移表有 條帶標號的轉移。每次搜尋在狀態首次被發現時標記它,並對每條出邊只檢查一次,這就給出所述的界。反向圖中某個狀態可能有很多入邊,但邊的總數不變。乘積至多有 個狀態,每個狀態有 個後繼,所以乘積搜尋滿足類似的界;它可以按需生成後繼,而不必儲存乘積的每條邊。
一個最短的被接受單詞或區分單詞是正面證書,可以透過模擬一部或兩部自動機來檢驗。關於空性或等價性的斷言則有不同的證書:從相應起始狀態可達的狀態集合,連同它不含任何禁止的終點、並且在每個轉移下封閉這一事實。可以透過檢查所有帶標號的出邊來驗證封閉性。僅僅沒能找到短單詞,並不足以下結論,除非搜尋已經窮盡了有限的可達狀態集,或者使用了另一個有根據的界。
無窮性證書由帶標號的進入路徑、環與離開路徑組成。檢查它們的端點以及接受狀態,便驗證了整個無窮族。反過來,沒有有用環這一事實,可以用可達且可共達子圖的拓撲排序來證明。這些證書使圖論證明更加具體,也把一個會終止的算法,與逐個單詞檢查無窮語言這種含糊其辭的說法區分開來。
總結
圖的可達性把語言的空性判定化為有限搜尋。乘積自動機把不等價性化為對分歧狀態的可達性。帶有非空環的接受路徑給出無窮多個長度互異的被接受單詞,而每條足夠長的接受路徑都含有這樣的環。
練習
快速檢查
(某個 DFA 的起始狀態是接受狀態。它的語言為空嗎?請給出見證單詞。)
看空單詞的運行。
解答 · 答案
不為空。空單詞使機器停在接受的起始狀態,它就是見證單詞。
快速檢查
(若兩部 DFA 在空單詞上的結果不一致,乘積搜尋返回甚麼?)
檢查乘積的起始狀態。
解答 · 答案
返回空單詞:乘積的起始狀態本身恰好有一個接受分量,所以不需要任何轉移。
快速檢查
(為甚麼可以任意多次繞行一個有用環,而離開路徑的出發狀態不變?)
環從哪裏開始、在哪裏結束?
解答 · 答案
環從同一個狀態出發並回到該狀態。每次繞行之後,離開路徑都可以從這同一個狀態出發。
快速檢查
(一部四狀態 DFA 接受一個長度為四的單詞。它的語言可能是有限的嗎?)
數一數接受運行訪問的狀態。
解答 · 答案
不可能。該接受運行(連同起始狀態)訪問五個狀態,因此有某個狀態重複。其間的非空環是有用的,並且可以重複,從而產生無窮多個被接受的單詞。