非確定有限狀態自動機

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

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

直觀介紹

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-元組 ${\displaystyle (Q,\Sigma ,T,q_{0},F)}$，它構成自

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

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

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

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

性質

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

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

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

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

NFA-ε的性質

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

${\displaystyle 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 )}$。

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

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

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

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

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

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

設x是字母表Σ上的字串。一個NFA-ε M接受字串x，如果存在x的形如x₁x₂ ... x_n的表示，這裏的x_i ∈(Σ ∪{ε})，和狀態序列 p₀,p₁, ..., p_n二者，這裏的p_i ∈ Q，滿足下列條件：

1. p₀ ${\displaystyle \in }$ E({q₀})
2. p_i ${\displaystyle \in }$ E(T(p_i-1, x_i ))對於i = 1, ..., n
3. p_n ${\displaystyle \in }$ F。

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

實現

有多種方式實現NFA:

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

例子

下面的例子展示一個NFA M，帶有二進制字母表，它確定輸入是否包含偶數個0或偶數個1。設M =(Q, Σ, T, s₀, F)這裏的

• Σ = {0, 1},
• Q = {s₀, s₁, s₂, s₃, s₄},
• E({s₀}) = { s₀, s₁, s₃ }
• F = {s₁, s₃}，而
• 轉移函數T定義自下列狀態轉移表：

	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

M的狀態圖是：

M可以被看作兩個DFA的併集：一個有狀態{S₂, S₁}而另一個有狀態{S₃, S₄}。

M的語言可以描述為如下正則表達式給出的正則語言：

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

NFA與DFA

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

${\displaystyle 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)}$

${\displaystyle 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機
• 演算法狀態機

參照

註釋

1. M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp.115-125.
2. FOLDOC Free Online Dictionary of Computing, Finite State Machine^{[永久失效連結]}

參考文獻

• 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.）