形式陈述

非确定性有限自动机是五元组 $N=(Q,\Sigma,\delta,q_0,F)$$N=(Q,\mathrm{\Sigma },\delta ,q_0,F)$，其中 $Q$$Q$ 有限，且

$$ \delta:Q\times\Sigma\to\mathcal P(Q). $$$$\delta :Q\times \mathrm{\Sigma }\to \mathcal{P}(Q).$$

扩展转移从状态集开始定义：

$$ \widehat\delta(S,\varepsilon)=S, \qquad \widehat\delta(S,wa)=\bigcup_{q\in\widehat\delta(S,w)}\delta(q,a). $$$$\hat{\delta }(S,\epsilon )=S,\hat{\delta }(S,wa)=\bigcup _{q\in \hat{\delta }(S,w)}\delta (q,a).$$

字符串 $w$$w$ 被接受，当且仅当

$$ \widehat\delta(\{q_0\},w)\cap F\ne\varnothing, $$$$\hat{\delta }(\{q_0\},w)\cap F\ne \varnothing ,$$

等价地，存在一条读取完整 $w$$w$ 并终止于接受状态的运行路径。本条 NFA 每步必须读取一个输入符号；允许不消耗输入转移的扩展单列为 $\varepsilon$$\epsilon$-NFA。

直觉

NFA 同时保留所有可能运行分支；接受是存在量词，只需一条分支成功。所谓“猜测”是数学描述，不表示机器依赖随机选择，也不要求实际并行硬件。

例子与边界

识别“倒数第二个字符为 $1$$1$”的 NFA 可以在读到某个 $1$$1$ 时分出一条分支，猜测它是目标位置，再检查后面恰有一个字符。若所有分支都失败则拒绝；分支数多少不改变存在分支语义。NFA 不含 $\varepsilon$$\epsilon$ 转移并不损失表达能力，因为任意 $\varepsilon$$\epsilon$-NFA 都可消去空转移。非确定性有限自动机也不等于概率自动机：没有为分支赋概率，更不按接受概率阈值判定。

推论与应用

NFA 往往比 DFA 更简洁。读完一个前缀后的全部可能状态形成一个集合，这直接导出子集构造和 DFA–NFA 等价定理；正则表达式实现中则常先构造更便于组合的 $\varepsilon$$\epsilon$-NFA。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，§2.3。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§1.2。