確定有限狀態自動機

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

基礎概念

定義

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

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

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

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

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

擴展轉移函數

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

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

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

工作方式（正式的語義）

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

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

DFA與有向圖

主條目：狀態圖

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

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

利弊

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

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

其它

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

例子

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

${\displaystyle {\mathcal {A}}}$的狀態圖

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

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

	0	1
S1	S2	S1
S2	S1	S2

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

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

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

封閉性及一些運算

封閉性

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

補運算

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

交運算和並運算

有兩個DFA，${\displaystyle {\mathcal {A}}_{1}=(Q_{1},\Sigma ,\delta _{1},s_{1},F_{1})}$和${\displaystyle {\mathcal {A}}_{2}=(Q_{2},\Sigma ,\delta _{2},s_{2},F_{2})}$，那麼由這兩個DFA創造出來的新的自動機定義為：${\displaystyle {\mathcal {B}}=(Q_{1}\times Q_{2},\Sigma ,\delta _{\mathcal {B}},(s_{1},s_{2}),M)}$。其中${\displaystyle M\subseteq Q_{1}\times Q_{2}}$，${\displaystyle \left(s_{1},s_{2}\right)}$為${\displaystyle {\mathcal {B}}}$的開始狀態，${\displaystyle \delta _{\mathcal {B}}}$為${\displaystyle {\mathcal {B}}}$的轉移函數，且作如下定義：${\displaystyle \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. 當${\displaystyle M=F_{1}\times F_{2}}$時，由上述方法得到的${\displaystyle {\mathcal {B}}}$就是DFA ${\displaystyle {\mathcal {A}}_{1}}$和${\displaystyle {\mathcal {A}}_{2}}$的交運算，記作：${\displaystyle {\mathcal {B}}={\mathcal {A}}_{1}\cap {\mathcal {A}}_{2}}$。也就是說對於讀入的字符串w，當且僅當${\displaystyle {\mathcal {A}}_{1}}$和${\displaystyle {\mathcal {A}}_{2}}$同時接受w的時候${\displaystyle {\mathcal {B}}}$接受w。
2. 當${\displaystyle M=Q_{1}\times F_{2}\bigcup F_{1}\times Q_{2}}$時，由上述方法得到的${\displaystyle {\mathcal {B}}}$就是DFA ${\displaystyle {\mathcal {A}}_{1}}$和${\displaystyle {\mathcal {A}}_{2}}$的並運算，記作：${\displaystyle {\mathcal {B}}={\mathcal {A}}_{1}\cup {\mathcal {A}}_{2}}$。也就是說對於讀入的字符串w，只要${\displaystyle {\mathcal {A}}_{1}}$或${\displaystyle {\mathcal {A}}_{2}}$中至少有一個接受w，${\displaystyle {\mathcal {B}}}$就接受w。

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

同態和逆同態運算

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

• ${\displaystyle ~h(\epsilon )=\epsilon }$
• ${\displaystyle ~h(u\sigma )=h(u)h(\sigma )}$

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

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

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

最小自動機

主條目：確定有限狀態自動機最小化

等價類自動機

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

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

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

唯一性

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

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

算法

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

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

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

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

這樣就得到了接受相同語言的最小自動機。複雜度為${\displaystyle 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

參見

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