動機
名稱不同的兩個狀態未必代表不同的資訊。如果對每一種可能的後續輸入,兩個狀態給出的接受或拒絕結果都相同,那麼讀這部機器的人就可以放心地把它們視為同一個狀態。反過來,只要存在一個能區分它們的後續輸入,就證明這兩個狀態不能被等同。本節把這項觀察轉化為一個規範的構造和一個有限的算法。這裏的自動機都是確定型且完全的;缺失的轉移必須先指向一個拒絕陷阱狀態。
定義
定義 1.1.1
(剩餘語言與前綴等價)
固定有限字母表 和語言 。 在詞 之後的剩餘語言(residual)為 。當 時,記 。
定義 1.1.2
(狀態等價、可達與最小性)
對於 DFA,如果兩個狀態接受的後續輸入恰好相同,則稱它們等價。如果存在某個詞把初始狀態帶到某個狀態,則稱該狀態可達。最小性指在識別 的完全 DFA 中狀態數最少。
右同餘性質由此直接得到:若 ,則對每個字母 有 ,因為 當且僅當 。請注意, 與 本身不必屬於 ;剩餘語言檢驗的是每一個後續輸入,包括 。
定理
定理 1.1.3
(Myhill–Nerode 定理)
語言 能被某個有限 DFA 識別,當且僅當 只有有限多個等價類。在這種情形下,以這些等價類為狀態、初始狀態為 、轉移為 、接受狀態為滿足 的 的 DFA,是 的一個最小完全 DFA。 的每個最小完全 DFA 都與它同構(作為帶初始狀態、帶標記並帶接受狀態集的自動機)。
定理 1.1.4
(劃分細化)
給定一個有限完全 DFA,先刪除不可達狀態。從接受狀態集和非接受狀態集中,只保留非空者作為初始劃分。只要某個區塊中的兩個狀態在某個字母上的轉移落入當前不同的區塊,就拆分該區塊。當不再有可拆分的區塊時,這些區塊恰好就是狀態等價類。其商 DFA 對原語言而言是最小的。
證明思路
證明
(剩餘語言類給出最小 DFA)
先設某個 DFA 識別 。如果讀入 與讀入 到達同一個狀態,那麼每個後續輸入的結果都相同,因此 。所以剩餘語言的等價類個數不超過狀態數。反過來,當等價類只有有限多個時,上述構造由右同餘性而是良定義的;接受性也是良定義的,因為 是一個可能的後續輸入。對 歸納可知,讀入 之後所處的狀態是 。因此它識別 。
的任何 DFA 對不同等價類中的詞必定到達不同的狀態,這給出下界。所構造的機器達到這個下界。若另一部機器也達到這個下界,則它的所有狀態都可達:否則刪除不可達狀態會得到更小的機器。把讀入 後到達的狀態映到 的映射是良定義的、滿射的,並且由於兩邊基數有限且相等,它是雙射。它保持初始狀態、轉移和接受性。這證明了唯一性是在重新命名意義下成立的,而不是狀態名稱逐字相同。
證明
(穩定劃分就是等價類)
對於細化算法:起初沒有任何區塊同時包含接受狀態和拒絕狀態,所以等價的狀態不會被分開。如果某次拆分在字母 上把 分開,則它們的後繼所在的區塊此前已被分開;由歸納可知,存在某個後綴 區分這兩個後繼,於是 區分 。因此等價的狀態永遠不會被拆開。算法終止時,同一區塊中的狀態在每個字母上的後繼都在同一區塊中,並且接受性一致。現在對後續輸入的長度歸納,即知它們等價。每次真正的拆分都使區塊數增加,而區塊數至多是可達狀態的個數,所以過程會終止。商自動機透過對輸入長度歸納而識別同一語言,並且它的不同狀態是可區分的。因此由第一個定理,它是最小的。
證明透視
為甚麼每個後綴都重要
對空後續輸入取得一致,只檢驗了當前的接受性。細化步驟多檢驗了一個起始字母,然後依賴一個任意的後綴。歸納涵蓋了每一個有限的後續輸入,儘管算法只儲存有限多個區塊。
假設在三處起作用。轉移函數的完全性使 對每個狀態和每個詞都有定義,所以每個後續輸入都能被檢驗。狀態集的有限性限制了拆分的次數,這就是過程會停止的原因。關鍵一步在於見證的記錄:只有存在一個真正區分兩個狀態的後綴 ,才會作出拆分,所以等價的狀態對永遠不會被拆開,而穩定性則給出反方向。若去掉完全性,就會有些後續輸入沒有被檢驗。
例題詳解
例題 1.1.5
(偶數個 1 的奇偶性)
在 上,令 為含有偶數個 1 的詞的集合。剩餘語言有兩個:偶數個 1 的前綴之後,後續輸入需要偶數個 1;奇數個 1 的前綴之後,後續輸入需要奇數個 1。它們在 上不同。因此最小機器有兩個狀態: 使狀態保持不變, 使兩個狀態互換,偶數狀態既是初始狀態又是接受狀態。
例題 1.1.6
(一次細化分開兩個拒絕狀態)
考慮字母表 和狀態 ,初始狀態為 ,唯一的接受狀態為 ,轉移為 、、。所有狀態均可達。起初的區塊是 與 。第一個區塊會被拆分,因為 轉移到前者,而 轉移到後者。三個單元素區塊是穩定的。後綴 區分 與 ,而 區分它們中任何一個與 。
例題 1.1.7
(需要無限多個狀態的語言)
對於 ,對不同的非負整數 ,前綴 與 被 區分:,但 。因此剩餘語言有無限多個,沒有有限 DFA 識別 。這個證明是為每一對前綴選取一個區分後綴,而不是應用泵引理。
常見錯誤
反例模式
當前答案相同並不意味著狀態相同
在三狀態的例子中, 與 對空後續輸入都拒絕,但從 出發 被接受,從 出發則被拒絕。僅僅因為二者當前都拒絕就把它們合併,會改變所識別的語言。
常見錯誤
(不要忘記刪除不可達狀態)
刪除不可達狀態是對給定機器進行最小化的必要步驟。如果合併了等價的可達狀態,卻沒有刪除某個不可達的孤立狀態,結果可能不是最小的。
反過來,商中的一個區塊可以包含多個狀態而不丟失資訊:它的轉移是良定義的,恰恰因為最終的劃分是穩定的。
理解並實現細化
可以把細化看作一系列要求越來越高的實驗。起初,兩個狀態只要對空後續輸入的表現一致,就留在一起。經過一次同時細化後,狀態還須對所有長度為一的後續輸入表現一致。經過 輪後,它們對長度至多為 的後續輸入表現一致。這個斷言由歸納得到:長度至多為 的後續輸入或者為空,或者形如 ,其中 的長度至多為 。要使它們對所有這樣的字串都一致,對每個 ,其 -後繼必須直到第 輪都一致。
這種解釋假定每一輪都是從上一輪的劃分同時進行的。實現時也可以一次拆分一個區塊;它會到達同一個穩定劃分,但其中間劃分不必與按長度編號的各輪一致。無論採用哪種實現,算法在每次拆分之後都必須繼續檢查每個字母,因為後繼之間新出現的區分,可能揭示出其前驅之間更早就存在的區分。
對於小型自動機,可以構造一張由可達狀態的無序對組成的表。把接受性不一致的每一對都標記出來,以 作為見證。每當某個未標記的對的 -後繼已經被標記並帶有見證 ,就用見證 標記該對。繼續下去,直到再沒有對可被標記。未標記的對由同樣的穩定劃分論證可知是等價的。見證在檢查實現時很有用:它們給出一個具體的輸入,說明合併某一對狀態會出錯。除非按適當的長度順序處理各對,否則這些見證不一定是最短的。
例題 1.1.8
(細化向後傳播)
取四個一元狀態 ,其中 為初始狀態, 是唯一的接受狀態,當 時 把每個 移到 ,而 自迴圈。所有狀態均可達。初始劃分為 。一次同時細化把後繼為接受狀態的 與 分開。下一輪把 與 分開,因為它們的後繼現在位於不同的區塊中。後綴 區分 與 :從前者出發到達 ,從後者出發到達 。四個狀態都是必需的。
商對每個原有轉移的定義為 。穩定性保證結果不依賴於代表元 的選取。對每個詞 ,歸納得到 。因此,商所做的不止是保留從初始狀態出發對完整輸入的接受性:它保持了每個原有狀態對每個未來輸入的行為。這說明了為甚麼在計算過程中合併這些狀態是合理的,而不是只有在讀完整個詞之後才合理。
還有一個有用的區別:固定自動機中狀態的等價,不同於語言的前綴的等價。狀態等價問的是,把任意一個狀態用作起點時會發生甚麼。前綴等價問的是,從真正的初始狀態出發,一個前綴之後跟著怎樣的剩餘語言。每個可達狀態至少對應一個前綴,並且它的後續語言恰好就是該前綴的剩餘語言。不可達狀態也有後續語言,但它們不能貢獻從真正的初始狀態出發所到達的新的剩餘語言,因此不屬於規範的最小機器。
語言的比較
規範機器還給出了判定同一字母表上兩個給定完全 DFA 是否等價的一個判定過程。把它們的不交併看作一個轉移系統,按接受性和轉移細化合併後的狀態集,然後比較兩個初始狀態。當且僅當每個詞要麼被兩者都接受、要麼被兩者都拒絕時,它們才在最終的同一個區塊中。與先分別最小化每部機器、再比較名稱不同,這一過程不假定任何特定的命名約定。在配對表方法中,若初始狀態對被標記,就給出一個明確的詞,見證二者不等價。在合併字母表不同的機器之前,應先指定一個共同的字母表,並用陷阱狀態補全轉移函數;否則「同一語言」還沒有在同一個定義域上被提出。
例如,含有偶數個 1 的詞的語言,在插入一個冗餘狀態後保持不變,只要該狀態的接受性與後繼行為與原來的偶數狀態完全一致。這樣的重複不改變任何後續語言,因此只要兩者都可達,細化就會把重複的狀態與原狀態合併。相反,如果新增的狀態在某個字母上的轉移不同,那麼這兩個狀態也許要再讀入若干字母之後才變得可區分。只有當目標狀態已經等價時,轉移的直接相等才足以保證等價,而不是僅僅因為標籤看起來相似。
有限見證與算法的適用範圍
有限狀態這項假設在算法中起兩次作用。第一,可達性可以透過圖搜尋來計算:從初始狀態出發,反覆加入已到達狀態的每個字母後繼。由於狀態有限,這一過程會停止。第二,可達狀態集的可能拆分只有有限多種。因此穩定劃分在有限次改變之後就會出現。正確性的證明並不需要預先知道最短區分詞長度的界,儘管有限的配對表在標記一個對時本身就能給出這樣的見證。
這個定理是關於所有語言的陳述,包括非正則語言。它的正向蘊涵把有限機器變成有限多個剩餘語言。它的反向蘊涵由有限多個剩餘語言構造出一部機器。要用這個定理證明非正則性,只需給出一族無限多個前綴,使它們的剩餘語言兩兩不同即可。不需要列出每一個剩餘語言,也不需要找到計算它們的算法。另一方面,檢查少數幾個可區分前綴的例子,並不能證明存在無限多個等價類:這個兩兩的論證必須對任意多個不同的下標都成立。
常見錯誤
(少數幾個可區分的前綴不能證明有無限多個等價類)
對於 ,檢查 、、 兩兩可區分,只說明至少需要三個狀態。非正則性的證明必須對任意的 給出區分後綴 (如例題詳解所示),這樣等價類的個數才沒有上界。
只有在固定了輸入字母表和完全性約定之後,最小機器才是唯一的。如果允許部分自動機在缺失轉移時拒絕,那麼拒絕陷阱狀態有時可以省略,從而改變狀態數。這裏的構造使用全轉移函數,對於「無望」的前綴,其剩餘語言是空語言。只要到達這個空剩餘語言,它就是一個普通的狀態。類似地,改變字母表可能引入新的可能後續輸入;比較時應明確給出共同的字母表。
作為最後的檢驗,考慮空語言。所有前綴都具有同一個空剩餘語言,所以它的最小完全 DFA 恰有一個非接受狀態,並在每個字母上自迴圈。包含所有詞的語言也只有一個狀態,但該狀態是接受狀態。兩部機器的狀態數都不是零:DFA 必須有一個初始狀態,即使在某個特定輸入詞中字母表沒有可用的轉移時也是如此。這個小例子同時檢驗了對初始狀態和空後續輸入的處理。
總結
剩餘語言恰好刻劃了一個前綴中能夠影響未來接受性的那部分資訊。它們的個數就是正則語言的狀態複雜度。細化在有限機器上計算同一個等價關係,而一個區分後綴就是某個擬議的合併有誤的證據。
下圖使用另一台五狀態二元字母表自動機,並非上面的單字母例子。可比較它的可達狀態細分與那些例子。
練習
快速檢查
(求以 結尾的二進制詞的最小完全 DFA,並說明空詞的狀態。)
想一想:狀態需要記住最後讀入的符號的甚麼資訊。
解答 · 答案
用狀態 表示最後一個符號是否為 ; 是初始狀態且拒絕, 接受。輸入 使任一狀態轉到 ,輸入 使任一狀態轉到 。它們被 區分,這證明了最小性。
快速檢查
(對 ,當 時,給出區分 與 的後綴。)
選取恰好能補全較短前綴所對應的 的個數的後綴。
解答 · 答案
取 。此時 ,而 ,因為 。這包括 的情形,此時後綴為 。
快速檢查
(解釋為甚麼一個不接受任何後續輸入的可達狀態,可以與任何具有同樣性質的其他可達狀態合併。)
比較這兩個狀態的剩餘語言。
解答 · 答案
兩個狀態的剩餘語言都是空語言,所以它們等價。商構造保持所有後續輸入;可達性並不妨礙安全地合併。
快速檢查
(對於一元詞,證明長度可被 整除的語言至少需要三個狀態。)
考慮前綴 、、。
解答 · 答案
之後的剩餘語言為 。若 ,取 使 ;則 在 之後被接受,在 之後則不被接受。因此 三個前綴的剩餘語言兩兩不同,這給出下界;由三個狀態構成的環達到這個下界。