非确定有限状态自动机

在计算理论中，非确定有限状态自动机或非确定有限自动机（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,\Sigma ,T,q_{0},F)$ ，它构成自

状态的有限集合 $Q$
输入符号的有限集合 $\Sigma$
转移函数 $T:Q\times (\Sigma \cup \{\epsilon \})\to {\mathcal {P}}(Q)$
“初始”（或“开始”）状态 $q_{0}$ ，有着 $q_{0}\in Q$
“接受”（或“最终”）状态的集合 $F$ ，有着 $F\subset Q$

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

T:Q\times (\Sigma \cup \{\epsilon \})\to {\mathcal {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$ 沿着零或更多个 $\epsilon$ 箭头前进可到达 $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與DFA

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

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

$F_{1}=\{q\in Q_{1}|q\cap F\neq 0\}$

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-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.）

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

[2] FOLDOC Free Online Dictionary of Computing, Finite State Machine^{[永久失效連結]}

[1]

[2]