確定有限狀態自動機

在計算理論中，確定有限狀態自動機或確定有限自動機（英語：deterministic finite automation, DFA）是一個能實現狀態轉移的自動機。對於一個給定的屬於該自動機的狀態和一個屬於該自動機字母表求和的字元，它都能根據事先給定的轉移函式轉移到下一個狀態（這個狀態可以是先前那個狀態）。

基本介紹

• 中文名：確定有限狀態自動機
• 外文名：deterministic finite automation
• 縮寫：DFA
• 領域：計算機

基礎概念

定義

確定有限狀態自動機 是由

一個非空有限的狀態集合 ；

一個輸入字母表（非空有限的字元集合）；

一個轉移函式 （例如： ）；

一個開始狀態 ；

一個接受狀態的集合 ；

所組成的5-元組。因此一個DFA可以寫成這樣的形式： 。

工作方式（非正式的語義）

確定有限狀態自動機從起始狀態開始，一個字元接一個字元地讀入一個字元串 （這裡的 指示Kleene星號運算元。），並根據給定的轉移函式一步一步地轉移至下一個狀態。在讀完該字元串後，如果該自動機停在一個屬於F的接受狀態，那么它就接受該字元串，反之則拒絕該字元串。

擴展轉移函式

為了在保證嚴謹的前提下，方便地敘述關於DFA的內容，我們定義如下擴展的轉移函式：

是自動機從狀態q順序讀入字元串w後達到的狀態。

擴展轉移函式遞歸的定義為：

工作方式（正式的語義）

對於一個確定有限狀態自動機 ，如果 ，我們就說該自動機接受字元串w，反之則表明該自動機拒絕字元串w。

被一個確定有限自動機接受的語言（或者叫“被識別的語言”）定義為 接受字元串 ，也就是由所有被接受的字元串組成的集合。

DFA與有向圖

除了數學上的嚴謹表述，通常為了討論方便，也使用狀態圖直觀地表示DFA。不難發現，對於一個給定的DFA，存在唯一一個對應的有向圖（但是嚴格意義上一個有向圖不能確定出唯一一個DFA）。有向圖的每個結點對應一個狀態，每條有向邊對應一種轉移。習慣上將結點畫成兩個圈表示接受狀態，一個圈表示拒絕狀態。用一條沒有起點的邊指向起始狀態。

除了在表述上方便以外，在研究某些問題（如“給定的DFA的語言是否為無窮集合”）時，狀態圖也提供了有效的解法。

利弊

DFA是一種實際的計算模型，因為有平凡的線性時間、恆定空間的線上算法模擬在輸入流上的DFA。給定兩個DFA有有效算法找到識別它們所識別語言的並集、交集和補集的DFA。還有有效算法確定一個DFA是否接受任何給定字元串，一個DFA是否接受所有字元串，兩個DFA是否識別同樣的語言，和對特定正則語言找到狀態數目最小的DFA（最小DFA）。

在另一方面，DFA在可識別的語言上有嚴格的限制—很多簡單的語言，包括需要多於恆定空間來解決的任何問題，不能被DFA識別。經典的DFA不能識別的簡單語言的例子是括弧語言，就是由正確配對的括弧組成的語言，比如 (()())。由形如ab的字元串組成的語言，就是有限數目個a，隨後是相等數目個b。可以證明沒有DFA有足夠狀態來識別這種語言（通俗地說，因為需要至少2n個狀態，而n是不恆定的）。

其他

1. 能被確定有限狀態自動機識別的語言是正則語言。
   
2. 確定有限狀態自動機是非確定有限狀態自動機的一種極限形式。
   
3. 確定有限狀態自動機在計算能力上等價於非確定有限狀態自動機。
   
4. 沒有接受狀態列表並沒有指定開始狀態的確定有限狀態機叫做轉移系統或半自動機。
   

封閉性及一些運算

封閉性

確定有限狀態自動機的交，並，差，補，連線，替換，同態，逆同態等運算是封閉的，也就是說確定有限狀態自動機通過這些運算產生的新的自動機也是確定有限狀態自動機。

補運算

是一個DFA，那么由補運算產生的新DFA定義為： 。顯然只要將 中接受的狀態設為不接受的狀態，同時把不接受的狀態設為接受的狀態就得到 。補運算的複雜度是： 。

交運算和並運算

有兩個DFA， 和 ，那么由這兩個DFA創造出來的新的自動機定義為： 。其中 ， 為 的開始狀態， 為 的轉移函式，且作如下定義： 。

當 時，由上述方法得到的 就是DFA 和 的交運算，記作 。也就是說對於讀入的字元串w，若且唯若 和 同時接受w的時候 接受w。

當 時，由上述方法得到的 就是DFA 和 的並運算，記作： 。也就是說對於讀入的字元串w，只要 或 中至少有一個接受w， 就接受w。

交運算和並運算的複雜度都是 。

同態和逆同態運算

一個同態函式可以遞歸的定義為：

於是則有。（以上所述中為空字元，）

：對於接受語言L的DFA，只要將其中代表的邊替換成一個序列並在其中加入不屬於原DFA狀態的新狀態，就產生了接受語言h(L)的DFA。

：定義一個都不變的新DFA，並定義新的轉移函式為，則就是逆同態運算產生的新DFA。

此外替換運算和逆同態運算的方法近似。

最小自動機

等價類自動機

對於一個正則語言，接受該語言的等價類自動機是一個的5-元組。其定義如下：

Q是等價關係~_L的等價類的集合：的集合

~_L被稱為Nerode關係，是Myhill-Nerode定理的基礎。簡單的來說就是對於任意，如果，那么x~_Ly。

唯一性

對於任意給定的確定有限狀態自動機都能找到一個與之計算能力等價的最小確定有限狀態自動機，簡稱最小自動機。該最小自動機中狀態的數量等於能識別相同語言的等價類自動機中等價關係的數量，我們可以稱最小自動機和等價類自動機“實際上”是相等的，也就是同構。非正式的說法是：對於最小自動機上的任意狀態都可以通過一個同構函式變換成等價類自動機上的一個狀態。

能識別一個正則語言的等價類自動機是唯一的，因此能識別該語言的最小自動機也是唯一的。

算法

定義一個非等價關係：，如下步驟可以得到這個集合N：

1.如果，就給所有的狀態對(p,q)和(q,p)打上標記

2.重複步驟3，直到所標記的狀態對沒有變化為止

3.對於未標記的狀態對(p,q)和σ，如果被標記過了就把(p,q)也標記上

4.以上所有標記了的狀態對的集合就是非等價關係N

以下是由一個任意DFA轉換到一個最小DFA的步驟：

1. 把所有不能從開始狀態達到的狀態刪除
   
2. 通過上述標記算法計算非等價關係N
   
3. 一步一步將不屬於N的狀態對中的兩個狀態合成一個狀態
   

這樣就得到了接受相同語言的最小自動機。複雜度為 。