在奇偶性例子中,一個 DFA 狀態概括已讀取的前綴。非確定性自動機在讀取相同前綴後,卻可能處於多個狀態。因此,有用的確定性摘要是一個可能狀態的集合,而不是猜哪條路徑會成功。改變狀態所記住的資訊,就自然得到子集構造。
以下始終分清三件事:NFA 內的一條路徑、全部可能終點的集合,以及代表這個集合的一個 DFA 狀態。這樣可以避免兩個常見錯誤:因為某個分支失敗便拒絕字串,或只因較早的前綴被接受便接受整個字串。
模擬前先定義接受條件
定義 6.2.1
(容許空轉移的 NFA)
-NFA 是五元組 ,其中 是有限狀態集, 是有限輸入字母表, 是起點, 是接受狀態集,而轉移函數為
這裏 是 的全部子集所組成的集合。一次轉移可以沒有目的地、只有一個,或有多個。-轉移改變狀態但不消耗輸入符號; 不是輸入字母表中的符號。不含 -轉移的普通 NFA,是每個 -後繼集合都為空的特例。
一條有限運行路徑,把邊標籤中的 刪去後,便拼成所讀取的輸入字串。當至少一條這樣的路徑由 出發、消耗整個字串並在 內結束,機器就接受該字串。其他運行可以失敗,或在 外結束。這個定義沒有概率或隨機選擇。
下方轉移表以空後繼集合 表示沒有相應邊。這與省略 DFA 轉移不同:對正在讀取的符號沒有後繼的 NFA 分支會終止,但其他分支仍可繼續。
反例模式
一個分支失敗,不代表字串被拒絕
令 對 0、1 都有自環,亦容許 ,再有 ,只有 是接受狀態,沒有其他邊。
輸入 01 時,運行 在接受集外結束;但 消耗相同字串並接受。若只選第一條運行,便會錯誤拒絕。正確模擬應在讀取 0 後保留兩個終點,再收集讀取 1 後的全部後繼。
這個 NFA 識別以 01 結尾的字串。接受路徑必須在倒數第二個 0 進入 ,再在最後的 1 進入 ,因為 沒有出邊。反過來,任何前綴都可先由 的自環讀取,再走最後這兩條邊。
把不消耗輸入的可達狀態全部納入
定義 6.2.2
(-閉包)
對子集 ,其 -閉包 是由 中某個狀態出發,沿零條或多條 -邊可達的全部狀態所組成的集合。零條邊的情況很重要,每個起始狀態都屬於自己的閉包。
閉包運算滿足
第一式把起始狀態納入。第二式是因為把兩條 -路徑接起來,仍是 -路徑,所以已閉的集合不會再增加狀態。第三式表示沒有任何起始狀態,就不能到達任何狀態。不要混淆 與 :前者是不含符號的字串,後者是不含狀態的集合。
例題 6.2.3
(-環的可達終點仍是有限集合)
假設 、, 接受,且在 有一條 0 自環。那麼 。這個環容許任意長的 -遊走,卻沒有更多不同狀態。
工作清單從起始集合出發,沿 -出邊前進;只有尚未見過的目的地才加入。每個狀態最多加入一次,所以有限 NFA 不會令搜尋永遠循環。取閉包並不消耗 0 或 1。
這個例子接受空字串,因為起點閉包含有 。再讀一個 0 會回到同一閉集合,讀 1 則得到空集合。因此,其語言是 ,包括空字串。接受不需要無限 -遊走:由 到 的有限 -邊,已足以見證空字串被接受。
先消耗一個符號,再取閉包
對輸入符號 ,把所有一條邊可達的目的地收集為
若 已是 -閉的,即 ,下一個完整可能狀態集合就是
原來的閉包處理消耗 之前的 -步驟,新閉包則處理之後的 -步驟。因此,只看原始符號轉移目的地,可能漏掉一個接受的可能性。
例題 6.2.4
(恰好接受 0 與 01 的機器)
起點為 ,接受集為 ,完整後繼表如下:
| 狀態 | 讀取 0 | 讀取 1 | -後繼 |
|---|---|---|---|
讀取 0 先產生原始集合 。其閉包是 ,因為可以選擇走 -邊而不消耗任何符號。因此,即使原始目的地不是接受狀態,0 仍被接受。由這個閉集合再讀取 1,得到 ,所以 01 也被接受。由 無法再消耗另一個符號。
現在追蹤較長輸入 010:
| 已處理前綴 | 最後一個符號的原始目的地 | 已確定的 -閉集合 | 若輸入在此結束,此前綴會接受嗎? |
|---|---|---|---|
| 尚未讀取符號 | 否 | ||
0 | 是 | ||
01 | 是 | ||
010 | 否 |
整個輸入 010 被拒絕。前面任何一段前綴被接受,都不代表可以忽略餘下輸入。接受狀態並非要求提早停止計算的指令。
用圖追蹤上面三個自動機。符號轉移步驟中的原始目的地只是預覽;取 -閉包後才確定新子集。比較前綴的判斷與整個字串的判斷。
證明子集是精確摘要
定理 6.2.5
(子集準確追蹤所有運行)
設 是 -NFA。對 上的字串 ,令 為:由 出發、恰好消耗 的某條運行可以結束的全部狀態;符號之前、之間與之後都容許 -步驟。則對每個字串 與符號 ,
而且 接受 ,當且僅當 。
證明
(對已消耗符號數作歸納)
對空字串,運行只能使用 -邊,所以恰好得到初始閉包。假設 正確。消耗 的任何運行,都有最後一條消耗符號且標為 的邊。在這條邊之前,運行已消耗 ,並在 某個狀態;之後則可沿 -邊前進。因此,它的最後狀態一定包含在符號轉移及閉包的結果內。
反過來,公式產生的每個狀態都有見證:先有一條讀取 並到達 中某狀態的運行,再有一條 -邊,最後接一條有限 -路徑。三部分構成讀取 的合法運行。對字串長度作歸納,就同時證明兩個包含方向,所以子集是精確答案,而非過度估計。
最後, 接受 ,當且僅當某條讀取 的運行在 內結束,亦即 。存在某條接受運行的條件,於是成為簡單的集合交集測試,毋須選定一條運行。
證明透視
為何歸納需要兩次取閉包
歸納是對 的符號數進行,而不是對運行長度進行。-環令讀取同一個字串的運行可以任意長,所以運行長度給不出上界。把每條運行在最後一條消耗符號的邊切開,就有上界:切開前的部分消耗的是嚴格較短的字串 。
有三個要點。第一, 按定義已是 -閉的:讀取 的任何運行都可再接上更多 -邊。因此公式中的閉包只需補上新符號之後的 -步驟;新符號之前的 -步驟早已包含在 內。第二,包含方向 把運行拆開,說明沒有漏掉終點;方向 把三段拼成運行,說明沒有虛構終點。第三,接受條件對運行作存在量化,所以只有終點集合才重要:兩條運行在同一狀態結束,往後能讀取的內容完全相同。
兩次閉包缺一不可。若由 而非 起步,基礎情況便不成立:在 -環例子中, 漏掉接受狀態 ,空字串會被錯誤拒絕。若符號轉移後不取閉包,歸納步驟便不成立:在恰好接受 0 與 01 的機器中,原始目的地 會令 0 被拒絕。 的有限性在這兩個等式中並未用到,它只保證每個閉包可計算,而且子集數目有限。
把可達子集變成 DFA 狀態
每個可達的 -閉子集,都用作一個 DFA 狀態。起點是 ,讀取 的轉移是 ,子集與 相交便是接受狀態。每個子集對每個符號恰好有一個後繼子集;即使子集包含多個 NFA 狀態,這仍然是確定性的。
常見錯誤
(接受子集只需與 F 相交)
子集不必包含於 。在恰好接受 0 與 01 的機器中,讀取 0 後到達的子集 含有不接受的 ,卻必須接受:結束於 的運行就是見證,一個見證已經足夠。若要求 ,0 便會被拒絕;正確的測試是 。
用工作清單建立轉移表:從初始子集開始,每個已發現子集只處理一次,計算它對每個字母表符號的後繼,只有新後繼才加入。子集最多有 個,所以構造會終止。這裏的相等是集合相等: 與 代表同一個 DFA 狀態。
推論 6.2.6
(子集構造保留語言)
令 為這樣的 DFA:起點是 ,讀取 的轉移是 ,接受狀態是與 相交的子集,並只保留由起點可達的子集。則 至多有 個狀態,而且 。
證明
(讀取 w 後的 DFA 狀態是 S_w)
上一個定理的兩條等式,正是 的起點與轉移規則,所以對 作歸納可知,讀取 後 處於狀態 。 的每個狀態都是 的子集,這給出上界 。最後, 接受 當且僅當 ,這正是 接受 的條件。
概念視角代數
子集步驟是布爾矩陣乘積
把集合 寫成 0–1 行向量,-邊寫成布爾矩陣 ,-邊寫成 ,以 OR 作加法、AND 作乘法。由於經 -邊可達的狀態,必可用少於 條 -邊到達,所以 就是乘以 ,而 就是 。對恰好接受 和 的機器, 是 ,與 相乘得 ,取閉包得 ,即集合 。
例題 6.2.7
(對上述機器作子集構造)
對接受 0 或 01 的機器,把可達子集命名為
| DFA 狀態 | 讀取 0 | 讀取 1 | 接受? |
|---|---|---|---|
| (起點) | 否 | ||
| 是 | |||
| 是 | |||
| 否 |
空子集是普通的拒絕 DFA 狀態:沒有運行剩下,而任何符號都不能憑空建立一條運行。它可達時就應納入,正如此例。相對地,之前識別以 01 結尾字串的 NFA,始終保留 這個可能性,其可達子集只有 、、,空子集並不可達。
把這三個子集命名為 、、。各行由 、、 算出,沒有其他邊:
| DFA 狀態 | 讀取 0 | 讀取 1 | 接受? |
|---|---|---|---|
| (起點) | 否 | ||
| 否 | |||
| 是 |
字串 0101 依次經過 而被接受;010 結束於 而被拒絕;空字串停留在拒絕的起點 。
常見錯誤
(DFA 沒有 列)
DFA 轉移表對 中每個符號各有一列,沒有 列。NFA 的 -邊已被吸收進定義各個子集的閉包之中,而確定性機器沒有不消耗輸入的轉移。含 列的表所描述的是另一種機器。
子集構造保留語言,卻不是最小化算法。指數上界限制的是可能子集數目,並非聲稱每個 NFA 都能到達每個子集。
反例模式
兩個接受子集仍可能需要不同的後續行為
四狀態表中的 與 都接受目前前綴,但不能只憑這點合併。後綴 1 把 帶到接受的 ,卻把 帶到拒絕的 。在已接受前綴 0 後加 1,得到接受的 01;在已接受前綴 01 後加相同後綴,卻得到拒絕的 011。
狀態等價要求對每個後續字串都同意,而不只是同意現在是否接受。證明奇偶 DFA 需要不同奇偶狀態時,使用的也是這種區分。
直接實現不變式
以下 Python 程式使用狀態名稱集合。字典中沒有的項目,表示空後繼集合;輸入是 上的字串。空字串是 Python 的 "",不是字面字元 "ε"。
def epsilon_closure(seeds, epsilon):
seen = set(seeds)
pending = list(seen)
while pending:
state = pending.pop()
for target in epsilon.get(state, ()):
if target not in seen:
seen.add(target)
pending.append(target)
return frozenset(seen)
def step(states, symbol, transitions, epsilon):
targets = {
target
for state in states
for target in transitions.get((state, symbol), ())
}
return epsilon_closure(targets, epsilon)
def accepts(word, start, accepting, transitions, epsilon):
states = epsilon_closure({start}, epsilon)
for symbol in word:
states = step(states, symbol, transitions, epsilon)
return not states.isdisjoint(accepting)
transitions = {("q0", "0"): {"q1"}, ("q1", "1"): {"q2"}}
epsilon = {"q1": {"q2"}}
for word in ["0", "01", "010", ""]:
print(repr(word), accepts(word, "q0", {"q2"}, transitions, epsilon))
布爾輸出依次為 True、True、False、False。工作清單的已訪問集合,防止無休止地探索 -環。frozenset 提供不可變表示,日後可用來命名 DFA 子集。毋須儲存每段分支歷史:兩條運行在相同前綴後到達同一狀態,往後可讀取甚麼只取決於該狀態,所以保留一次集合成員資格已足夠。
程式刻意等符號轉移及其閉包都完成,才更新 states。手算時也應把原始目的地與已消耗前綴所對應的確定狀態分開標示,否則表格可能聲稱已消耗一個符號,卻仍顯示上一段前綴的集合。
練習
快速檢查
(先算閉包,再判斷空字串)
在 -環例子中,計算 與 。空字串會被接受嗎?環容許無限多條遊走,為何已訪問集合仍保證終止?
解答 · 答案
閉包分別是 與 。空字串被接受,因為初始閉包含有接受狀態 。搜尋記錄不同狀態,而不是完整遊走;兩個狀態各加入一次,之後重訪就不會再加入工作清單。
快速檢查
(對後綴語言保留全部分支)
對接受以 01 結尾字串的 NFA,追蹤 010 的子集。哪些前綴若在當時結束會被接受?為何整個字串被拒絕?
解答 · 答案
起初為 ,之後依次為 、、。只有前綴 01 有接受終點。010 的最後子集沒有 ,所以整個字串被拒絕。留在 的分支仍存在,但該狀態不接受。
快速檢查
(解釋只看原始目的地為何會錯誤拒絕)
在恰好接受 0 或 01 的 NFA 中,某模擬讀取 0 後得到原始目的地 ,因為 而拒絕。它漏了哪項操作?正確的最後接受測試是甚麼?
解答 · 答案
符號轉移後應取 -閉包。它保留 並加入 ,得到 ,與 的交集非空,所以 0 被接受。-邊不消耗額外輸入符號,即使已沒有符號剩下,仍須考慮它。
快速檢查
(分清可達性與冪集上界)
三狀態的後綴 NFA 最多有八個可能子集。為何構造所得 DFA 卻只有三個可達狀態?為何不應另把空陷阱狀態算作可達?最小化會問另一個甚麼問題?
解答 · 答案
起始子集包含 ,而 對每個符號都有自環,所以每個到達的子集都保留它。轉移恰好產生 、、,分別由 、0、01 到達,沒有一個為空。上界計算全部子集,包括不可達的。最小化則問:是否有可達 DFA 狀態對每個後續字串都同意,因此可在不改變語言下視作同一狀態?