查看“︁非确定有限状态自动机”︁的源代码

{{NoteTA
|G1 = IT
}}
在[[计算理论]]中，'''非确定有限状态自动机'''或'''非确定有限自动机（NFA）'''是对每个状态和输入符号对可以有多个可能的下一个状态的[[有限状态自动机]]。这区别于[[确定有限状态自动机]]（DFA），它的下一个可能状态是唯一确定的。尽管DFA和NFA有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定NFA，都可以构造一个等价的DFA，反之亦然：通过使用[[幂集构造]]。两种类型的自动机只识别[[正则语言]]。非确定有限自动机有时被称为[[有限类型的子移位]]（subshift）。非确定有限状态自动机可推广为[[概率自动机]]，它为每个状态转移指派概率。

非确定有限自动机是[[Michael O. Rabin]]和[[达纳·斯科特]]（Dana Scott）在1959年介入的<ref>M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", ''IBM Journal of Research and Development'', '''3''':2 (1959) pp.115-125.</ref>，他们证明了它与确定自动机的等价性。

== 直观介绍 ==

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-元组]] <math>(Q, \Sigma, T, q_0, F)</math>，它构成自
* 状态的有限[[集合 (数学)|集合]]<math>Q</math>
* 输入[[符号]]的有限集合<math>\Sigma</math>
* 转移[[函数]]<math>T: Q \times (\Sigma \cup \{\epsilon \}) \to \mathcal{P}(Q)</math>
* “初始”（或“开始”）状态<math>q_0</math>，有着<math>q_0 \in Q</math>
* “接受”（或“最终”）状态的集合<math>F</math>，有着<math>F \subset Q</math>

这里的<math>\mathcal{P}(Q)</math>指示<math>Q</math>的幂集。“有ε-移动的NFA”（有时也叫做“NFA-ε”或“NFA-λ”）修订转移函数为允许[[空串]]ε作为可能的输入，结果为

:<math>T: Q \times (\Sigma \cup \{\epsilon \}) \to \mathcal{P}(Q)</math>。

可以证明普通NFA和有ε移动的NFA是等价的，给定任何一个都可以构造出识别同样语言的另一个。

== 性质 ==

机器开始于任意初始状态并读取来自它的符号表的符号的字符串。自动机使用状态[[转移函数]]''T''来使用当前状态，和刚读入的符号或空串来确定下一个状态。但是，“NFA的下一个状态不只依赖于当前输入事件，还依赖于任意数目的后续输入事件。直到这些后续事件出现才有可能确定这个机器所处的状态” <ref>FOLDOC Free Online Dictionary of Computing, ''[http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=nfa Finite State Machine]{{dead link|date=2018年2月 |bot=InternetArchiveBot |fix-attempted=yes }}''</ref>。如果在自动机完成读取的时候，它处于接受状态，则称NFA接受了这个字符串，否则称为它拒绝了这个字符串。

NFA接受的所有字符串的集合是NFA接受的语言。这个语言是[[正则语言]]。

对于所有NFA都可以找到接受同样语言的一个[[确定有限状态自动机]]（DFA）。所以出于实现（可能）更简单的机器的目的把现存的NFA转换成DFA是可行的。这是使用[[幂集构造]]进行的，这可能导致在必需状态的数目上的指数增长。幂集构造的形式证明在[[非确定有限自动机/Proofs|这里]]给出。

对于有状态的[[可数集合|可数无限]]集合的非确定有限自动机，幂集构造给出有状态的[[连续统]]的确定自动机因为可数无限集合的幂集是连续统：<math>2^{\aleph_0}=\aleph_1</math>)。在这种情况下，为了使状态转移有意义，状态的集合必须被赋予一个[[拓扑空间|拓扑]]。这种系统叫做[[拓扑自动机]]。

== NFA-ε的性质 ==

对于所有<math>p,q\in Q</math>，写<math>p\stackrel{\epsilon}{\rightarrow}q</math>当且仅当从<math>p</math>沿着零或更多个<math>\epsilon</math>箭头前进可到达<math>q</math>。换句话说，<math>p\stackrel{\epsilon}{\rightarrow}q</math>当且仅当存在<math>q_{1}, q_{2},\cdots q_{k}\in Q</math>这里的<math>k\geq 0</math>使得

:<math>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)</math>。

对于任何<math>p\in Q</math>，从''p''可到达的状态的集合叫做''p''的'''ε-闭包'''，并写为

:<math>\,E(\{p\}) = \{ q\in Q : p\stackrel{\epsilon}{\rightarrow}q\}</math>。

对于<math>P\subset Q</math>的任何子集，定义''P''的ε-闭包为
 
:<math>E(P) = \bigcup\limits_{p\in P}E(\{p\})</math>。

ε-转移是传递的，这可以证明，对于所有<math>q_{0}, q_{1}, q_{2}\in Q</math>和<math>P\subset Q</math>，如果<math>q_{1}\in E(\{q_{0}\})</math>且<math>q_{2}\in E(\{q_{1}\})</math>，则<math>q_{2}\in E(\{q_{0}\})</math>。

类似的，如果<math>q_{1}\in E(P)</math>且<math>q_{2}\in E(\{q_{1}\})</math>则<math>q_{2}\in E(P)</math>

设''x''是字母表Σ上的字符串。一个NFA-ε ''M''接受字符串''x''，如果存在''x''的形如''x<sub>1</sub>x<sub>2</sub> ... x<sub>n</sub>''的表示，这里的''x<sub>i</sub>'' ∈(Σ ∪{ε})，和状态序列 
''p<sub>0</sub>,p<sub>1</sub>, ..., p<sub>n</sub>''二者，这里的''p<sub>i</sub>'' ∈ ''Q''，满足下列条件：
# ''p<sub>0</sub>'' <math>\in</math> E({''q<sub>0</sub>''})
# ''p<sub>i</sub>'' <math>\in</math> E(''T''(''p<sub>i-1</sub>'', ''x<sub>i</sub> ''))对于''i'' = ''1, ..., n''
# ''p<sub>n</sub>'' <math>\in</math> ''F''。

特别注意某些字母''x<sub>i</sub>''可以是{ε}；它们不是选择自单独的Σ，而是来自Σ ∪{ε}。

== 实现 ==

有多种方式实现NFA:

* 转换成等价的DFA。在某些情况下这导致在自动机大小上的指数爆炸，从而辅助空间正比于在NFA中状态的数目（因为状态值存储要求给在NFA中的每个状态最多一位）。 
* 保持机器当前可能处在的所有状态的[[集合数据结构]]。在消耗最后一个输入符号的时候，如果这些状态之一是最终状态，则机器接受这个字符串。在最坏的情况下，这要求辅助空间正比于在NFA中状态的数目；如果集合结构为每个NFA状态使用一位，则这个方式等价于前者。
* 建立多个复件。对于每个n路决定，NFA建立这个机器的直到<math>n-1</math>个复件。每个都进入单独的状态。如果在耗尽最后的输入符号的时候，至少一个NFA复件处在接受状态，则NFA就接受它。（这也要求关于NFA状态数目的线性存储，因为对所有NFA状态都可能有一个机器）。
* 通过NFA的转移结构明确的传播（propagate）记号（token）并在一个记号到达最终状态的时候匹配。这在NFA应当编码触发转移的事件的额外上下文的时候是有用的。（对使用这种技术来跟踪对象引用的实现可查看[http://citeseer.ist.psu.edu/allan05adding.html Tracematches] {{Wayback|url=http://citeseer.ist.psu.edu/allan05adding.html |date=20080308040825 }}）。

== 例子 ==

下面的例子展示一个NFA ''M''，带有二进制字母表，它确定输入是否包含偶数个0或偶数个1。设''M'' =(''Q'', Σ, ''T'', ''s<sub>0</sub>'', ''F'')这里的
* Σ = {0, 1},
* ''Q'' = {''s''<sub>0</sub>, ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ''s''<sub>4</sub>},
* E({''s''<sub>0</sub>}) = { s<sub>0</sub>, s<sub>1</sub>, s<sub>3</sub> }
* ''F'' = {''s''<sub>1</sub>, ''s''<sub>3</sub>}，而
* 转移函数''T''定义自下列[[状态转移表]]：
::{| class=wikitable 
|
|<center>'''0'''</center>
|<center>'''1'''</center>
|<center>'''ε'''</center>
|-
|<center>'''''S''<sub>0</sub>'''</center>
|<center>{}</center>
|<center>{}</center>
|<center>{''S''<sub>1</sub>, ''S''<sub>3</sub>}</center>
|-
|<center>'''''S''<sub>1</sub>'''</center>
|<center>{''S''<sub>2</sub>}</center>
|<center>{''S''<sub>1</sub>}</center>
|<center>{}</center>
|-
|<center>'''''S''<sub>2</sub>'''</center>
|<center>{''S''<sub>1</sub>}</center>
|<center>{''S''<sub>2</sub>}</center>
|<center>{}</center>
|-
|<center>'''''S''<sub>3</sub>'''</center>
|<center>{''S''<sub>3</sub>}</center>
|<center>{''S''<sub>4</sub>}</center>
|<center>{}</center>
|-
|<center>'''''S''<sub>4</sub>'''</center>
|<center>{''S''<sub>4</sub>}</center>
|<center>{''S''<sub>3</sub>}</center>
|<center>{}</center>
|}

''M''的[[状态图]]是：

:[[File:NFAexample.svg|300px]]

''M''可以被看作两个[[确定有限状态自动机|DFA]]的并集：一个有状态{''S''<sub>2</sub>, ''S''<sub>1</sub>}而另一个有状态{''S''<sub>3</sub>, ''S''<sub>4</sub>}。 

''M''的语言可以描述为如下[[正则表达式]]给出的[[正则语言]]：
:<math>(1^*(01^*01^*)^*) \cup(0^*(10^*10^*)^*) </math>

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

<math>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)</math>

<math>F_1 = \{q \in Q_1| q\cap F \ne 0\}</math>

== NFA-ε的应用 ==

NFA和DFA是等价的，如果一个语言可被一个NFA识别，则它也可以被一个DFA识别，反之亦然。这种等价性的建立是重要和有用的。有用是因为构造识别给定语言的NFA有时比构造这个语言的DFA要容易很多。重要是因为NFA可以用来减少建立[[计算理论]]中很多重要性质的数学工作的复杂性。例如，使用NFA比使用DFA证明下列性质要更加容易：

（i）两个[[正则语言]]的并集是正则的。

（ii）两个[[正则语言]]的串接是正则的。

（iii）一个[[正则语言]]的[[Kleene星号|Kleene闭包]]是正则的。

== 参见 ==
* [[自动机]]
* [[确定有限状态自动机]]
* [[非确定有限状态自动机]]
* [[Mealy机]]
* [[Moore机]]
* [[算法状态机]]

== 引用 ==
=== 註釋 ===
<references/>
=== 參考文獻 ===
* 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.）''

[[Category:自动机]]
[[Category:编译原理]]