计算理论专题复习：NFA（非确定性有限自动机）核心教程与真题通关指南

本篇笔记专为快速掌握 NFA (Non-deterministic Finite Automaton) 并备战名校（如大阪大学情报工学专攻）计算理论专业课考试而设计。我们将以最直观的语言、严谨的数学定义以及实战真题，带你彻底攻克这一高频考点。

目录

1. DFA 与 NFA 的本质区别

2. NFA 的运行机制与“分身”判定规则

3. $\epsilon$-转移 (Epsilon Transition) 的引入

4. 核心概念：$\epsilon$-闭包 ($\epsilon$-closure)

5. 核心进阶：子集构造法 (Subset Construction)

6. 大阪大学真题实战演练

1. DFA 与 NFA 的本质区别

在学习非确定性有限自动机（NFA）之前，我们首先需要明确它与确定性有限自动机（DFA）的联系与区别。

1.1 核心定义对比

DFA 与 NFA 唯一的本质区别在于：同一个状态面对同一个输入，DFA 只有唯一一种选择；而 NFA 可以有零个、一个或多个选择。

我们从数学形式化定义（五元组 $M = (Q, \Sigma, \delta, q_0, F)$）中可以看得更加直观：

• DFA 的转移函数：

  $\delta: Q \times \Sigma \rightarrow Q$

  解释：输入一个当前状态和一个字符，返回唯一一个确定的下一个状态。

• NFA 的转移函数：

  $\delta: Q \times \Sigma \rightarrow \mathcal{P}(Q)$

  解释：返回的是一个状态集合（$\mathcal{P}(Q)$ 表示状态集 $Q$ 的幂集 Power Set）。 例如，如果状态集 $Q = \{q_0, q_1, q_2\}$，那么 $\delta(q_0, 0)$ 的结果可能是 $\{q_1\}$、$\{q_1, q_2\}$，甚至是空集 $\emptyset$（代表没有任何出边）。

1.2 状态转移图对比

特性	DFA (确定性)	NFA (非确定性)
同一输入多条边	❌ 不允许。若有 $q_0 \xrightarrow{0} q_1$，则不能有 $q_0 \xrightarrow{0} q_2$。	允许。可以同时存在 $q_0 \xrightarrow{0} q_1$ 和 $q_0 \xrightarrow{0} q_2$。
无对应输入的边	❌ 不允许。必须对字母表 $\Sigma$ 中的每个字符都有出边。	允许。若在 $q_0$ 遇到字符 0 且无出边，计算路径直接消失。
空串 $\epsilon$ 转移	❌ 不允许。	允许。不消耗字符即可发生状态跳转。

2. NFA 的运行机制与“分身”判定规则

2.1 “分身”与并行计算

理解 NFA 运作最直观的方法是将其想象成“分身（并行计算路径）”：

1. 初始时，机器在初始状态 $q_0$。

2. 当读入一个字符时，若存在多条可行的转移路径，自动机就会同时分裂出多个分身去探索不同的路径。

3. 如果面对某个字符没有任何转移边，该分身（路径）就会死亡并消失。

2.2 终极判定原则（⚠️ 考试核心）

“只要存在（$\exists$）至少一条路径在读完整个输入串后，停留在接受状态（Accepting State），该字符串就被接受（Accept）；只有当所有路径都死亡或未停留在接受状态时，才被拒绝（Reject）。”

⚠️ 易错警示

1. 中途经过接受状态不等于接受：自动机不会因为“中途曾经到达过接受状态”而提前结束。它必须且只能在读完最后一个字符后，检查当前存活的状态集合中是否包含接受状态。

2. 存在性 vs 唯一性：DFA 只有一条路径，而 NFA 只要“有任何一条分支能成功”即可。

2.3 经典基础练习题

📝 练习 1：单字符输入

【题目】 设有一个 NFA：

• 初始状态为 $q_0$。

• 读入字符 0 时，机器可以转移到 $q_1$，也可以转移到 $q_2$。

• 其中 $q_1$ 是接受状态，$q_2$ 不是接受状态。

• 输入字符串："0"。

问：该 NFA 最终判定为 Accept 还是 Reject？为什么？

【解析】

1. 初始状态为 $\{q_0\}$。

2. 读入字符 0 后，活跃的状态集合变为 $\{q_1, q_2\}$。

3. 此时输入串 "0" 已经全部读完。

4. 我们检查当前存活的状态集：$\{q_1, q_2\} \cap \{q_1\} = \{q_1\} \neq \emptyset$（即存活集合中包含了接受状态 $q_1$）。

5. 根据“存在即接受”的原则，最终结果为 Accept。

📝 练习 2：多字符输入与路径消失

【题目】 设有一个 NFA，其转移关系如下：

• $q_0 \xrightarrow{0} q_1$ （$q_1$ 为接受状态）

• $q_0 \xrightarrow{0} q_2$ （$q_2$ 为非接受状态）

• $q_1$ 和 $q_2$ 面对输入 0 或 1 均无任何出边。

• 输入字符串："00"。

问：该 NFA 最终判定为 Accept 还是 Reject？请写出状态集合的变化过程。

【解析】

1. 开始阶段：初始状态集合为 $\{q_0\}$。

2. 读入第一个 0：活跃状态集更新为 $\{q_1, q_2\}$。

3. 读入第二个 0：

   • 试图从 $q_1$ 出发沿 0 转移：无此转移，此路径消失。

   • 试图从 $q_2$ 出发沿 0 转移：无此转移，此路径消失。

4. 输入读完：此时活跃状态集合为空集 $\emptyset$。

5. 判定结果：由于没有任何一条路径存活，更没有任何路径停留在接受状态，因此最终结果为 Reject。

📝 练习 3：多分支综合探索

【题目】 设 NFA 的状态转移图如下：

• $q_0 \xrightarrow{0} q_1$ （$q_1$ 为接受状态）

• $q_0 \xrightarrow{0} q_2$ （$q_2$ 为非接受状态）

• $q_2 \xrightarrow{1} q_1$

输入字符串为 "01"。请判断结果是 Accept 还是 Reject，并详细写出每条可能路径的变化。

【解析】

1. 开始阶段：处于初始状态 $\{q_0\}$。

2. 读入字符 0：活跃状态集变为 $\{q_1, q_2\}$。

3. 读入字符 1：

   • 路径 A (来自 $q_1$)：从 $q_1$ 试图读取 1。由于 $q_1$ 无出边，此路径死亡。

   • 路径 B (来自 $q_2$)：从 $q_2$ 读取 1，成功转移到 $q_1$。

4. 输入读完：最终活跃状态集为 $\{q_1\}$。

5. 判定结果：由于 $q_1$ 是接受状态，最终结果为 Accept。

3. $\epsilon$-转移 (Epsilon Transition) 的引入

在大阪大学的历年真题中，带 $\epsilon$-转移的 NFA（通常写作 $\epsilon\text{-NFA}$）是绝对的高频考点。

3.1 什么是 $\epsilon$-转移？

$\epsilon$-转移（$\epsilon$-transition）指的是“不消耗任何输入字符就可以进行的状态转移”。你可以将其直观地理解为自动机内部的 “免费传送门” 或 “瞬间移动”。

Start ──> q0 ──(ε)──> q1 ──(1)──> q2 (Accept)

⚠️ 两个极为重要的概念澄清：

1. $\epsilon$ 不是字母表中的字符： 字母表 $\Sigma$ 是用户可以输入的字符集（例如 $\Sigma = \{0, 1\}$）。$\epsilon$ 表示“空串”，用户不可能在输入框里输入一个 $\epsilon$。 为了形式化定义 $\epsilon$-转移，我们会把转移函数的输入字母表扩展为：

   $\Sigma_\epsilon = \Sigma \cup \{\epsilon\}$

2. 走 $\epsilon$-转移不前进输入指针： 只有读取真实的字母表字符（如 0, 1）时，输入字符串的扫描指针才会向后移动；而走 $\epsilon$ 边时，指针保持在原位。

3.2 $\epsilon$-转移基础练习题

📝 练习 4：验证 $\epsilon$-转移运行

【题目】 考虑以下 $\epsilon\text{-NFA}$：

Start ──> q0 ──(ε)──> q1 ──(0)──> q2 (Accept)

输入字符串为："0"。 请判断最终结果是 Accept 还是 Reject，并写出转移路径。

【解析】

1. 初始位于 $q_0$。由于存在 $q_0 \xrightarrow{\epsilon} q_1$，机器可以不消耗字符直接免费移动到 $q_1$。

2. 此时输入串仍为 "0"，且输入指针仍指向字符 0。

3. 从 $q_1$ 读取真正的输入字符 0，转移到 $q_2$。

4. 输入字符全部消耗完毕，机器停在接受状态 $q_2$。

5. 最终结果：Accept。

4. 核心概念：$\epsilon$-闭包 ($\epsilon$-closure)

在处理 $\epsilon\text{-NFA}$ 时，如果不引入数学上严谨的 $\epsilon$-闭包 ($\epsilon$-closure) 概念，在做状态转换（NFA $\rightarrow$ DFA）时极易出错。

4.1 什么是 $\epsilon$-闭包？

对于 NFA 的任意状态 $q$，其 $\epsilon$-闭包（记作 $\epsilon\text{-closure}(q)$） 定义为：

从状态 $q$ 出发，仅通过 $\epsilon$-转移（可以走 0 条、1 条或多条 $\epsilon$ 边）所能到达的所有状态的集合（包含 $q$ 自身）。

如果是一个状态集合 $S$ 的 $\epsilon$-闭包，则为集合内每个状态的 $\epsilon$-闭包的并集：

$\epsilon\text{-closure}(S) = \bigcup_{s \in S} \epsilon\text{-closure}(s)$

4.2 经典练习题

📝 练习 5：计算 $\epsilon$-闭包

【题目】 已知状态转移图如下：

q0 ──(ε)──> q1 ──(ε)──> q2 ──(0)──> q3

请计算：$\epsilon\text{-closure}(q_0)$ 是什么集合？

【解析】 我们从 $q_0$ 出发，只沿着 $\epsilon$ 边进行探索：

• 走 0 条 $\epsilon$ 边：到达 $q_0$ 自身。

• 走 1 条 $\epsilon$ 边：$q_0 \xrightarrow{\epsilon} q_1$，到达 $q_1$。

• 走 2 条 $\epsilon$ 边：$q_0 \xrightarrow{\epsilon} q_1 \xrightarrow{\epsilon} q_2$，到达 $q_2$。

• 由于 $q_2 \xrightarrow{0} q_3$ 需要消耗字符 0，因此 $q_3$ 不能算入 $\epsilon$-闭包中。

所以，$\epsilon\text{-closure}(q_0) = \{q_0, q_1, q_2\}$。

4.3 💡 黄金法则：先展开 $\epsilon$-闭包，再读取输入

在含有 $\epsilon$-转移的 NFA 中，每当机器处于某个状态集合（或刚开始启动）时，第一步永远是先计算该集合的 $\epsilon\text{-closure}$，将其完全展开，然后再去读取下一个真实的输入字符。

📝 练习 6：综合 $\epsilon$-闭包的计算

【题目】 设 $\epsilon\text{-NFA}$ 结构如下：

          ┌──(1)──> q2
          │
Start ──> q0 ──(ε)──> q1 ──(0)──> q3 (Accept)

输入字符串为："0"。 请判断最终结果是 Accept 还是 Reject，并写出解题思考过程。

【解析】

1. 初始展开： 虽然初始状态是 $q_0$，但在读取任何字符前，必须先求其 $\epsilon$-闭包：

   $\epsilon\text{-closure}(q_0) = \{q_0, q_1\}$

   这意味着在读取第一个字符之前，自动机实际上已经同时处于 $q_0$ 和 $q_1$ 了。

2. 读取字符 0：

   • 从 $q_0$ 出发面对 0：无此转移。

   • 从 $q_1$ 出发面对 0：可以转移到 $q_3$。

   • 因此，转移后的状态集合为 $\{q_3\}$。

3. 计算末尾的 $\epsilon$-闭包：

   $\epsilon\text{-closure}(q_3) = \{q_3\}$

4. 判定结果：由于 $q_3$ 是接受状态，最终结果为 Accept。

5. 核心进阶：子集构造法 (Subset Construction)

这是大阪大学计算理论真题中出现频率最高、分值最重的题型：将 NFA（含 $\epsilon$-转移）转换为等价的最小 DFA。其核心算法就是“子集构造法”。

5.1 算法核心步骤

1. 确定 DFA 的初始状态 $S_0$：

   $S_0 = \epsilon\text{-closure}(q_{start})$

   (注意：一定要包含初始状态本身的 $\epsilon$-闭包)

2. 构造 DFA 的转移函数： 对于每一个已知的 DFA 状态（即 NFA 的状态子集）$U$ 和字母表中的每一个字符 $a \in \Sigma$：

   $\delta_{DFA}(U, a) = \epsilon\text{-closure}\left( \bigcup_{u \in U} \delta_{NFA}(u, a) \right)$

   直观理解：先找出 $U$ 中所有状态面对 $a$ 能到达的状态，然后对这个结果集求 $\epsilon$-闭包。

3. 迭代更新： 重复步骤 2，直到没有产生新的 DFA 状态为止。

4. 确定 DFA 的接受状态集 $F_{DFA}$： 任何一个包含了 NFA 接受状态的子集，都成为 DFA 的接受状态。

5. 处理死状态 (Dead State)： 若转移结果为空集 $\emptyset$，在 DFA 中通常画作一个“死状态”（或陷阱状态），它面对任何输入都自我循环。

5.2 子集构造法经典范例

我们用一个精致的例子来完整演示这一过程。

【例题】 已知 $\epsilon\text{-NFA}$ $M = (Q, \Sigma, \delta, q_0, F)$，其中 $Q = \{A, B, C\}$，$\Sigma = \{0, 1\}$，初始状态为 $A$，接受状态集 $F = \{C\}$。状态转移定义如下：

• $A \xrightarrow{\epsilon} B$

• $A \xrightarrow{0} A$

• $B \xrightarrow{1} C$

• $C \xrightarrow{0} C$

请将该 NFA 转换为等价的 DFA。

【详细推导步骤】

第一步：求 DFA 的初始状态

$S_0 = \epsilon\text{-closure}(A) = \{A, B\}$

(因为 $A$ 可以通过 $\epsilon$ 免费到达 $B$)

第二步：从 $S_0$ 出发，探索在输入 0 和 1 下的转移

1. 输入 0：

   • 先求转移：$\delta_{NFA}(A, 0) \cup \delta_{NFA}(B, 0) = \{A\} \cup \emptyset = \{A\}$

   • 再求闭包：$\epsilon\text{-closure}(\{A\}) = \{A, B\} = S_0$

   • 结论：$\delta_{DFA}(S_0, 0) = S_0$

2. 输入 1：

   • 先求转移：$\delta_{NFA}(A, 1) \cup \delta_{NFA}(B, 1) = \emptyset \cup \{C\} = \{C\}$

   • 再求闭包：$\epsilon\text{-closure}(\{C\}) = \{C\}$ (记作新状态 $S_1$)

   • 结论：$\delta_{DFA}(S_0, 1) = S_1$

第三步：从新状态 $S_1 = \{C\}$ 出发探索

1. 输入 0：

   • 先求转移：$\delta_{NFA}(C, 0) = \{C\}$

   • 再求闭包：$\epsilon\text{-closure}(\{C\}) = \{C\} = S_1$

   • 结论：$\delta_{DFA}(S_1, 0) = S_1$

2. 输入 1：

   • 先求转移：$\delta_{NFA}(C, 1) = \emptyset$

   • 再求闭包：$\epsilon\text{-closure}(\emptyset) = \emptyset$ (记作死状态 $S_d$)

   • 结论：$\delta_{DFA}(S_1, 1) = S_d$

第四步：补充死状态 $S_d = \emptyset$ 的转移

• $\delta_{DFA}(S_d, 0) = S_d$

• $\delta_{DFA}(S_d, 1) = S_d$

第五步：确定接受状态并画出 DFA

由于原 NFA 的接受状态是 $C$，任何包含 $C$ 的子集都是 DFA 的接受状态。

• 因此，DFA 的接受状态为：$S_1 = \{C\}$。

DFA 状态转移表：

DFA 状态	NFA 子集构成	输入 0	输入 1	是否为接受状态
$S_0$ (Start)	$\{A, B\}$	$S_0$	$S_1$	❌
$S_1$ (Accept)	$\{C\}$	$S_1$	$S_d$
$S_d$	$\emptyset$	$S_d$	$S_d$	❌

6. 大阪大学真题实战演练

为了检验和巩固学习成果，本节提供了一道高度还原大阪大学情报工学专攻《计算理论》过去问风格的综合大题，并附带了严谨的步骤解析和 DFA 最小化扩展知识。

📝 综合真题突破：$\epsilon\text{-NFA}$ 分析、转换与最小化

【题目】 设字母表 $\Sigma = \{a, b\}$，考虑以下给定的 $\epsilon\text{-NFA}$ $M = (Q, \Sigma, \delta, q_0, F)$：

          ┌───────────────(a)──────────────┐
          │                                v
Start ──> q0 ──(ε)──> q1 ──(b)──> q2 ──(ε)──> q3 (Accept)

(注意：图中 $q_0 \xrightarrow{a} q_3$ 是一条直接的 $a$ 弧；$q_1 \xrightarrow{b} q_2$ 是 $b$ 弧；$q_0 \xrightarrow{\epsilon} q_1$ 和 $q_2 \xrightarrow{\epsilon} q_3$ 是空串边)

1. [语言识别] 写出该 NFA 所识别的语言 $L(M)$ 的正则表达式（Regular Expression）。

2. [子集构造] 使用子集构造法，将该 $\epsilon\text{-NFA}$ 转换为等价的 DFA（要求写出详细的子集推导过程与状态转移表）。

3. [DFA 最小化] 对转换得到的 DFA 进行最小化，并画出最小化后的 DFA 状态转移图。

【第一问解析：语言识别】

我们分析从 $q_0$ 到接受状态 $q_3$ 的所有可行路径：

• 路径 1：$q_0 \xrightarrow{a} q_3$。消耗字符：a。

• 路径 2：$q_0 \xrightarrow{\epsilon} q_1 \xrightarrow{b} q_2 \xrightarrow{\epsilon} q_3$。消耗字符：b（由于 $\epsilon$ 不消耗字符，整条路径仅消耗了一个 b）。

因此，该自动机能够且仅能接受字符串 "a" 和 "b"。

• 对应的正则表达式为：

  $a + b \quad (\text{或 } a|b)$

【第二问解析：子集构造法转换】

Step 1: 确定 DFA 的初始状态 $A$

对原 NFA 的初始状态 $q_0$ 求 $\epsilon$-闭包：

$A = \epsilon\text{-closure}(q_0) = \{q_0, q_1\}$

(通过 $q_0 \xrightarrow{\epsilon} q_1$)

Step 2: 计算状态 $A = \{q_0, q_1\}$ 的转移

• 输入 a：

  • $\delta_{NFA}(q_0, a) \cup \delta_{NFA}(q_1, a) = \{q_3\} \cup \emptyset = \{q_3\}$

  • 求闭包：$\epsilon\text{-closure}(\{q_3\}) = \{q_3\}$ (记作新状态 $B$)

  • 结论：$\delta_{DFA}(A, a) = B$

• 输入 b：

  • $\delta_{NFA}(q_0, b) \cup \delta_{NFA}(q_1, b) = \emptyset \cup \{q_2\} = \{q_2\}$

  • 求闭包：$\epsilon\text{-closure}(\{q_2\}) = \{q_2, q_3\}$ (由于存在 $q_2 \xrightarrow{\epsilon} q_3$，记作新状态 $C$)

  • 结论：$\delta_{DFA}(A, b) = C$

Step 3: 计算状态 $B = \{q_3\}$ 的转移

由于 $q_3$ 在原 NFA 中无任何出边：

• 输入 a：$\delta_{DFA}(B, a) = \emptyset$ (记作死状态 $D$)

• 输入 b：$\delta_{DFA}(B, b) = \emptyset = D$

Step 4: 计算状态 $C = \{q_2, q_3\}$ 的转移

$q_2$ 和 $q_3$ 在原 NFA 中均无任何对字母表 $\{a, b\}$ 的有向转移：

• 输入 a：$\delta_{DFA}(C, a) = \emptyset = D$

• 输入 b：$\delta_{DFA}(C, b) = \emptyset = D$

Step 5: 计算死状态 $D = \emptyset$ 的转移

• $\delta_{DFA}(D, a) = D$

• $\delta_{DFA}(D, b) = D$

DFA 状态转移表总结：

DFA 状态	NFA 子集	输入 a	输入 b	是否为接受状态
$A$ (Start)	$\{q_0, q_1\}$	$B$	$C$	❌
$B$ (Accept)	$\{q_3\}$	$D$	$D$
$C$ (Accept)	$\{q_2, q_3\}$	$D$	$D$
$D$	$\emptyset$	$D$	$D$	❌

(注：由于 $B$ 和 $C$ 均包含原 NFA 的接受状态 $q_3$，故它们都是 DFA 的接受状态)

【第三问解析：DFA 最小化】

为了得到最简 DFA，我们使用经典的等价类划分法（Myhill-Nerode 状态划分定理）。

Step 1: 初始划分

将状态集分为非接受状态组 $P_{non}$ 和接受状态组 $P_{acc}$：

$P_0 = \{ \{A, D\}, \{B, C\} \}$

Step 2: 考察非接受状态组 $\{A, D\}$

• 对于状态 $A$：

  • $\delta_{DFA}(A, a) = B \in \{B, C\}$

  • $\delta_{DFA}(A, b) = C \in \{B, C\}$

• 对于状态 $D$：

  • $\delta_{DFA}(D, a) = D \in \{A, D\}$

  • $\delta_{DFA}(D, b) = D \in \{A, D\}$

由于 $A$ 和 $D$ 面对相同输入转移到了不同的等价组，因此 $\{A, D\}$ 必须拆开。 目前划分更新为：

$P_1 = \{ \{A\}, \{D\}, \{B, C\} \}$

Step 3: 考察接受状态组 $\{B, C\}$

• 对于状态 $B$：

  • $\delta_{DFA}(B, a) = D \in \{D\}$

  • $\delta_{DFA}(B, b) = D \in \{D\}$

• 对于状态 $C$：

  • $\delta_{DFA}(C, a) = D \in \{D\}$

  • $\delta_{DFA}(C, b) = D \in \{D\}$

由于 $B$ 和 $C$ 面对所有输入的行为完全一致（均转移至死状态 $D$），因此 $B$ 和 $C$ 是等价状态，可以合并。我们将合并后的状态命名为 $BC$。

最终等价状态划分结果：

$P_{final} = \{ \{A\}, \{BC\}, \{D\} \}$

最小化后的 DFA 状态转移图表描述：

• 状态集：初始状态 $A$，接受状态 $BC$，死状态 $D$。

• 转移关系：

  • $A \xrightarrow{a} BC$

  • $A \xrightarrow{b} BC$

  • $BC \xrightarrow{a, b} D$

  • $D \xrightarrow{a, b} D$

最小化 DFA 状态转移图：

           ┌─────(a, b)─────┐
           v                │
(Start) ──> A ──(a,b)──> [BC] (Accept) ──(a,b)──> D ↺ (a,b)