非确定有限状态自动机

在計算理論中，**非確定有限狀態自動機**或**非確定有限自動機（NFA）** 是對每個狀態和輸入符號對可以有多個可能的下一個狀態的有限狀態自動機。這區別於確定有限狀態自動機（DFA），它的下一個可能狀態是唯一確定的。儘管 DFA 和 NFA 有不同的定義，在形式理論中可以證明它們是等價的；就是說，對於任何給定 NFA，都可以構造一個等價的 DFA，反之亦然：通過使用冪集構造。兩種類型的自動機只辨識正規語言。非確定有限自動機有時被稱為有限類型的子移位（subshift）。非確定有限狀態自動機可推廣為概率自動機，它為每個狀態轉移指派概率。

非確定有限自動機是 Michael O. Rabin 和達納・斯科特（Dana Scott）在 1959 年介入的，他們證明了它與確定自動機的等價性。

## 直觀介紹

NFA 同 DFA 一樣，消耗輸入符號的字串。對每個輸入符號它變換到一個新狀態直到所有輸入符號到被耗盡。

不像 DFA，非確定意味著對於任何輸入符號，它的下一個狀態不是唯一確定的，可以是多個可能狀態中的任何一個。因此在形式定義中，一般都談論狀態冪集的子集：轉移函式不提供一個單一狀態，而是提供所有可能狀態的某個子集。

一種擴充的 NFA 是 **NFA-λ**（也叫做 **NFA-ε** 或**有 ε 移動的 NFA**），它允許到新狀態的變換不消耗任何輸入符號。例如，如果它處於狀態 1，下一個輸入符號是 _a_，它可以移動到狀態 2 而不消耗任何輸入符號，因此就有了歧義：在消耗字母 _a_ 之前系統是處於狀態 1 還是狀態 2 呢？由於這種歧義性，可以更加方便的談論系統可以處在的可能狀態的集合。因此在消耗字母 _a_ 之前，NFA-ε 可以處於集合 {1,2} 內的狀態中的任何一個。等價的說，你可以想像這個 NFA 同時處於狀態 1 和狀態 2: 這給出了對冪集構造的非正式提示：等價於這個 NFA 的 DFA 被定義為此時處於狀態 _q_={1,2} 中。不消耗輸入符號的到新狀態的變換叫做 **λ 轉移**或 **ε 轉移**。它們通常標記著希臘字母 λ 或 ε。

接受輸入的概念類似於 DFA。當最後的輸入字元被消耗的時候，NFA 接受這個字串，若且唯若有某個轉移集合把它帶到一個接受狀態。等價的說，它拒絕這個字串，如果不管應用什麼轉移，它都不能結束於接受狀態。

## 形式定義

通常定義兩種類似類型的 NFA: NFA 和「有 ε- 移動的 NFA」。普通的 NFA 被定義為 5 - 元組 $(Q,\Sigma ,T,q_{0},F)$ ，它構成自

* 狀態的有限集合 $Q$
* 輸入符號的有限集合 $\Sigma $
* 轉移函式 $T:Q\times (\Sigma \cup \{\epsilon \})\to {\mathcal {P}}(Q)$
* 「初始」（或「開始」）狀態 $q_{0}$ ，有著 $q_{0}\in Q$
* 「接受」（或「最終」）狀態的集合 $F$ ，有著 $F\subset Q$

這裡的 ${\mathcal {P}}(Q)$ 指示 $Q$ 的冪集。「有 ε- 移動的 NFA」（有時也叫做「NFA-ε」或「NFA-λ」）修訂轉移函式為允許空字串 ε 作為可能的輸入，結果為

　
: $T:Q\times (\Sigma \cup \{\epsilon \})\to {\mathcal {P}}(Q)$ 。

可以證明普通 NFA 和有 ε 移動的 NFA 是等價的，給定任何一個都可以構造出辨識同樣語言的另一個。

## 性質

機器開始於任意初始狀態並讀取來自它的符號表的符號的字串。自動機使用狀態轉移函式 _T_ 來使用當前狀態，和剛讀入的符號或空字串來確定下一個狀態。但是，「NFA 的下一個狀態不只依賴於當前輸入事件，還依賴於任意數目的後續輸入事件。直到這些後續事件出現才有可能確定這個機器所處的狀態」 。如果在自動機完成讀取的時候，它處於接受狀態，則稱 NFA 接受了這個字串，否則稱為它拒絕了這個字串。

NFA 接受的所有字串的集合是 NFA 接受的語言。這個語言是正規語言。

對於所有 NFA 都可以找到接受同樣語言的一個確定有限狀態自動機（DFA）。所以出於實現（可能）更簡單的機器的目的把現存的 NFA 轉換成 DFA 是可行的。這是使用冪集構造進行的，這可能導致在必需狀態的數目上的指數增長。冪集構造的形式證明在這裡給出。

對於有狀態的可數無限集合的非確定有限自動機，冪集構造給出有狀態的連續統的確定自動機因為可數無限集合的冪集是連續統： $2^{\aleph _{0}}=\aleph _{1}$ )。在這種情況下，為了使狀態轉移有意義，狀態的集合必須被賦予一個拓撲。這種系統叫做拓撲自動機。

## NFA-ε 的性質

對於所有 $p,q\in Q$ ，寫 $p{\stackrel {\epsilon }{\rightarrow }}q$ 若且唯若從 $p$ 沿著零或更多個 $\epsilon $ 箭頭前進可到達 $q$ 。換句話說， $p{\stackrel {\epsilon }{\rightarrow }}q$ 若且唯若存在 $q_{1},q_{2},\cdots q_{k}\in Q$ 這裡的 $k\geq 0$ 使得

　
: $q_{1}\in T(p,\epsilon ),q_{2}\in T(q_{1},\epsilon )\cdots ,q_{k}\in T(q_{k-1},\epsilon ),q\in T(q_{k},\epsilon )$ 。

對於任何 $p\in Q$ ，從 _p_ 可到達的狀態的集合叫做 _p_ 的 **ε- 閉包**，並寫為

　
: $\,E(\{p\})=\{q\in Q:p{\stackrel {\epsilon }{\rightarrow }}q\}$ 。

對於 $P\subset Q$ 的任何子集，定義 _P_ 的 ε- 閉包為

　
: $E(P)=\bigcup \limits _{p\in P}E(\{p\})$ 。

ε- 轉移是傳遞的，這可以證明，對於所有 $q_{0},q_{1},q_{2}\in Q$ 和 $P\subset Q$ ，如果 $q_{1}\in E(\{q_{0}\})$ 且 $q_{2}\in E(\{q_{1}\})$ ，則 $q_{2}\in E(\{q_{0}\})$ 。

類似的，如果 $q_{1}\in E(P)$ 且 $q_{2}\in E(\{q_{1}\})$ 則 $q_{2}\in E(P)$

設 _x_ 是字母表 Σ 上的字串。一個 NFA-ε _M_ 接受字串 _x_，如果存在 _x_ 的形如 _x1x2 ... xn_ 的表示，這裡的 _xi_ ∈(Σ ∪{ε})，和狀態序列 _p0,p1, ..., pn_ 二者，這裡的 _pi_ ∈ _Q_，滿足下列條件：

1. _p0_ $\in $ E({_q0_})
2. _pi_ $\in $ E(_T_(_pi-1_, _xi_ )) 對於 _i_ = _1, ..., n_
3. _pn_ $\in $ _F_。

特別注意某些字母 _xi_ 可以是 {ε}；它們不是選擇自單獨的 Σ，而是來自 Σ ∪{ε}。

## 實現

有多種方式實現 NFA:

* 轉換成等價的 DFA。在某些情況下這導致在自動機大小上的指數爆炸，從而輔助空間正比於在 NFA 中狀態的數目（因為狀態值儲存要求給在 NFA 中的每個狀態最多一位）。
* 保持機器當前可能處在的所有狀態的集合資料結構。在消耗最後一個輸入符號的時候，如果這些狀態之一是最終狀態，則機器接受這個字串。在最壞的情況下，這要求輔助空間正比於在 NFA 中狀態的數目；如果集合結構為每個 NFA 狀態使用一位，則這個方式等價於前者。
* 建立多個復件。對於每個 n 路決定，NFA 建立這個機器的直到 $n-1$ 個復件。每個都進入單獨的狀態。如果在耗盡最後的輸入符號的時候，至少一個 NFA 復件處在接受狀態，則 NFA 就接受它。（這也要求關於 NFA 狀態數目的線性儲存，因為對所有 NFA 狀態都可能有一個機器）。
* 通過 NFA 的轉移結構明確的傳播（propagate）記號（token）並在一個記號到達最終狀態的時候匹配。這在 NFA 應當編碼觸發轉移的事件的額外上下文的時候是有用的。（對使用這種技術來跟蹤物件參照的實現可檢視 Tracematches （頁面存檔備份，存於網際網路檔案館））。

## 例子

下面的例子展示一個 NFA _M_，帶有二進位字母表，它確定輸入是否包含偶數個 0 或偶數個 1。設 _M_ =(_Q_, Σ, _T_, _s0_, _F_) 這裡的

* Σ = {0, 1},
* _Q_ = {_s_0, _s_1, _s_2, _s_3, _s_4},
* E({_s_0}) = { s0, s1, s3 }
* _F_ = {_s_1, _s_3}，而
* 轉移函式 _T_ 定義自下列狀態轉移表：

　
: :

_M_ 的狀態圖是：

　
:

_M_ 可以被看作兩個 DFA 的併集：一個有狀態 {_S_2, _S_1} 而另一個有狀態 {_S_3, _S_4}。 

_M_ 的語言可以描述為如下正規表示式給出的正規語言：

　
: $(1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})$

## NFA 與 DFA

NFA 與確定有限自動機（DFA，或簡稱 FA）的辨識能力是一樣的，因而兩者是等價的。每個 FA 也可以寫成 NFA 的形式，只要把轉換函式由 $\delta (q_{n-1},x)=q_{n}$ 改寫成 $\delta (q_{n-1},x)=\{q_{n}\}$ 就可以，即是與之等價的 NFA 的轉換函式的輸出結果即是 FA 的轉換函式的輸出結果的單元集。反之，對任何 NFA _M_=(_Q_, Σ, δ, _q_0, _F_) 來說，如果它可以接受語言 L，則必定存在某個 FA _M_1=(_Q_1, Σ, δ1, _q_1, _F_1)，也可以接受 L。可以從「狀態」的定義下手「消除」NFA 的不確定性。NFA 的轉換函式的輸出結果本為狀態集合 _Q_ 的子集合，現在把這一個子集合當成一個狀態看待，即是 FA _M_1 中的狀態是 NFA 中狀態集合的子集合。這技巧叫做子集合的建構（subset construction）。即是

$$
Q_{1}=2^{Q}{\text{ and }}q_{1}=\{q_{0}\}{\text{ for }}q\in Q_{1}{\text{ and }}a\in \Sigma ,\delta _{1}(q,a)=\bigcup _{p\in q}\delta (p,a)
$$

$$
F_{1}=\{q\in Q_{1}|q\cap F\neq 0\}
$$

## NFA-ε 的應用

NFA 和 DFA 是等價的，如果一個語言可被一個 NFA 辨識，則它也可以被一個 DFA 辨識，反之亦然。這種等價性的建立是重要和有用的。有用是因為構造辨識給定語言的 NFA 有時比構造這個語言的 DFA 要容易很多。重要是因為 NFA 可以用來減少建立計算理論中很多重要性質的數學工作的複雜性。例如，使用 NFA 比使用 DFA 證明下列性質要更加容易：

（i）兩個正規語言的併集是正則的。

（ii）兩個正規語言的串接是正則的。

（iii）一個正規語言的 Kleene 閉包是正則的。

## 參見

* 自動機
* 確定有限狀態自動機
* 非確定有限狀態自動機
* Mealy 機
* Moore 機
* 演算法狀態機

## 參照

### 註釋

### 參考文獻

* Michael Sipser, _Introduction to the Theory of Computation_. PWS, Boston. 1997. ISBN 0-534-95097-3. _（see section 1.2: Nondeterminism, pp.47–63.）_
* John E. Hopcroft and Jeffrey D. Ullman, _Introduction to Automata Theory, Languages and Computation_, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. _（See chapter 2.）_