動機
有限狀態機一次讀入一個符號,並且只能記住有界的資訊量。這項限制令它所識別的語言類在數學上十分整潔,同時也劃出了一條邊界:一些看上去很簡單的語言需要無界的記憶。本節把這兩方面都精確化。我們證明三種不同的描述——確定型自動機、帶靜默轉移的非確定型自動機,以及正則表達式——定義同一類語言,然後證明一個用來說明某語言不屬於該類的工具。
若干標準主題沒有處理:例如最小化算法以及最小自動機唯一性的完整理論,下文證明的可區分性界只是該理論的下界部分。
定義
定義 1.2.1
(字母表、字與語言)
字母表 是有限非空的符號集合。 上的字是符號的有限序列; 表示空字串, 表示所有字的集合。字 的長度記作 。語言是 的任一子集。語言的連接為 ,並令 ,其中 。
語言 (不含任何字)與 (恰含空字串)是不同的;在連接與星號的構造中混淆兩者是常見的錯誤來源。
定義 1.2.2
(DFA)
確定型有限自動機是 ,其中 有限, 是全函數,,。定義 與 。則 。
定義 1.2.3
(帶靜默移動的 NFA)
-NFA 是 ,其中 。對 ,-閉包 是包含 、且包含從任一成員經 -轉移可達的所有狀態的最小集合。令 ,。語言為 。
概念視角算法
把非確定性看作模擬一個狀態集合
可以把 -NFA 看作一個程式,它維護「當前可能所處的狀態集合」。每讀入一個符號,先把每個成員沿匹配的邊移動,再對靜默移動取閉包。該程式可能的記憶內容只有有限多種,即各個子集,因此它是一台 DFA。指數界是這個程式所需記憶的上界;許多 NFA 可達的子集遠少於此,如下面第一個例題所示,八個子集中只有四個可達。
定義 1.2.4
(正則表達式)
上的正則表達式由原子 、 以及每個 ,經並 、連接 與星號 構成。其語言為 ,,,,,。表達式的規模把每個原子和每個運算符的出現各計一次。若一個語言等於某個 DFA 的 ,則稱其為正則語言。
定義 1.2.5
(可區分的字)
固定語言 。若存在字 使得 與 中恰有一個屬於 ,則稱字 被 區分。
定理
定理 1.2.6
(子集構造)
設 是狀態集為 的 -NFA。定義 ,其中 ,。則 。特別地,-NFA 的每個語言都是正則的,且至多 個狀態的 DFA 就足夠。
證明
(追蹤可達狀態的集合)
首先說明 的含義符合直覺: 當且僅當存在一條從 到 的路徑,其標記為符號或 ,刪去 後拼成 。對 ,這樣的路徑只用靜默移動,得到 。對 ,路徑分解為:一段拼成 且終於某個 的路徑,一步 -轉移到 ,以及一段從 到 的靜默路徑;歸納假設給出 ,所以 屬於所述閉包,反向則按同一分解逆讀即可。其次,對 歸納可得 :基礎情形就是起始狀態的定義,歸納步驟即等式 。 接受意味著 ,即 。
證明透視
子集構造中各個假設在何處起作用
構造只用到 的有限性,使 成為合法的有限狀態集。 是全函數,因為 對每個集合(包括空集)都有定義,空集成為陷阱狀態。關鍵一步是等式 :它說明 NFA 的全部非確定性歷史被一個集合概括,因此未來只依賴於該集合。證明最後落在 的定義上,即「存在一個成員是接受狀態」。
定理 1.2.7
(Thompson 構造)
對每個正則表達式 ,存在 -NFA ,使 ,且它有唯一的起始狀態(無入邊)、唯一的接受狀態(與起始狀態不同,無出邊),狀態數至多為 。
證明
(對表達式結構歸納)
對 的結構歸納。對原子,用兩個狀態: 不連邊, 用 -邊相連,字母則用該字母相連;狀態數為 ,與規模 相符。對 ,新增起始狀態,用 -邊指向兩個子機的起始狀態;新增接受狀態,接收來自兩個子機接受狀態的 -邊;狀態數 。對 ,從 的接受狀態向 的起始狀態添加一條 -邊;新機的起始與接受狀態分別是 的起始狀態和 的接受狀態。對 ,新增起始狀態 與接受狀態 ,並添加 -邊 、、 與 。「無入邊、無出邊」的性質可逐項檢查得到保持。正確性依賴這些性質:路徑只能在子機的起始狀態進入、只能從其接受狀態離開,所以每條接受路徑都分解為對子機的完整穿越。並的路徑恰走一個分支;連接的路徑先穿越 再穿越 ,得到 ;星號的路徑作 次完整穿越,得到 ,直接邊 提供 。
定理 1.2.8
(狀態消去遞推式)
設 是無 -移動的 NFA,狀態編號為 ,起始狀態為 。令 為所有從 到 、且中間狀態都屬於 的路徑所標記的字的集合。則 ,且
因此 ,是有限多個可由正則表達式給出的語言之並。
證明
(在主元狀態的各次出現處切開路徑)
基礎情形是一步路徑的定義,當 時空路徑貢獻 。對 ,考慮從 到 、中間狀態屬於 的路徑。若 從未作為中間狀態出現,則其字屬於 。否則,在 作為中間狀態的第一次與最後一次出現處切開,並在兩者之間的每次出現處也切開。首段從 到 ,中間各段從 到 ,末段從 到 ,每段的中間狀態都屬於 。這給出第二項;反之,把這樣的各段連接起來得到符合要求的路徑。該遞推式只證明正確性;所得表達式可能增長得非常快。
證明思路
定理 1.2.9
(正則語言的封閉性)
若 是正則語言,則 、 與 也是正則語言。
證明
(補、積與並)
對補集,取 為全函數的 DFA,交換接受與非接受狀態:每個字決定唯一的運行,所以它終於 當且僅當不終於 。對 與 的交集,在 上並行運行兩台機器,接受集為 ;對字歸納可知配對運行就是兩個運行的配對。並集可取至少有一個分量接受的狀態對,或用德摩根(De Morgan)律。
定理 1.2.10
(正則語言的泵引理)
設 是正則語言。則存在 ,使每個滿足 的 都可寫成 ,其中 ,,且對所有 有 。
證明
(對運行用鴿巢原理)
取 的 個狀態的 DFA,以及 滿足 。其運行的前 個狀態 不可能兩兩不同,故存在 使 。令 為前 個符號, 為接著的 個符號, 為其餘部分。則 ,並且從 讀入 又回到 ,所以讀入 ()也終於 。因此 的終止狀態與 或 相同,從而被接受。
定理 1.2.11
(可區分性下界)
若 兩兩被 區分,則識別 的每個 DFA 至少有 個狀態。
證明
(相同狀態必給出相同結果)
設 是 的 DFA。若對 有 ,則對每個 ,字 與 終於同一狀態,要麼都被接受要麼都被拒絕,這與可區分性矛盾。故 個狀態 互不相同。
反例模式
泵引理的條件是必要的,而非充分的
斷言(錯誤):若一個語言滿足泵引理的結論,則它是正則的。令 ,取 。 中長度至少為 的字以 、 或 開頭;令 為首字母,。若字以 或 開頭,則 變成 或 ,對所有 仍在第二部分中。若字為 ,則泵送給出 :當 時屬於第一部分,當 時得到 ,屬於第二部分。所以結論對 成立。然而 不是正則的:字 ()兩兩可區分,因為 ,而當 時 。由可區分性下界,不存在有限 DFA。修正:泵引理只有在其結論失敗時才能證明非正則;需要雙向檢驗時應使用可區分性。
例題
例題 1.2.12
(「倒數第二個符號是 1」的子集構造)
設 的狀態為 ,起始狀態為 ,接受集為 ,邊為 、、。從 出發:讀 留在 ,讀 到 。從 :讀 到 ,讀 到 。從 :讀 到 ,讀 到 。從 :讀 到 ,讀 到 。八個子集中有四個可達,含 的兩個是接受狀態。一個字被接受當且僅當其倒數第二個符號是 ,因為恰在讀到 時進入 ,再讀一個符號後到達 。
例題 1.2.13
(「 的個數為偶數」的狀態消去)
在 上,令狀態 (起始且接受)表示迄今 的個數為偶數,狀態 表示為奇數,讀 交換狀態,讀 留在原狀態。則 ,,,。可算得 ,,,,於是 ,這裏 表示語言相等。它描述了該語言,並且等於 ,後者是去掉狀態 、改寫狀態 上的環得到的表達式。兩種形式相等是通過共同的自動機驗證的,而不是靠符號操作。
例題 1.2.14
(質數長度的語言不是正則的)
令 ,並假設存在泵長度 。取質數 ,令 。則 ,。取 泵送:新長度為 ,是兩個不小於 的整數之積,因而是合數,所以 ,與引理矛盾。 的選取依賴於 是合法的,因為引理對所有 都成立。
例題 1.2.15
( 有無窮多個兩兩可區分的字)
對 ,字 兩兩可區分:取 ,則 ,而當 時 。所以對每個 ,識別 的任一 DFA 至少需要 個狀態,這對有限機器是不可能的,故 不是正則的。
反例模式
一個失敗的分解並不足夠
在 中,可用有效泵長度 :任何長度至少四的字都可泵送其第一個符號。字 亦有合法分解 、、。泵送兩次得到 ,不在 。但 是正則的:引理只要求存在一個合適分解,並不要求這個自行選取的分解成功。例如選初始零區塊中的 ,便可為此字構造有效迴圈。
例題 1.2.16
(一元平方長度語言不是正則的)
令 。假設其泵長度為 ,選 ,其長度至少為 。任何合法分解都有 ,其中 。取 ,新長度為 。
由於 ,
相鄰平方數之間沒有整數平方,因此 。這對每個合法分解都矛盾,即使我們不知道分解的具體位置也成立。
常見錯誤
常見錯誤
(交換標記不能求 NFA 的補)
交換 NFA 的接受與非接受狀態並不能得到其語言的補集;這只對完全 DFA 成立,因為 NFA 可能沿一條路徑接受某字而沿另一條路徑拒絕它。
常見錯誤
(空語言不是空字串)
把 當作 會令星號的結論出錯:,而 與任何語言連接都是空集。
常見錯誤
(泵引理的分解不是由你選的)
在泵引理的論證中,引理給你 與分解,分解不是由你選的。有效的證明必須處理所有滿足 且 的 。你只有兩步自由選擇:用 表示 ,以及選取 。最後,如上面的反例所示,泵引理不能用來證明某個語言是正則的。
另一個錯誤是把 當作實際得到的 DFA 的規模。它只是所有可達子集數的上界;不過指數級增長一般無法避免:「倒數第 個符號」的練習給出一個有 個狀態的 NFA,而任何對應的 DFA 都至少需要 個狀態。
總結
DFA、-NFA 與正則表達式定義同一類語言:子集構造把非確定性化為確定性,Thompson 構造把表達式化為自動機,消去遞推式把自動機化為表達式。該類對補、交、並封閉。泵送給出正則語言的一個必要性質,可區分的字則給出狀態數的定量下界。最小化算法以及按等價類的完整刻畫不在本節範圍內。
練習
快速檢查
(用泵引理證明 不是正則的。)
選一個前 個符號固定了被泵部分的字。
解答 · 答案
設 為泵長度,取 。任一分解都有 ,所以 ,。則 中 比 多,不屬於該語言,矛盾。
快速檢查
(給出一個 NFA ,使得交換其接受與非接受狀態所得的 NFA 並不接受 的補集。)
試試只有兩個狀態、一元字母表的 NFA。
解答 · 答案
取狀態 ,起始狀態 ,接受集 ,字母表 ,邊 與 。則 ,其補集為 。交換後接受集為 :字 到達 因而被接受,儘管 。所以新 NFA 接受整個 ,而不是 。
快速檢查
(對 ,令 為 上長度至少為 、且倒數第 個符號為 的字的集合。證明識別 的每個 DFA 至少有 個狀態。)
比較兩個長度為 的字,看它們第一個不同的位置。
解答 · 答案
取全部 個長度為 的字。若 在從左數第 位首次不同,附加 。則 與 的第 位分別是 與 (長度 )的倒數第 個符號,且兩者中恰有一個為 。所以 可區分,由可區分性下界得結論。
快速檢查
(用 NFA 證明正則語言 的反轉 是正則的。)
把 DFA 的每條邊反向。
解答 · 答案
設 是 的 DFA,把它看作只有一個起始狀態、接受集為 的 NFA。反轉每條邊,令舊起始狀態成為唯一接受狀態,並新增一個起始狀態,用 -邊指向 的每個成員。 中從 到某個 且標記為 的路徑,恰對應新機器中從 到 且標記為 的路徑。所以新的 -NFA 接受 當且僅當 ,由子集構造知 是正則的。若 ,新機器沒有接受路徑,而 確實如此。