确定有限状态自动机

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

## 基礎概念

### 定義

確定有限狀態自動機 ${\mathcal {A}}$ 是由

* 一個非空有限的狀態集合 $Q$
* 一個輸入字母表 $\Sigma $ （非空有限的字元集合）
* 一個轉移函式 $\delta :Q\times \Sigma \rightarrow Q$ （例如： $\delta \left(q,\sigma \right)=p,\left(p,q\in Q,\sigma \in \Sigma \right)$ ）
* 一個開始狀態 $s\in Q$
* 一個接受狀態的集合 $F\subseteq Q$

所組成的 5 - 元組。因此一個 DFA 可以寫成這樣的形式： ${\mathcal {A}}=\left(Q,\Sigma ,\delta ,s,F\right)$ 。

### 工作方式（非正式的語意）

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

### 擴充轉移函式

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

　
: $\delta ^{*}:Q\times \Sigma ^{*}\rightarrow Q$ 。

 * $\delta ^{*}\left(q,w\right)$ 是自動機從狀態 q 順序讀入字串 w 後達到的狀態
* 擴充轉移函式遞迴的定義為：
   * $\delta ^{*}\left(q,\epsilon \right)=q$
  * $\delta ^{*}\left(q,u\sigma \right)=\delta (\delta ^{*}(q,u),\sigma ),\forall u\in \Sigma ^{*},\sigma \in \Sigma $

### 工作方式（正式的語意）

對於一個確定有限狀態自動機 ${\mathcal {A}}=\left(Q,\Sigma ,\delta ,s,F\right)$ ，如果 $\delta ^{*}\left(s,w\right)\in F$ ，我們就說該自動機接受字串 w，反之則表明該自動機拒絕字串 w。

被一個確定有限自動機接受的語言（或者叫「被辨識的語言」）定義為： ${\mathcal {L}}({\mathcal {A}})=\{w\in \Sigma ^{*}|{\mathcal {A}}~$ 接受字串 $~w\}$ ，也就是由所有被接受的字串組成的集合。

### DFA 與有向圖

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

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

### 利弊

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

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

### 其它

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

## 例子

下面是一個確定有限狀態自動機的例子。

確定有限狀態自動機 ${\mathcal {A}}=\left(Q,\Sigma ,\delta ,s,F\right)$

 * $Q=\{S_{1},S_{2}\}$
* $\Sigma =\{0,1\}$
* $s=S_{1}$
* $F=\{S_{1}\}$
* $\delta $ 由下面的狀態轉移表定義：

　
:

* 對應的轉移函式為：
   * $\delta (S_{1},0)=S_{2}$
  * $\delta (S_{1},1)=S_{1}$
  * $\delta (S_{2},0)=S_{1}$
  * $\delta (S_{2},1)=S_{2}$

狀態 $S_{1}$ 表示在輸入的字串中有偶數個 0，而 $S_{2}$ 表示有奇數個 0。在輸入中 1 不改變自動機的狀態。當讀完輸入的字串的時候，狀態將顯示輸入的字串是否包含偶數個 0。

 ${\mathcal {A}}$ 能辨識的語言是 ${\mathcal {L}}({\mathcal {A}})=\{w|\#_{0}(w)\equiv 0~(mod~2)\}$ 。用正規表示式表示為： $(1^{*}(01^{*}0)^{*})^{*}$ 。

## 封閉性及一些運算

### 封閉性

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

### 補運算

 ${\mathcal {A}}=(Q,\Sigma ,\delta ,s,F)$ 是一個 DFA，那麼由補運算產生的新 DFA 定義為： ${\bar {\mathcal {A}}}=(Q,\Sigma ,\delta ,s,Q-F)$ 。顯然只要將 ${\mathcal {A}}$ 中接受的狀態設為不接受的狀態，同時把不接受的狀態設為接受的狀態就得到 ${\bar {\mathcal {A}}}$ 。補運算的複雜度是： $O(\left|Q\right|)$ 。

### 交運算和並運算

有兩個 DFA， ${\mathcal {A}}_{1}=(Q_{1},\Sigma ,\delta _{1},s_{1},F_{1})$ 和 ${\mathcal {A}}_{2}=(Q_{2},\Sigma ,\delta _{2},s_{2},F_{2})$ ，那麼由這兩個 DFA 創造出來的新的自動機定義為： ${\mathcal {B}}=(Q_{1}\times Q_{2},\Sigma ,\delta _{\mathcal {B}},(s_{1},s_{2}),M)$ 。其中 $M\subseteq Q_{1}\times Q_{2}$ ， $\left(s_{1},s_{2}\right)$ 為 ${\mathcal {B}}$ 的開始狀態， $\delta _{\mathcal {B}}$ 為 ${\mathcal {B}}$ 的轉移函式，且作如下定義： $\forall q_{1}\in Q_{1},~q_{2}\in Q_{2},~\sigma \in \Sigma :\delta _{\mathcal {B}}((q_{1},q_{2}),\sigma )=(\delta _{1}(q_{1},\sigma ),\delta _{2}(q_{2},\sigma ))$ 。

1. 當 $M=F_{1}\times F_{2}$ 時，由上述方法得到的 ${\mathcal {B}}$ 就是 DFA ${\mathcal {A}}_{1}$ 和 ${\mathcal {A}}_{2}$ 的交運算，記作： ${\mathcal {B}}={\mathcal {A}}_{1}\cap {\mathcal {A}}_{2}$ 。也就是說對於讀入的字串 w，若且唯若 ${\mathcal {A}}_{1}$ 和 ${\mathcal {A}}_{2}$ 同時接受 w 的時候 ${\mathcal {B}}$ 接受 w。
2. 當 $M=Q_{1}\times F_{2}\bigcup F_{1}\times Q_{2}$ 時，由上述方法得到的 ${\mathcal {B}}$ 就是 DFA ${\mathcal {A}}_{1}$ 和 ${\mathcal {A}}_{2}$ 的並運算，記作： ${\mathcal {B}}={\mathcal {A}}_{1}\cup {\mathcal {A}}_{2}$ 。也就是說對於讀入的字串 w，只要 ${\mathcal {A}}_{1}$ 或 ${\mathcal {A}}_{2}$ 中至少有一個接受 w， ${\mathcal {B}}$ 就接受 w。

交運算和並運算的複雜度都是 $O(\left|Q_{1}\right|\left|Q_{2}\right|\left|\Sigma \right|)$ 。

### 同態和逆同態運算

一個同態函式 $h:\Sigma ^{*}\rightarrow \Gamma ^{*}$ 可以遞迴的定義為：

 * $~h(\epsilon )=\epsilon $
* $~h(u\sigma )=h(u)h(\sigma )$

於是則有 $~h(uv)=h(u)h(v)$ 。（以上所述中 $~\epsilon $ 為空字元， $~u,v\in \Sigma ^{*},\sigma \in \Sigma $ ）

 1. ${\mathcal {L}}\subseteq \Sigma ^{*}:h({\mathcal {L}}):=\{h(w)~|~w\in {\mathcal {L}}\}$ ：對於接受語言 L 的 DFA，只要將其中代表 $~\delta (q,\sigma )$ 的邊替換成一個序列 $~h(\sigma )$ 並在其中加入不屬於原 DFA 狀態的新狀態，就產生了接受語言 h (L) 的 DFA。
2. ${\mathcal {L}}\subseteq \Gamma ^{*}:h^{-1}({\mathcal {L}}):=\{w~|~h(w)\in {\mathcal {L}}\}$ ：定義一個 $~Q,\Sigma ,s,F$ 都不變的新 DFA，並定義新的轉移函式為 $~\delta '(q,\sigma ):=\delta ^{*}(q,h(\sigma ))$ ，則 $~(Q,\Sigma ,\delta ',s,F)$ 就是逆同態運算產生的新 DFA。

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

## 最小自動機

### 等價類自動機

對於一個正規語言，接受該語言的等價類自動機是一個 $~(Q,\Sigma ,\delta ,s,F)$ 的 5 - 元組。其定義如下：

* Q 是等價關係～L 的等價類的集合： $[x],x\in \Sigma ^{*}$ 的集合
* $~s=[\epsilon ]$
* $F=\{[x]~|~x\in L\}$
* $~\delta ([x],\sigma )=[x\sigma ]$

~L 被稱為 Nerode 關係，是 Myhill-Nerode 定理的基礎。簡單的來說就是對於任意 $~x,y,z\in \Sigma ^{*}$ ，如果 $xz\in L\Leftrightarrow yz\in L$ ，那麼 x~Ly。

### 唯一性

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

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

### 演算法

定義一個非等價關係： $N:=\{(p,q)~|~p,q\in Q,\exists w\in \Sigma ^{*}:\delta ^{*}(p,w)\in F\leftrightarrow \delta ^{*}(q,w)\notin F\}$ ，如下步驟可以得到這個集合 N：

1. 如果 $p\in F,~q\notin F$ ，就給所有的狀態對 (p,q) 和 (q,p) 打上標記
2. 重複步驟 3，直到所標記的狀態對沒有變化為止
3. 對於未標記的狀態對 (p,q) 和 σ，如果 $~(\delta (p,\sigma ),\delta (q,\sigma ))$ 被標記過了就把 (p,q) 也標記上
4. 以上所有標記了的狀態對的集合就是非等價關係 N

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

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

這樣就得到了接受相同語言的最小自動機。複雜度為 $O(\left|Q\right|^{2}\left|\Sigma \right|)$ 。

## 參照

* Michael Sipser, _Introduction to the Theory of Computation_. PWS, Boston. 1997. ISBN 0-534-94728-X. Section 1.1: Finite Automata, pp.31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.4.4 DFA can accept only regular language

## 參見

* 無環確定有限狀態自動機
* 非確定有限狀態自動機
* 圖靈機
* 讀只右移圖靈機