[科普中国]-非确定有限状态自动机

在计算理论中，非确定有限状态自动机或**非确定有限自动机（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接受这个字符串，当且仅当有某个转移集合把它带到一个接受状态。等价的说，它拒绝这个字符串，如果不管应用什么转移，它都不能结束于接受状态。1

形式定义通常定义两种类似类型的NFA: NFA和“有ε-移动的NFA”。普通的NFA被定义为5-元组(Q, Σ,T,q0,F)，它构成自

状态的有限集合Q

输入符号的有限集合Σ

转移函数T:Q×Σ →P(Q)

“初始”（或“开始”）状态q0，有着q0∈Q

“接受”（或“最终”）状态的集合F，有着F⊆Q

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

T:Q×(Σ ∪{ε})→P(Q)。

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

性质机器开始于任意初始状态并读取来自它的符号表的符号的字符串。自动机使用状态转移函数T来使用当前状态，和刚读入的符号或空串来确定下一个状态。但是，“NFA的下一个状态不只依赖于当前输入事件，还依赖于任意数目的后续输入事件。直到这些后续事件出现才有可能确定这个机器所处的状态”。如果在自动机完成读取的时候，它处于接受状态，则称NFA接受了这个字符串，否则称为它拒绝了这个字符串。

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

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

对于有状态的可数无限集合的非确定有限自动机，幂集构造给出有状态的连续统的确定自动机因为可数无限集合的幂集是连续统：。在这种情况下，为了使状态转移有意义，状态的集合必须被赋予一个拓扑。这种系统叫做拓扑自动机。1

实现有多种方式实现NFA:

转换成等价的DFA。在某些情况下这导致在自动机大小上的指数爆炸，从而辅助空间正比于在NFA中状态的数目（因为状态值存储要求给在NFA中的每个状态最多一位）。

保持机器当前可能处在的所有状态的集合数据结构。在消耗最后一个输入符号的时候，如果这些状态之一是最终状态，则机器接受这个字符串。在最坏的情况下，这要求辅助空间正比于在NFA中状态的数目；如果集合结构为每个NFA状态使用一位，则这个方式等价于前者。

创建多个复件。对于每个n路决定，NFA创建这个机器的直到{\displaystyle n-1}个复件。每个都进入单独的状态。如果在耗尽最后的输入符号的时候，至少一个NFA复件处在接受状态，则NFA就接受它。（这也要求关于NFA状态数目的线性存储，因为对所有NFA状态都可能有一个机器）。

通过NFA的转移结构明确的传播（propagate）记号（token）并在一个记号到达最终状态的时候匹配。这在NFA应当编码触发转移的事件的额外上下文的时候是有用的。（对使用这种技术来跟踪对象引用的实现可查看Tracematches）。2

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

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

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

（iii）一个正则语言的Kleene闭包是正则的。2

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所