非确定有限状态自动机

维基百科，自由的百科全书

在计算理论中，非确定有限状态自动机或非确定有限自动机(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-元组 (Q, Σ, T, q₀, F)，它构成自

状态的有限集合 Q
输入符号的有限集合 Σ
转移函数 T : Q × Σ → P(Q)
“初始”(或“开始”)状态 q₀，有着 q₀ ∈ Q
“接受”(或“最终”)状态的集合 F，有着 F ⊆ Q

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

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

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

[编辑] 性质

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

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

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

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

[编辑] NFA-ε的性质

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

$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)$ 。

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

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

对于 $P\subset Q$ 的任何子集，定义 P 的ε-闭包为

$E(P) = \bigcup\limits_{p\in P}E(\{p\})$ 。

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

类似的，如果 $q_{1}\in E(P)$ 且 $q_{2}\in E(\{q_{1}\})$ 则 $q_{2}\in E(P)$

设 x 是字母表Σ上的字符串。一个 NFA-ε M 接受字符串 x，如果存在 x 的形如 x₁x₂ ... x_n 的表示，这里的 x_i ∈ (Σ ∪{ε})，和状态序列 p₀,p₁, ..., p_n二者，这里的 p_i ∈ Q，满足下列条件:

p₀ $\in$ E({q₀})
p_i $\in$ E(T(p_i-1, x_i )) 对于 i = 1, ..., n
p_n $\in$ F。

特别注意某些字母 x_i 可以是 {ε}；它们不是选择自单独的Σ，而是来自Σ ∪{ε}。

[编辑] 实现

有多种方式实现 NFA:

转换成等价的 DFA。在某些情况下这导致在自动机大小上的指数爆炸，从而辅助空间正比于在 NFA 中状态的数目(因为状态值存储要求给在 NFA 中的每个状态最多一位)。
保持机器当前可能处在的所有状态的集合数据结构。在消耗最后一个输入符号的时候，如果这些状态之一是最终状态，则机器接受这个字符串。在最坏的情况下，这要求辅助空间正比于在 NFA 中状态的数目；如果集合结构为每个 NFA 状态使用一位，则这个方式等价于前者。
建立多个复件。对于每个 n 路决定，NFA 建立这个机器的直到 $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	ε
S₀	{}	{}	{S₁, S₃}
S₁	{S₂}	{S₁}	{}
S₂	{S₁}	{S₂}	{}
S₃	{S₃}	{S₄}	{}
S₄	{S₄}	{S₃}	{}

M 的状态图是:

M 可以被看作两个DFA的并集: 一个有状态 {S₂, S₁} 而另一个有状态 {S₃, S₄}。

M 的语言可以描述为如下正则表达式给出的正则语言:

$(1^*(01^*01^*)^*) \cup (0^*(10^*10^*)^*)$

[编辑] NFA-ε的应用

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

(i) 两个正则语言的并集是正则的。

(ii) 两个正则语言的串接是正则的。

(iii) 一个正则语言的Kleene闭包是正则的。

[编辑] 引用

^ M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp.115-125.
^ FOLDOC Free Online Dictionary of Computing, Finite State Machine

Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. (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-029880-X. (See chapter 2.)

[_note-0] M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp.115-125.

[_note-1] FOLDOC Free Online Dictionary of Computing, Finite State Machine

[1]

[2]