有限自動機逐個符號讀入字串。狀態必須記住已讀前綴中足夠的資訊,才能決定任何後續字串的結果。我們先構造機器,再證明它恰好識別目標語言。
精確定義
定義 6.1.1
(確定有限自動機)
確定有限自動機(DFA)是五元組 : 是有限狀態集合, 是字母表, 是全定義的轉移函數, 是初始狀態, 是接受狀態集合。全定義表示每個狀態對每個輸入符號都有指定轉移。
以 表示從 讀完整個字串 後的狀態;特別地,空字串滿足 ,並且 。當且僅當 ,機器接受 。
除非明確加入拒絕陷阱狀態及其轉移,缺失箭嘴本身並不是拒絕規則。
追蹤兩個奇偶位
令 為所有 的數目及 的數目均為偶數的二進制字串。使用 四個狀態:第一個字母記錄 的數目奇偶,第二個記錄 的數目奇偶; 為偶數, 為奇數。初始及唯一接受狀態均為 。
| 狀態 | 讀入 0 | 讀入 1 |
|---|---|---|
| EE | OE | EO |
| EO | OO | EE |
| OE | EE | OO |
| OO | EO | OE |
例題 6.1.2
(追蹤三個字串,包括空字串)
讀入 得 ,因此接受:它有兩個 和兩個 。讀入 則停在 ,因此拒絕: 的數目為偶數,但 只出現一次。空字串不讀入任何符號,機器仍停在 ,所以被接受:兩種符號均出現零次,而零是偶數。
命題 6.1.3
(奇偶機器識別 L)
對每個二進制字串 ,狀態 的第一個字母記錄 中 的數目的奇偶,第二個字母記錄 的數目的奇偶。因此,當且僅當 ,機器接受 。
證明
(對字串長度作歸納)
當 時,兩個數目均為零,即為偶數,而 。假設命題對 成立。依上表,讀入 恰好改變狀態的第一個字母(、),第二個字母不變;讀入 恰好改變第二個字母(、),第一個字母不變。字串 比 多一個 , 的數目相同; 的情況類似,所以命題對 成立。依歸納法,命題對每個有限字串成立。
唯一接受狀態是 ,故機器接受 恰好等價於兩個數目均為偶數。這同時證明兩個方向:不會錯收 以外的字串,也不會漏收 內的字串。
證明透視
為何不變式必須是整個狀態
歸納不能直接對「」這個命題進行。知道 被拒絕,並不能決定 會否被接受,下面的反例正說明這一點。命題必須加強為完整的奇偶對,而這正是狀態所儲存的資訊。加強之後,接受條件就成為狀態的等式 ,一個論證便同時給出兩個包含方向。
八個表項只透過兩個統一事實進入證明:讀入 翻轉第一個字母,讀入 翻轉第二個字母。所以一個歸納步驟便同時涵蓋四個狀態。 的全定義性在這裏是默默使用的,因為 必須對每個字串都有定義。若任何一個表項出錯,例如 讀入 變成 而非 ,不變式在前綴 就已失效:它有一個 、兩個 ,卻會停在 而非 。
同一部機器還有第二種描述。把 分別對應到模 整數的數對 。
概念視角代數
狀態是模 2 的和
在這個對應下,讀入 即加上 ,讀入 即加上 ;逐一核對八個表項即可確認,例如 。因此讀完 後,狀態是各字母向量之和:
其中 是 在 中出現的次數。加法可交換,所以重排 的字母不會改變狀態: 與 到達同一狀態。接受條件就是這個和等於零向量。
為何至少需要四個狀態
定義 6.1.4
(可區分字串)
設 為語言。若存在字串 ,使 與 恰有一個屬於 ,則稱字串 與 對 可區分。
命題 6.1.5
(至少需要四個狀態)
任何識別 的 DFA 都至少有四個狀態。
證明
(四個兩兩可區分的前綴)
四對奇偶值均可到達:、、、 分別到達 、、、,所以這四個字串的奇偶對互不相同。任取其中兩個奇偶對不同的字串 和 ,依 選擇同一後綴 :若 的 數目為奇數便加入一個 ,若 的 數目為奇數便加入一個 。這個後綴令 兩位皆為偶數。對 加上相同後綴,翻轉的是相同的位,所以 與 仍至少有一位不同,即至少有一位為奇數。因此 與 恰有一個屬於 , 與 可區分。
設 為任何識別 的 DFA。若這四個字串中有兩個到達 的同一狀態,則對每個後綴 , 與 也到達同一狀態,因而得到相同結果,這與可區分性矛盾。所以四個字串到達 的四個不同狀態。上面的四狀態機器因而最小。這是對所有 的 DFA 的證明,不只是找不到更小的圖。
例題 6.1.6
(區分兩個前綴的後綴)
前綴 與 分別到達 與 。前者的 數目為奇數,所以取 。於是 有兩個 、沒有 ,屬於 ;而 有一個 ,不屬於 。若有機器把這兩個前綴合併, 與 就會得到相同結果,這是錯的。
反例模式
相同結果不代表可以合併
假設有人聲稱:只要兩個前綴都被拒絕,它們就可以共用一個狀態。前綴 與 都被拒絕,因為各自有一個數目為奇數。可是接上 後,,而 (一個 和一個 )。兩個前綴對這個後續字串的表現不同,所以正確的機器必須把它們分開。兩個前綴只有在每個後續字串都得到相同結果時,才能共用一個狀態。
例題 6.1.7
(同一論證用於另一個不變式)
令 為 的數目可被 整除的二進制字串。取狀態 ( 的數目模 ),讀入 則加一(模 ),讀入 則不變,初始狀態為 ,接受集合為 ;依相同的歸納可知這部機器識別 。前綴 、、 兩兩可區分。後綴 把 與其餘兩個分開: 有三個 ,屬於 ,而 有四個、 有五個。後綴 把 與 分開: 有三個 , 則有四個。因此至少需要三個狀態,而上述機器顯示三個已經足夠。空字串被接受,因為零可被 整除。
常見錯誤
(狀態不等於最後一個符號)
表示目前 的總數為偶數、 的總數為奇數,並不表示最後讀到哪個符號。 和 等不同前綴可到達同一狀態,因為接上任何相同後綴時,它們的接受結果一致。
常見錯誤
(長度為偶數並不足夠)
長度為偶數的字串不一定屬於 。字串 長度為二,但它有一個 和一個 ,兩個數目都是奇數。只記住長度奇偶的機器會把 與 合併,無法分辨 和 ,但只有 屬於 。
練習
快速檢查
(追蹤 和 ;哪些被接受?)
逐個符號跟著轉移表走。
解答 · 答案
依次經過 ,故接受; 依次經過 ,停在 ,故拒絕。
快速檢查
(哪個後綴可區分 和 ?請用兩個結果字串是否被接受來解釋。)
試試最短的後綴。
解答 · 答案
後綴 令 到 ,而 到 ;只有前者接受。
快速檢查
(若只把接受集合改為 ,轉移不變,新語言是甚麼?)
先看狀態的第一個字母代表甚麼。
解答 · 答案
第一位必須為偶,第二位不限;即所有含偶數個 的二進制字串。