基本介紹
- 中文名：非確定有限狀態自動機
- 簡寫：NFA
- 領域：計算機
簡介,直觀介紹,形式定義,性質,實現,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, Σ,T,q0,F)，它構成自
這裡的P(Q)指示Q的冪集。“有ε-移動的NFA”（有時也叫做“NFA-ε”或“NFA-λ”）修訂轉移函式為允許空串ε作為可能的輸入，結果為
- T:Q×(Σ ∪{ε})→P(Q)。
可以證明普通NFA和有ε移動的NFA是等價的，給定任何一個都可以構造出識別同樣語言的另一個。
性質
機器開始於任意初始狀態並讀取來自它的符號表的符號的字元串。自動機使用狀態轉移函式T來使用當前狀態，和剛讀入的符號或空串來確定下一個狀態。但是，“NFA的下一個狀態不只依賴於當前輸入事件，還依賴於任意數目的後續輸入事件。直到這些後續事件出現才有可能確定這個機器所處的狀態”。如果在自動機完成讀取的時候，它處於接受狀態，則稱NFA接受了這個字元串，否則稱為它拒絕了這個字元串。
NFA接受的所有字元串的集合是NFA接受的語言。這個語言是正則語言。
對於所有NFA都可以找到接受同樣語言的一個確定有限狀態自動機（DFA）。所以出於實現（可能）更簡單的機器的目的把現存的NFA轉換成DFA是可行的。這是使用冪集構造進行的，這可能導致在必需狀態的數目上的指數增長。冪集構造的形式證明在這裡給出。
對於有狀態的可數無限集合的非確定有限自動機，冪集構造給出有狀態的連續統的確定自動機因為可數無限集合的冪集是連續統：
。在這種情況下，為了使狀態轉移有意義，狀態的集合必須被賦予一個拓撲。這種系統叫做拓撲自動機。
實現
有多種方式實現NFA:
- 轉換成等價的DFA。在某些情況下這導致在自動機大小上的指數爆炸，從而輔助空間正比於在NFA中狀態的數目（因為狀態值存儲要求給在NFA中的每個狀態最多一位）。
- 保持機器當前可能處在的所有狀態的集合數據結構。在消耗最後一個輸入符號的時候，如果這些狀態之一是最終狀態，則機器接受這個字元串。在最壞的情況下，這要求輔助空間正比於在NFA中狀態的數目；如果集合結構為每個NFA狀態使用一位，則這個方式等價於前者。
- 創建多個復件。對於每個n路決定，NFA創建這個機器的直到{\displaystyle n-1}個復件。每個都進入單獨的狀態。如果在耗盡最後的輸入符號的時候，至少一個NFA復件處在接受狀態，則NFA就接受它。（這也要求關於NFA狀態數目的線性存儲，因為對所有NFA狀態都可能有一個機器）。
- 通過NFA的轉移結構明確的傳播（propagate）記號（token）並在一個記號到達最終狀態的時候匹配。這在NFA應當編碼觸發轉移的事件的額外上下文的時候是有用的。（對使用這種技術來跟蹤對象引用的實現可查看Tracematches）。
NFA-ε的套用
NFA和DFA是等價的，如果一個語言可被一個NFA識別，則它也可以被一個DFA識別，反之亦然。這種等價性的創建是重要和有用的。有用是因為構造識別給定語言的NFA有時比構造這個語言的DFA要容易很多。重要是因為NFA可以用來減少創建計算理論中很多重要性質的數學工作的複雜性。例如，使用NFA比使用DFA證明下列性質要更加容易：
（i）兩個正則語言的並集是正則的。
（ii）兩個正則語言的串接是正則的。
（iii）一個正則語言的Kleene閉包是正則的。
