• ChatGPT - NFA到DFA子集构造法

NFA到DFA子集构造法 (Subset Construction)

🎯 大阪大学情報工学・計算理论考前冲刺必胜笔记

在大阪大学计算理论近年的出题规律中，NFA 到 DFA 的子集构造法 (Subset Construction) 几乎是必考技能（如 2012、2016、2026 年真题）。本笔记旨在帮助你理清所有数学符号、纠正手写常犯错误、补充知识盲区，并实现“在考场上 5 分钟内无错完成转换”的目标。

📌 目录

1. 认知重构：为什么需要子集构造法？

2. 数学符号与直观理解（扫除认知死角）

3. 核心计算规则：状态转移与接受状态判断

4. 高级拓展：处理 $\epsilon$-transition（补充盲区例题）

5. 考试通用算法：BFS 状态展开表法（防漏技巧）

6. 双重实战演练（含纠错与阪大 2026 真题标准答案）

1. 认知重构：为什么需要子集构造法？

在自动机理论中，DFA（确定有限自动机）和 NFA（非确定有限自动机）在表达能力（Language Recognition）上是完全等价的。但是它们的运行机制有着本质的区别：

• DFA (Deterministic Finite Automaton)：对于当前状态，读入一个输入符号，有且仅有唯一一个去向状态。

• NFA (Non-deterministic Finite Automaton)：对于当前状态，读入一个输入符号，可以同时去多个状态（甚至 $0$ 个状态），并且支持不消耗字符的空移（$\epsilon$-transition）。

【NFA 的不确定性示例】
         0
   q0 -------> q1
    \    0
     \-------> q2

当 NFA 读入 0 时，可能在 $q_1$，也可能在 $q_2$。在物理现实中，我们无法让机器“同时存在于两个平行宇宙”。 因此，我们换一个视角来看 DFA：

DFA 的当前状态，本质上就是“当前 NFA 机器可能所在的所有状态的集合”。

这就是 Subset (子集) 构造法 的由来。我们要构造一个全新的 DFA，它的每一个“状态”都是原 NFA 状态集合的一个“子集”。

2. 数学符号与直观理解（扫除认知死角）

在正式做题前，必须彻底搞懂符号的数学定义，这是写出完美卷面步骤的基础。

2.1 什么是 $\delta$ (Delta)？

在自动机中，$\delta$ 表示 状态转移函数 (Transition Function)。

• 对于 DFA：$\delta(q_1, a) = q_2$

  • 人话：当前在状态 $q_1$，读入字符 $a$，去向唯一的状态 $q_2$。

• 对于 NFA：$\delta(q_1, a) = \{q_2, q_3\}$

  • 人话：当前在状态 $q_1$，读入字符 $a$，可能去向的集合是 $\{q_2, q_3\}$。

  • 数学形式统一：即使只去一个状态，也必须写成集合形式，如 $\delta(q_0, 0) = \{q_1\}$。

2.2 状态 $q_1$ 与 状态集合 $\{q_1\}$ 的本质区别

• $q_1$：原始 NFA 中的一个单个物理节点（元素）。

• $\{q_1\}$：子集构造法中，由我们人为创建的 DFA 的一个新节点（单元素集合）。

• $\{q_0, q_2\}$：DFA 中的一个新节点。在 DFA 中，它是一个整体，代表“此时 NFA 机器可能在 $q_0$ 或 $q_2$”，千万不要把它拆开看作两个步骤。

3. 核心计算规则：状态转移与接受状态判断

3.1 集合的转移计算

如果新 DFA 当前处于状态 $R$（$R$ 是 NFA 状态的集合），读入符号 $a$，我们要如何计算它会转移到哪个新状态？

$\delta_D(R, a) = \bigcup_{q \in R} \delta_N(q, a)$

🔑 考试口诀：分别询问集合中的每个成员去哪里，然后把所有的答案取并集 (Union)，最后去重。

💡 极简计算练习

已知某 NFA 满足：

• $\delta_N(q_0, 0) = \{q_0, q_1\}$

• $\delta_N(q_1, 0) = \emptyset$

求：$\delta_D(\{q_0, q_1\}, 0)$？ 【解析】

$\delta_D(\{q_0, q_1\}, 0) = \delta_N(q_0, 0) \cup \delta_N(q_1, 0) = \{q_0, q_1\} \cup \emptyset = \{q_0, q_1\}$

3.2 Accept State (接受状态) 的判定

这是阪大考试中最容易失分的技术细节。

• 规则：只要 DFA 的状态集合中，包含至少一个原 NFA 的接受状态（Accept State），那么这个 DFA 状态就是接受状态。

• 数学定义：若原 NFA 的接受状态集为 $F_N$，则 DFA 的接受状态集为：

$F_D = \{ R \subseteq Q \mid R \cap F_N \neq \emptyset \}$

💡 示例直观判定

假设原 NFA 的接受状态集 $F_N = \{q_2\}$。判定以下 DFA 状态是否为接受状态：

• $\{q_0, q_1\}$ $\rightarrow$ ❌ Reject (不含 $q_2$)

• $\{q_2\}$ $\rightarrow$ Accept (包含 $q_2$)

• $\{q_0, q_2\}$ $\rightarrow$ Accept (包含 $q_2$)

• $\{q_0, q_1, q_2\}$ $\rightarrow$ Accept (包含 $q_2$)

4. 高级拓展：处理 $\epsilon$-transition（补充盲区例题）

若 NFA 中存在 $\epsilon$-transition（即空移，无需读入字符即可转移），则必须在构造时计算 $\epsilon$-闭包 ($\epsilon$-closure)。

4.1 什么是 $\epsilon$-closure？

• 定义：$\epsilon\text{-closure}(q)$ 是指从状态 $q$ 出发，仅通过 $\epsilon$ 转移（$0$ 条或多条）所能到达的所有状态的集合（自身默认包含在内）。

4.2 计算公式修正

1. DFA 初始状态：不再是单独的 $\{q_0\}$，而是：

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

2. 转移后做闭包：在对每个集合成员求符号 $a$ 的转移后，必须对结果集合里的每一个状态再求一次 $\epsilon\text{-closure}$：

   $\delta_D(R, a) = \epsilon\text{-closure}\left( \bigcup_{q \in R} \delta_N(q, a) \right)$

📝 补充经典例题：含 $\epsilon$ 转移的 NFA 到 DFA 转换

【题目】 给定如下含 $\epsilon$ 转移的 NFA：

• 状态集：$\{q_0, q_1, q_2\}$，初始状态 $q_0$，接受状态集 $F = \{q_2\}$。

• 转移关系：

  • $\delta(q_0, a) = \{q_0\}$, $\delta(q_0, \epsilon) = \{q_1\}$

  • $\delta(q_1, b) = \{q_2\}$

  • $\delta(q_2, a) = \{q_2\}$

【求解步骤】

第一步：计算所有状态的 $\epsilon$-closure

• $\epsilon\text{-closure}(q_0) = \{q_0, q_1\}$ （通过 $\epsilon$ 可以由 $q_0$ 走到 $q_1$）

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

• $\epsilon\text{-closure}(q_2) = \{q_2\}$

第二步：求 DFA 的初始状态

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

第三步：迭代展开状态转移表

1. 对于状态 $\{q_0, q_1\}$：

   • 输入 $a$：

     $\delta_N(q_0, a) \cup \delta_N(q_1, a) = \{q_0\} \cup \emptyset = \{q_0\}$

     求闭包：$\epsilon\text{-closure}(\{q_0\}) = \{q_0, q_1\}$。

   • 输入 $b$：

     $\delta_N(q_0, b) \cup \delta_N(q_1, b) = \emptyset \cup \{q_2\} = \{q_2\}$

     求闭包：$\epsilon\text{-closure}(\{q_2\}) = \{q_2\}$。

2. 对于新状态 $\{q_2\}$：

   • 输入 $a$：

     $\delta_N(q_2, a) = \{q_2\}$

     求闭包：$\epsilon\text{-closure}(\{q_2\}) = \{q_2\}$。

   • 输入 $b$：

     $\delta_N(q_2, b) = \emptyset \rightarrow \emptyset$

【所得 DFA 转移表】

DFA 状态	输入 $a$	输入 $b$	是否 Accept
$\{q_0, q_1\}$ (Start)	$\{q_0, q_1\}$	$\{q_2\}$	❌ Reject
$\{q_2\}$ (Accept)	$\{q_2\}$	$\emptyset$	Accept (含 $q_2$)

5. 考试通用算法：BFS 状态展开表法（防漏技巧）

为了避免在紧张的考场中漏算、重复计算或写错状态，建议采用 队列 + 发现状态表 的 BFS 机械化计算流程。

【BFS 计算流程图】
 确定初始状态 S0 (求闭包) 
       │
       ▼
 放入队列 Q 并记入“已发现状态表”
       │
 ┌────►│ (队列 Q 非空？)
 │     ▼
 │   出队一个状态 R
 │     │
 │     ▼
 │   分别计算在每个输入字符 a 处的转移：R_new = δ_D(R, a)
 │     │
 │     ├─► 若 R_new 是一个全新状态：加入队列 Q，记入“已发现状态表”
 │     └─► 若 R_new 是已存在状态：不作处理
 │     │
 └─────┴───────────────────────────────────── 当队列为空时，算法停止

6. 双重实战演练（含纠错与标准答案）

📝 实战一：常规自测题（深刻纠错）

【题目描述】 给定 NFA（Alphabet $\Sigma = \{0, 1\}$，Start = $q_0$，Accept = $\{q_2\}$，无 $\epsilon$ 转移）：

NFA 状态	输入 $0$	输入 $1$
$q_0$	$\{q_0, q_1\}$	$\{q_0\}$
$q_1$	$\{q_2\}$	$\{q_2\}$
$q_2$	$\emptyset$	$\{q_2\}$

🚨 典型错误剖析（手写笔记纠错）

在新接触子集构造法时，容易直接把 NFA 的状态重新组合成 DFA。例如，手写笔记曾将 DFA 的状态写成了 $\{q_0\}, \{q_1\}, \{q_2\}$。

• 为什么错？

  • DFA 的状态本身就是集合（例如 $\{q_0, q_1\}$）。在转移过程中，这些集合作为一个整体的节点存在。不能直接拆成 $q_0, q_1, q_2$ 各自独立的转移。

✍️ 完美推导过程

1. 初始状态：$A = \{q_0\}$

2. 处理 $A = \{q_0\}$：

   • $\delta_D(\{q_0\}, 0) = \{q_0, q_1\}$ （发现新状态 $B = \{q_0, q_1\}$）

   • $\delta_D(\{q_0\}, 1) = \{q_0\}$ （指向 $A$）

3. 处理 $B = \{q_0, q_1\}$：

   • $\delta_D(\{q_0, q_1\}, 0) = \delta_N(q_0, 0) \cup \delta_N(q_1, 0) = \{q_0, q_1\} \cup \{q_2\} = \{q_0, q_1, q_2\}$ （发现新状态 $C = \{q_0, q_1, q_2\}$）

   • $\delta_D(\{q_0, q_1\}, 1) = \delta_N(q_0, 1) \cup \delta_N(q_1, 1) = \{q_0\} \cup \{q_2\} = \{q_0, q_2\}$ （发现新状态 $D = \{q_0, q_2\}$）

4. 处理 $C = \{q_0, q_1, q_2\}$：

   • $\delta_D(\{q_0, q_1, q_2\}, 0) = \{q_0, q_1\} \cup \{q_2\} \cup \emptyset = \{q_0, q_1, q_2\}$ （指向 $C$）

   • $\delta_D(\{q_0, q_1, q_2\}, 1) = \{q_0\} \cup \{q_2\} \cup \{q_2\} = \{q_0, q_2\}$ （指向 $D$）

5. 处理 $D = \{q_0, q_2\}$：

   • $\delta_D(\{q_0, q_2\}, 0) = \{q_0, q_1\} \cup \emptyset = \{q_0, q_1\}$ （指向 $B$）

   • $\delta_D(\{q_0, q_2\}, 1) = \{q_0\} \cup \{q_2\} = \{q_0, q_2\}$ （指向 $D$）

📊 最终答案（DFA 转移表）

DFA 状态	输入 $0$	输入 $1$	是否 Accept
$\{q_0\}$	$\{q_0, q_1\}$	$\{q_0\}$	❌
$\{q_0, q_1\}$	$\{q_0, q_1, q_2\}$	$\{q_0, q_2\}$	❌
$\{q_0, q_2\}$	$\{q_0, q_1\}$	$\{q_0, q_2\}$	(含 $q_2$)
$\{q_0, q_1, q_2\}$	$\{q_0, q_1, q_2\}$	$\{q_0, q_2\}$	(含 $q_2$)

📝 实战二：2026年大阪大学计算理论真题（终极演练）

【真题要求】 已知 NFA $N_2$ 如下图所示：

• 状态集：$\{s_0, s_1, s_2\}$，初始状态 $s_0$，接受状态集 $F = \{s_2\}$。

• 转移关系同上。

• 任务：构造与之等价、且状态数最少的 DFA，并写出状态对应关系。

【原 NFA 结构图】
      ┌─── 0 ───┐
      ▼         │
 ──► (s0) ──0──► (s1) ──0,1──► ((s2)) ──1──┐
      │ ▲                         ▲        │
      │ └─── 1 ───────────────────┼────────┘
      └────────────── 1 ──────────┘

🚨 手写草稿致命错误纠正

你在草稿中写出：

DFA 一共有 3 个状态：$\{s_0\}$, $\{s_0, s_1\}$, $\{s_0, s_1, s_2\}$。

• 为什么漏掉了 $\{s_0, s_2\}$？

  • 你在计算 $\delta_D(\{s_0, s_1\}, 1)$ 时出了错。

  • 根据规则：

    $\delta_D(\{s_0, s_1\}, 1) = \delta_N(s_0, 1) \cup \delta_N(s_1, 1) = \{s_0\} \cup \{s_2\} = \{s_0, s_2\}$

  • 由于 $\{s_0, s_2\}$ 属于之前从未出现的全新集合，必须将其加入可达状态表中，并对其继续展开转移计算。

✍️ 完美答题推导步骤

第 1 步：利用子集构造法展开转移

序号	标识	DFA 状态	输入 $0$	输入 $1$	是否为 Accept State
1	$A$	$\{s_0\}$	$\{s_0, s_1\}$	$\{s_0\}$	❌ Reject
2	$B$	$\{s_0, s_1\}$	$\{s_0, s_1, s_2\}$	$\{s_0, s_2\}$	❌ Reject
3	$C$	$\{s_0, s_2\}$	$\{s_0, s_1\}$	$\{s_0, s_2\}$	Accept (含 $s_2$)
4	$D$	$\{s_0, s_1, s_2\}$	$\{s_0, s_1, s_2\}$	$\{s_0, s_2\}$	Accept (含 $s_2$)

第 2 步：状态数最少化 (Minimization) 的逻辑证明 考题中明确要求“状态数最少”。我们需要验证以上 4 个状态是否可以进一步合并。

我们将 DFA 状态划分为非接受状态集 $P_1 = \{A, B\}$ 与接受状态集 $P_2 = \{C, D\}$。

1. 测试 $P_1 = \{A, B\}$ 是否能合并：

   • 对于状态 $A = \{s_0\}$：

     • 输入 0 转移到 $\{s_0, s_1\} = B \in P_1$

   • 对于状态 $B = \{s_0, s_1\}$：

     • 输入 0 转移到 $\{s_0, s_1, s_2\} = D \in P_2$

   • 结论：因为 $A$ 和 $B$ 在输入 0 时转移到了不同的划分集合（一个去 $P_1$，一个去 $P_2$），所以它们不等价，不可合并。

2. 测试 $P_2 = \{C, D\}$ 是否能合并：

   • 对于状态 $C = \{s_0, s_2\}$：

     • 输入 0 转移到 $\{s_0, s_1\} = B \in P_1$

   • 对于状态 $D = \{s_0, s_1, s_2\}$：

     • 输入 0 转移到 $\{s_0, s_1, s_2\} = D \in P_2$

   • 结论：因为 $C$ 和 $D$ 在输入 0 时转移到了不同的划分集合（一个去 $P_1$，一个去 $P_2$），所以它们也不等价，不可合并。

因此，该由 4 个状态构成的 DFA 已经是最简形式。

第 3 步：给出的最终对应关系（满分答卷样式）

等价 DFA 共有 4 个状态，定义为 $\{A, B, C, D\}$，状态转移及对应关系如下：

• 状态 $A$（初始状态）：对应原 NFA 状态集合 $\{s_0\}$。

• 状态 $B$：对应原 NFA 状态集合 $\{s_0, s_1\}$。

• 状态 $C$（接受状态）：对应原 NFA 状态集合 $\{s_0, s_2\}$。

• 状态 $D$（接受状态）：对应原 NFA 状态集合 $\{s_0, s_1, s_2\}$。

【最简等价 DFA 状态图】
         0               1
 ──► (A) ───► (B) ─────────────► ((C)) ◄┐
      ▲        │                  │ │   │ 1
    1 │        │ 0                │ └───┘
      └── (A) ◄┴─────► ((D)) ────┘
                         ▲   │
                         └───┘ 0

7. 阪大高分秒杀口诀与防漏技巧

为了保证考试万无一失，请在演练和考场上牢记以下黄金规则：

1. 第一步算闭包：一拿到题目，先看有没有 $\epsilon$ 转移。如果有，初始状态必须先求闭包。

2. 建表防漏：在草稿纸上准备一个“已发现状态表”，算完一个打一个勾。

3. 不要脑补未达状态：理论状态数最多有 $2^n$ 个，但只列出从初始状态可达 (Reachable) 的集合，多余的状态千万不要画，浪费时间且容易扣分。

4. 死状态 (Dead State) 处理：如果题目要求“所有输入都有定义”（全定义 DFA），而某个状态在输入某个字符时没有任何转移（即返回 $\emptyset$），则必须显式引入一个死状态 $\{\emptyset\}$，使其所有转移指向自身。