非確定有限狀態自動機

非確定有限狀態自動機區別於確定有限狀態自動機（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接受這個字符串，當且僅當有某個轉移集合把它帶到一個接受狀態。等價的説，它拒絕這個字符串，如果不管應用什麼轉移，它都不能結束於接受狀態。 ^[1] 

通常定義兩種類似類型的NFA: NFA和“有ε-移動的NFA”。普通的NFA被定義為5-元組(Q, Σ,T,q₀,F)，它構成自

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

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

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

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

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

對於有狀態的可數無限集合的非確定有限自動機，冪集構造給出有狀態的連續統的確定自動機因為可數無限集合的冪集是連續統：

。在這種情況下，為了使狀態轉移有意義，狀態的集合必須被賦予一個拓撲。這種系統叫做拓撲自動機。 ^[1] 

有多種方式實現NFA:

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

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

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

（iii）一個正則語言的Kleene閉包是正則的。 ^[2]