Lesson 59: NFA→DFA 子集构造
练习任务
难度：中
实现 NFA（非确定有限自动机）的三个核心算法，完成从 NFA 到 DFA 的完整转换流程。你需要完成：
e_closure()— ε-闭包计算：给定状态集（位掩码），返回所有经ε转移可达的状态NFA_simulate()— NFA 模拟：给定输入串，逐步跟踪状态集变化，判断是否被 NFA 接受subset_construct()— 子集构造算法：将 NFA 转化为等价的 DFA，打印 DFA 转换表
固定 NFA 识别语言 a*b | ab*（零个或多个 a 后接一个 b，或，或者一个 a 后接零个或多个 b）。测试输入串 "aab"（应接受）和 "aba"（应拒绝）。
提示：NFA 运行时不是处于"某一个"状态，而是"一组可能的状态"。子集构造本质上是将所有"运行时可能遇到的状态集"预先枚举出来。每步先做 symbol 转移（消耗一个字符），再做ε-闭包（"免费"移动），顺序不能颠倒。
核心知识点
- 有限自动机五要素 — M = (Q, Σ, δ, q₀, F)：状态集、字母表、转移函数、初态、接受态
- DFA vs NFA 的本质区别 — 确定性（每状态每符号唯一后继）vs 非确定性（多后继 + ε转移）
- ε-闭包的不动点迭代 — do-while 反复扫描直到没有新状态加入，不是一次扫描
- NFA 模拟 = 状态集演算 — 每读入一个符号，计算新的可能状态集，最后检查是否包含接受态
- 子集构造 = 幂集的可达部分 — DFA 的每个状态对应 NFA 状态集的一个子集，最多 2ⁿ 个但通常远少于此
- 位掩码状态集编码 — int 的低位每位代表一个状态，位运算替代集合操作，效率极高
- DFA 最小化的 Hopcroft 算法概述 — 等价状态合并的思想，与 Myhill-Nerode 定理的关系
代码框架
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_STATES 4
#define EPSILON -1
#define NO_TARGET -2
/* 符号索引: 0 = 'a', 1 = 'b' */
int char_to_idx(char c) { return c - 'a'; }
/*
* ε转移表: EPSILON_TRANS[state] = {target, target, ..., NO_TARGET}
* 例如: EPSILON_TRANS[0] = {1, 2, NO_TARGET} 表示 0--ε-->1, 0--ε-->2
*/
int EPSILON_TRANS[MAX_STATES][MAX_STATES] = {
{1, 2, NO_TARGET}, // 0: ε→1, ε→2
{NO_TARGET}, // 1: 无ε转移
{NO_TARGET}, // 2: 无ε转移
{NO_TARGET} // 3: 无ε转移
};
/*
* 符号转移表: NFA_TRANS[state][symbol_idx][targets..., NO_TARGET]
* 例如: NFA_TRANS[1][0] = {1, NO_TARGET} 表示 1--a-->1
*/
int NFA_TRANS[MAX_STATES][2][MAX_STATES] = {
/* state 0: a→无, b→无 */
{{NO_TARGET}, {NO_TARGET}},
/* state 1: a→{1}, b→{3} */
{{1, NO_TARGET}, {3, NO_TARGET}},
/* state 2: a→{3}, b→无 */
{{3, NO_TARGET}, {NO_TARGET}},
/* state 3: a→无, b→{3} */
{{NO_TARGET}, {3, NO_TARGET}}
};
/*
* e_closure(states):
* 计算状态集 states（位掩码）的ε-闭包
* 反复遍历 STATES 中的每个状态，将其ε目标加入 STATES
* 直到不动点（没有新状态加入）
*/
int e_closure(int states) {
// ① 用 do-while 反复扫描，直到不变
// changed标记本轮是否有新状态加入
// 对 STATES 中每个状态 s:
// 遍历 EPSILON_TRANS[s][j]，将目标状态 t 加入 STATES
// 如果有新状态，changed = true
// 直到 !changed
return states; // 返回闭包后的位掩码
}
/*
* NFA_simulate(input):
* 对输入串 input 执行 NFA 模拟
* 每步: symbol转移 → e_closure，打印当前状态集
* 最后判断是否接受（状态集中包含状态3）
*/
bool NFA_simulate(const char *input) {
// ② 初始: current = e_closure(1 << 0) // {0}的ε闭包
//
// ③ 遍历每个字符 ch:
// next = 0
// 对 current 中每个状态 s:
// 遍历 NFA_TRANS[s][char_to_idx(ch)] 每个目标 t:
// next |= (1 << t)
// current = e_closure(next)
//
// 打印当前状态集（位掩码和状态列表）
return false;
}
/*
* subset_construct():
* 子集构造算法，将 NFA 转化为等价的 DFA
* 从 DFA 初态 = e_closure({0}) 开始，BFS 式枚举所有可达子集
* 打印最终 DFA 转换表
*/
void subset_construct() {
// ④ D0 = e_closure(1 << 0)
//
// ⑤ 用数组/队列存储已发现的 DFA 状态子集
// BFS: 取出一个未处理的子集 S
// 判断 S 是否为接受态(S & (1<<3) != 0)
//
// 对每个符号 a, b:
// T = 0
// 对 S 中每个状态 s:
// 遍历 NFA_TRANS[s][sym] 的每个目标 t:
// T |= (1 << t)
// T = e_closure(T)
//
// 如果 T != 0 且 T 是新的子集 → 加入队列
//
// ⑥ 打印转换表
}
int main(void) {
/* 演示 e_closure */
printf("e-closure({0}) = ");
int c0 = e_closure(1 << 0);
for (int s = 0; s < MAX_STATES; s++)
if (c0 & (1 << s)) printf("%d ", s);
printf("\n\n");
/* 演示 NFA 模拟 */
printf("=== NFA simulate 'aab' ===\n");
bool acc = NFA_simulate("aab");
printf("Result: %s\n\n", acc ? "ACCEPT" : "REJECT");
printf("=== NFA simulate 'aba' ===\n");
acc = NFA_simulate("aba");
printf("Result: %s\n\n", acc ? "ACCEPT" : "REJECT");
/* 演示子集构造 */
printf("=== Subset Construction ===\n");
subset_construct();
return 0;
}阅读骨架后，尝试自己填充 // ① 到 // ⑥ 标记的部分。核心挑战：ε-闭包为什么需要 do-while 而非一次扫描？NFA 模拟中为什么要先 symbol 转移再 ε-闭包？子集构造如何用 BFS 枚举所有可达的状态子集？
TIP
先不要往下翻看参考解答。用位掩码在纸上追踪 NFA 模拟 "aab" 的全过程——从 {0,1,2}（二进制 0111）开始，每步计算下一个状态集。
深度讲解
1. 有限自动机基础——DFA 与 NFA
1.1 五要素定义
有限自动机（Finite Automaton）是计算理论中最基础的数学模型，用于描述和识别正则语言。一个 FA 由五个要素定义：
M = (Q, Σ, δ, q₀, F)
Q : 有限状态集 → 本题: Q = {0, 1, 2, 3}
Σ : 有限输入字母表 → 本题: Σ = {a, b}
δ : 转移函数 → 见转移表
q₀ : 初态 → 本题: q₀ = 0
F : 接受态集 → 本题: F = {3}**本题 NFA 的完整状态转移图如下。语言 a*b | ab* 的含义：零个或多个 a 后接恰好一个 b，或者恰好一个 a 后接零个或多个 b。
┌──────────┐
│ a │
└──→ 1 ───┘ (a* 自环)
↗ ε │
/ │ b
┌─────/ ↓
│ 0 3 ← 接受态
└─────\ ↑
\ │ b
↘ ε a │
└──→ 2 ──┘ (a后进入3)
│
└── b ──→ 3 (b* 自环)1.2 DFA vs NFA：确定性 vs 非确定性
| 维度 | DFA | NFA |
|---|---|---|
| 转移确定性 | 每个状态对每个符号唯一后继 | 可有多条转移（包括 0 条） |
| ε转移 | 不允许 | 允许（空串转移） |
| 状态数 | 可能很多（最坏 2ⁿ） | 通常较少 |
| 模拟复杂度 | O(n) — 每步只需查一个状态 | O(n· |
| 能否判定接受 | 简单：读完串看当前状态 | 需维护状态集，读完看是否包含接受态 |
| 表达能力 | 正则语言 | 等价！（正则语言） |
核心定理定理（Rabin-Scott, 1959）：对任意 NFA，存在等价的 DFA 识别相同语言。子集构造算法就是证明这个定理的构造性方法。
2. ε-闭包——不动点迭代算法
2.1 定义与必要性
ε-closure(S) = 从集合 S 中任意状态出发，仅经过ε转移（零步或多步）能到达的所有状态的集合。
为什么需要ε-闭包？ 因为 NFA 在任何时刻都可以"免费"地沿ε转移移移移动，不需要消耗任何输入符号。NFA 在某时刻的"真实"可能状态集，必须包含所有ε可达的状态。
2.2 不动点迭代实现
/* ε-闭包：不动点迭代 */
int e_closure(int states) {
int closure = states;
int changed;
do {
changed = 0;
for (int s = 0; s < MAX_STATES; s++) {
if (!(closure & (1 << s))) continue; // s不在closure中
for (int j = 0; EPSILON_TRANS[s][j] != NO_TARGET; j++) {
int t = EPSILON_TRANS[s][j];
if (!(closure & (1 << t))) { // t是新状态
closure |= (1 << t);
changed = 1;
}
}
}
} while (changed);
return closure;
}为什么需要 do-while 而不是一次扫描？ 考虑ε链 0→1→2：第一次扫描拿到直接ε目标 {1}，但 1 可能又有ε转移。do-while 确保沿着任意长度的ε链追踪到底。
e-closure({0}) 的计算过程:
──────────────────────────────────────
初始: closure = {0} (位掩码 0001 = 1)
第1轮扫描:
状态0在closure中, ε目标: 1, 2
→ 1不在closure → 加入, closure = {0,1} (0011 = 3)
→ 2不在closure → 加入, closure = {0,1,2} (0111 = 7)
changed = true
第2轮扫描:
状态0: ε目标1,2 已在closure中
状态1: ε目标: 无
状态2: ε目标: 无
changed = false → 不动点!
结果: e-closure({0}) = {0,1,2} (位掩码 7)CAUTION
如果只用一次 for 循环扫描，遇到ε链 0→1→2→3 时只能拿到直接ε目标。do-while 是闭包计算的本质——反复迭代直到"稳定"（不动点）。
3. NFA 模拟——状态集演算
3.1 算法流程
NFA 运行时，不是处于"某一个"状态，而是处于"一组可能的状态"。每读入一个符号，计算新的状态集。
输入: 字符串 w = w₁w₂...wₙ
输出: ACCEPT 或 REJECT
current = e-closure({q₀}) ← 初始状态集（含ε闭包）
for i = 1 to n:
next = ∅
for each state s in current: ← 对当前每个可能状态
for each t in δ(s, wᵢ): ← 查symbol转移
next = next ∪ {t}
current = e-closure(next) ← 再求ε闭包
if current ∩ F ≠ ∅: ← 若状态集中包含接受态
return ACCEPT
else:
return REJECT关键细节：每步分为两个阶段——先做 symbol 转移转移（消耗一个输入字符），再做ε-闭包（"免费"移动）。顺序不能颠倒！ 如果先做ε闭包再做 symbol 转移，相当于在消耗符号前多走了ε步，结果会出错。
3.2 完整跟踪："aab"（应接受）
Step 0 (初始):
e-closure({0}) = {0, 1, 2}
状态集: {0,1,2} (位掩码 0111 = 7)
Step 1 (读 'a'):
symbol转移: 从{0,1,2}出发
0 --a--> 无转移
1 --a--> {1} (1的自环)
2 --a--> {3} (2的唯一a转移)
→ 到达: {1, 3} (位掩码 1010 = 10)
e-closure({1,3}) = {1, 3} (1和3都没有ε转移)
状态集: {1,3}
Step 2 (读 'a'):
symbol转移: 从{1,3}出发
1 --a--> {1}
3 --a--> 无转移
→ 到达: {1} (位掩码 0010 = 2)
e-closure({1}) = {1}
状态集: {1}
Step 3 (读 'b'):
symbolol转移: 从{1}出发
1 --b--> {3}
→ 到达: {3} (位掩码 1000 = 8)
e-closure({3}) = {3}
状态集: {3}
最终: {3} ∩ {3} ≠ ∅ → ACCEPT ✓3.3 完整跟踪："aba"（应拒绝）
Step 0: e-closure({0}) = {0,1,2}
Step 1 (读'a'): {1,3} → e-closure → {1,3}
Step 2 (读'b'): {3} → e-closure → {3}
Step 3 (读'a'): ∅ (状态3没有a转移)
→ e-closure(∅) = ∅
最终: ∅ ∩ {3} = ∅ → REJECT ✓NOTE
NFA 模拟的"状态集"会因无法转移而变成空集 ∅（位掩码 0），表示 NFA 已经"卡死"——所有可能路径都已失败。
4. 子集构造——从 NFA 到 DFA
4.1 核心原理
NFA 有 n 个状态，DFA 的每个状态对应 NFA 状态集的一个子集。由于幂集大小为 2ⁿ，DFA 最多有 2ⁿ 个状态。算法系统地枚举所有"可达"的子集。
输入: NFA (Q, Σ, δ, q₀, F)
输出: 等价的DFA (Q', Σ, δ', q₀', F')
1. q₀' = e-closure({q₀}) ← DFA初态 = NFA初态的ε闭包
2. Q' = {q₀'} ← 已发现的DFA状态集
3. 未处理队列 = [q₀']
4. while 未处理队列非空:
S = 取出一个未处理子集
if S ∩ F ≠ ∅: ← S包含NFA接受态
标记S为DFA接受态
for each symbol a in Σ:
T = ∅
for each state s in S:
for each t in δ(s, a):
T = T ∪ {t}
T = e-closure(T) ← 关键: 先symbol转移再ε闭包
if T ≠ ∅:
if T ∉ Q': ← 新子集
Q' = Q' ∪ {T}
将T加入未处理队列
δ'(S, a) = T
else:
δ'(S, a) = 死状态(或留空)
5. 输出 Q', δ', q₀', F'4.2 本题 NFA→DFA 转换全过程
初始:
DFA初态 D0 = e-closure({0}) = {0,1,2} (位掩码 7)
Q' = {D0}, 未处理 = [D0]
────────────────────────────────────────────
处理 D0 = {0,1,2}:
接受态? 3∉{0,1,2} → No
符号 'a':
symbol转移: 0→无, 1→{1}, 2→{3} → {1,3}
e-closure({1,3}) = {1,3} (位掩码 10)
→ 新子集! D1
δ'(D0, a) = D1
符号 'b':
symbol转移: 0→无, 1→{3}, 2→无 → {3}
e-closure({3}) = {3} (位掩码 8)
→ 新子集! D2
δ'(D0, b) = D2
────────────────────────────────────────────
处理 D1 = {1,3}:
接受态? 3∈{1,3} → Yes!
符号 'a':
symbol转移: 1→{1}, 3→无 → {1}
e-closure({1}) = {1} (位掩码 2)
→ 新子集! D3
δ'(D1, a) = D3
符号 'b':
symbol转移: 1→{3}, 3→{3} → {3}
e-closure({3}) = {3} = D2 (已存在)
δ'(D1, b) = D2
────────────────────────────────────────────
处理 D2 = {3}:
接受态? Yes!
符号 'a': 3→无 → ∅ → 无转移(死状态)
符号 'b': 3→{3} → e-closure = {3} = D2 (自环)
────────────────────────────────────────────
处理 D3 = {1}:
接受态? No
符号 'a': 1→{1} → {1} = D3 (自环)
符号 'b': 1→{3} → {3} = D2最终 DFA 转换表：
┌──────────┬──────────────┬────────┬────────┬─────────┐
│ DFA状态 │ NFA子集 │ a │ b │ 接受态? │
├──────────┼──────────────┼────────┼────────┼─────────┤
│ D0 │ {0, 1, 2} │ D1 │ D2 │ No │
│ D1 │ {1, 3} │ D3 │ D2 │ Yes │
│ D2 │ {3} │ — │ D2 │ Yes │
│ D3 │ {1} │ D3 │ D2 │ No │
└───────────┴──────────────┴────────┴────────┴─────────┘DFA 状态转移含义：
a a
┌──→ D0 ──→ D1 ──→ D3 ──┐
│ │ b │ b │ b │
│ ↓ ↓ ↓ │
│ D2 ←─────┘ └─└────┘
│ │ b (自环)
│ └──┘
接受态: D1, D2 (双圈)IMPORTANT
子集构造是"惰性"的——只生成实际可达的 DFA 状态。NFA 有 4 个状态，理论上 16 个可能子集，但本题只有 4 个是可达的。实践中，子集数量通常远小于 2ⁿ。
5. 位掩码状态集表示
使用 int 的低 4 位表示 NFA 状态集，是一种高效且优雅的编码方式：
位掩码编码:
状态0 → bit 0 (值 1 = 0x1)
状态1 → bit 1 (值 2 = 0x2)
状态2 → bit 2 (值 4 = 0x4)
状态3 → bit 3 (值 8 = 0x8)
常用操作:
加入状态s: states |= (1 << s)
检查状态s: if (states & (1 << s))
空集判断: if (states == 0)
包含接受态3: if (states & (1 << 3))| 状态集 | 位掩码值 | 二进制 |
|---|---|---|
| ∅ | 0 | 0000 |
| 1 | 0001 | |
| 2 | 0010 | |
| 4 | 0100 | |
| 8 | 1000 | |
| 3 | 0011 | |
| 7 | 0111 | |
| 10 | 1010 |
WARNING
常见错误：加入状态 s 时写成 states |= s 而非 states |= (1 << s)。当 s=3 时，|=3 只添加了 bit0 和 bit1（值 1+2=3），而非 bit3（值 8）。必须使用 (1 << s) 将状态号转为对应的位。
6. DFA 最小化概念
子集构造产生的 DFA 不一定是最小的。DFA 最小化将"不可区分"的状态合并。两个状态 p 和 q 等价，当且仅当对所有输入串 w，从 p 出发接受 w ⇔ 从 q 出发接受 w。
Hopcroft 算法（简要）：
- 初始划分：接受态组 和 非接受态组
- 反复细化：若同一组中的状态对某个符号转移到不同组，则分裂
- 直到不再再分裂为止
本题 DFA 最小化分析：
初始划分: Π₀ = { {D1, D2}, {D0, D3} }
检查接受态组 {D1, D2}:
符号a: D1→D3, D2→死状态 → 转移目标不在同一组!
→ 分裂: {D1}, {D2}
检查非接受态组 {D0, D3}:
符号a: D0→D1, D3→D3 → D1∈接受态, D3∈非接受态 → 不同组!
→ 分裂: {D0}, {D3}
结论: 本题DFA已经是最小化的(4个状态不可再合并)7. 常见错误速查
| 错误 | 后果 | 正确做法 |
|---|---|---|
位掩码写成 states |= s 而非 states |= (1 << s) | s=3 时只加了 bit0 和 bit1 | states |= (1 << s) |
| ε-闭包只做一轮扫描（不用 do-while） | 遇ε链只能拿到直接ε目标 | do-while 反复迭代至不动点 |
| NFA 模拟中先求ε-闭包再做 symbol 转移 | 多走了不该走的ε步 | 先 symbol 转 转移，再ε-闭包 |
| 子集构造中忘记对新子集求ε-闭包 | 生成的 DFA 不等价 | move(S,a) 之后必须 e_closure |
states & (1<<3) 写成 states == (1<<3) | 状态集含 3 和其他状态时误判 | 用 & 检查是否包含 |
next_subset == 0 时也创建新状态 | 产生多余"空集状态" | 空集直接标记为死状态/无转移 |
参考解答
练习1: e_closure — ε-闭包不动点迭代
#define MAX_STATES 4
#define NO_TARGET -2
int EPSILON_TRANS[MAX_STATES][MAX_STATES] = {
{1, 2, NO_TARGET},
{NO_TARGET},
{NO_TARGET},
{NO_TARGET}
};
/* ε-闭包: 不动点迭代 */
int e_closure(int states) {
int closure = states;
int changed;
do {
changed = 0;
for (int s = 0; s < MAX_STATES; s++) {
if (!(closure & (1 << s)))
continue;
/* 扫描状态s的所有ε目标 */
for (int j = 0; EPSILON_TRANS[s][j] != NO_TARGET; j++) {
int t = EPSILON_TRANS[s][j];
if (!(closure & (1 << t))) {
closure |= (1 << t);
changed = 1;
}
}
}
} while (changed);
return closure;
}要点：用 do-while 反复扫描所有状态，每次发现新的ε可达状态就加入 closure 并标记 changed。当一整轮扫描都没有新状态加入时，达到不动点，返回最终闭包。(1 << s) 将状态号转为位掩码；closure & (1 << t) 检查状态 t 是否已在集合中。
练习2: NFA_simulate — NFA 模拟
#define MAX_STATES 4
#define NO_TARGET -2
int NFA_TRANS[MAX_STATES][2][MAX_STATES] = {
{{NO_TARGET}, {NO_TARGET}},
{{1, NO_TARGET}, {3, NO_TARGET}},
{{3, NO_TARGET}, {NO_TARGET}},
{{NO_TARGET}, {3, NO_TARGET}}
};
void print_states(int states) {
printf("{");
int first = 1;
for (int s = 0; s < MAX_STATES; s++) {
if (states & (1 << s)) {
if (!first) printf(", ");
printf("%d", s);
first = 0;
}
}
printf("}");
}
bool NFA_simulate(const char *input) {
int current = e_closure(1 << 0); // 初始: {0}的ε闭包
printf("Step 0: ");
print_states(current);
printf("\n");
for (int i = 0; input[i] != '\0'; i++) {
int sym = input[i] - 'a'; // 0='a', 1='b'
int next = 0;
/* 先做 symbol 转移 */
for (int s = 0; s < MAX_STATES; s++) {
if (!(current & (1 << s))) continue;
for (int j = 0; NFA_TRANS[s][sym][j] != NO_TARGET; j++) {
int t = NFA_TRANS[s][sym][j];
next |= (1 << t);
}
}
/* 再做ε-闭包 */
current = e_closure(next);
printf("Step %d (read '%c'): ", i + 1, input[i]);
print_states(current);
printf("\n");
if (current == 0) // 卡死
printf(" → dead (no transitions possible)\n");
}
/* 检查是集中包含接受态3 */
return (current & (1 << 3)) != 0;
}核心逻辑：
- 初始状态集 =
e_closure({0})，确保包含所有ε可达状态 - 每读入一个字符，先从当前所有可能状态做 symbol 转移，再对到达的状态集求ε-闭包
- 若某步后状态集变为空（位掩码 0），表示 NFA 已"卡死"
- 最后检查状态集是否包含接受态 3（位掩码
1 << 3= 8）
练习3: subset_construct — 子集构造算法
#define MAX_DFA_STATES 16 // 最多2^4=16个DFA状态
#define NO_TARGET -2
void subset_construct() {
int dfa_states[MAX_DFA_STATES]; // 每个DFA状态的NFA子集
int dfa_accept[MAX_DFA_STATES]; // 是否为接受态
int dfa_trans[MAX_DFA_STATES][2]; // 转移表
int dfa_count = 0;
/* 初始: DFA初态 = e_closure({0}) */
int start = e_closure(1 << 0);
dfa_states[dfa_count] = start;
dfa_count++;
/* BFS 枚举所有可达的DFA状态 */
for (int i = 0; i < dfa_count; i++) {
int S = dfa_states[i];
/* 接受态判定 */
dfa_accept[i] = (S & (1 << 3)) ? 1 : 0;
/* 对每个符号计算转移 */
for (int sym = 0; sym < 2; sym++) {
int T = 0;
/* symbol转移: 从S中的每个状态出发 */
for (int s = 0; s < MAX_STATES; s++) {
if (!(S & (1 << s))) continue;
for (int j = 0; NFA_TRANS[s][sym][j] != NO_TARGET; j++) {
int t = NFA_TRANS[s][sym][j];
T |= (1 << t);
}
}
/* ε-闭包 */
T = e_closure(T);
if (T == 0) {
dfa_trans[i][sym] = -1; // 死状态/无转移
continue;
}
/* 检查 T 是否是新子集 */
int found = -1;
for (int k = 0; k < dfa_count; k++) {
if (dfa_states[k] == T) {
found = k;
break;
}
}
if (found == -1) {
/* 新子集! 加入 */
found = dfa_count;
dfa_states[dfa_count++] = T;
}
dfa_trans[i][sym] = found;
}
}
/* 打印转换表 */
printf("┌──────┬──────────┬─────┬─────┬──────────┐\n");
printf("│ DFA │ NFA子集 │ a │ b │ 接受态? │\n");
printf("├──────┼──────────┼─────┼─────┼──────────┤\n");
for (int i = 0; i < dfa_count; i++) {
printf("│ D%-3d │ {", i);
int first = 1;
for (int s = 0; s < MAX_STATES; s++) {
if (dfa_states[i] & (1 << s)) {
if (!first) printf(",");
printf("%d", s);
first = 0;
}
}
printf("} │");
for (int sym = 0; sym < 2; sym++) {
if (dfa_trans[i][sym] == -1)
printf(" — │");
else
printf(" D%-2d │", dfa_trans[i][sym]);
}
printf(" %-8s │\n", dfa_accept[i] ? "Yes" : "No");
}
printf("└──────┴──────────┴─────┴─────┴──────────┘\n");
printf("Total DFA states: %d\n", dfa_count);
}核心逻辑：
- DFA 初态 =
e_closure({0})，加入子集列表 - BFS 枚举：对每个未处理的子集 S，计算对每个符号的转移目标 T
- T 的计算分两步：先 symbol 转移（从 S 中每个状态出发），再 ε-闭包
- 若 T 是新的子集，加入列表继续处理；若已存在，记录转移关系
- 最后打印完整的 DFA 转换表
对照检查：e_closure 用了 do-while 反复迭代吗？NFA_simulate 中是先 symbol 转转移，再ε-闭包吗？subset_construct 检查了空子集（T==0）不创建新状态吗？位掩码操作用了
(1 << s)而非s吗？
课堂讨论
为什么 NFA 需要ε转移？它有什么实际用途？ — ε转移让 NFA 的构造变得模块化。两个 NFA 的"并"可以通过一个ε转移的新初态连接到两个子 NFA 的初态来实现（Thompson 构造法）。在本题中，ε转移优雅地表达了"要么走 ab 分支，要么走 ab分支"的选择。
如果 NFA 的ε-闭包包含回路会怎样？ — 不动点算法仍然正确。例如，若状态 0→ε→1→ε→0 形成ε环，算法会检测到新状态加入后，下一轮仍然扫描整个 closure，但发现所有ε目标都已存在，
changed = false，正确结束。子集构造的最坏情况是什么？能举一个例子吗？ — 最坏情况是 2ⁿ 个 DFA 状态。经典例子是语言"倒数第 k 个字符是 a"的 NFA，只需要 k+1 个状态，但任何 DFA 至少需要 2^k 个状态。这说明非确定性可以带来指数级的状态压缩。
NFA 模拟和子集构造有什么关系？ — NFA 模拟在运行时动态计算状态集（对特定输入串）；子集构造在编译时预先计算所有可能的状态集（对所有可能输入）。子集构造本质上是"穷举"了 NFA 模拟可能遇到的所有状态集。
如何验证生成的 DFA 是正确际用途？ — 选一组测试串（包括应接受和应拒绝的），同时对 NFA 模拟和 DFA 模拟运行，比较结果。DFA 模拟很简单：从初态 D0 出发，逐字符查表转移，最后检查是否在接受态。
位掩码表示有什么局限性？什么时候不够用？ — 当 NFA 状态数超过 32（或 64）时，单个 int 不够用。此时可以用
unsigned long long（64 位）或uint64_t，或使用位数组/位集结构。不过大多数教学场景的 NFA 状态数不超过 32。
讨论答案
Q1: 为什么 NFA 需要ε转移？
ε转移让 NFA 的构造变得模块化。以本题的 a*b | ab* 为例，如果没有ε转移，从初态 0 出发，读到 'a' 时不知道该走 a* 分支（状态 1）还是 ab*分支（状态 2）。有了ε转移，NFA 在开始时"免费"地同时进入两个分支的起始状态——这就是非确定性的本质应用。
在理论层面，Thompson 构造法用ε转移系统地实现了正则表达式到 NFA 的转换：串联（ε连接）、并联（ε分叉）、星号（ε回环）。ε转移使构造过程保持"局部性"——每个子表达式独立构造，然后通过ε"拼接"。
/* Thompson构造的概念示意 */
/*
* R1·R2 (串联): R1的接受态 ──ε──→ R2的初态
* R1|R2 (并联): 新初态 ──ε──→ R1初态
* └──ε──→ R2初态
* R* (星号): 新初态 ──ε──→ R初态
* R接受态 ──ε──→ R初态 (回环)
* 新初态 ──ε──→ 新接受态 (跳过R)
*/Q2: ε-闭包含回路时不动点算法仍然正确
考虑回路 0→ε→1→ε→0 的情况：
e-closure({0}) 的迭代过程:
初始: closure = {0}
第1轮: 扫描{0} → ε目标1不在closure → 加入, {0,1}
第2轮: 扫描{0} → 1已在 → 跳过; 扫描{1} → ε目标0已在 → 跳过
changed = false → 不动点!
e-closure({0}) = e-closure({1}) = {0,1}这揭示了ε回路的深层含义：如果两个状态互为ε可达，它们实际上是"ε等价"的——在不消耗任何输入的情况下可以互相到达。在 DFA 最小化时，这种等价性可能导致状态合并。算法通过 do-while 自然地处理了回路情况，不会陷入死循环。
Q3: 子集构造的最坏情况与指数膨胀
经典例子是语言 L_k = "倒数数第 k 个字符是 a"。这个语言：
- 可以用一个 k+1 状态的 NFA 表示（只需"记住"k 步之前的字符）
- 任何 DFA 识别该语言至少需要 2^k 个状态（必须"记住"最近 k 个字符的每一种可能）
当 k=3 时：NFA 需要 4 个状态，DFA 需要 8 个状态。当 k=10 时：NFA 只需 11 个状态，DFA 需要 1024 个状态。这说明非确定性可以带来指数级的状态压缩——这是 NFA 真正的理论价值所在。
但在实践中，大多数"自然"的正则表达式产生的 NFA，其等价的 DFA 状态数在多项式范围内。这也是为什么 DFA 方法在实际系统中（如 lex、RE2）是可行的。
Q4: NFA 模拟与子集构造的关系
NFA 模拟 (online): 子集构造 (offline):
───────────── ─────────────────
特定输入串 w 所有可能输入串
↓ ↓
逐步跟踪状态集变化 预先枚举所有可达子集
↓ ↓
判断 w 是否被接受 生成等价 DFA
↓
用 DFA 判断任意串
适合: 偶尔判断少量串 适合: 反复判断大量串
每次都是 O(|w|·|Q|) 预处理 O(2^|Q|)，后续 O(|w|)子集构造可以理解为先对 NFA 做符号执行的穷举——就是编译器前端的静态分析，预先计算所有可能的运行时状态。实际上，子集构造过程中处理每个 DFA 状态的 symbol 转移时，做的计算和 NFA 模拟中一步的 symbol 转移完全相同。
如果只需要判断少数几个串，NFA 模拟更高效（不需要 DFA 的构造开销）；如果需要反复判断大量串（如词法分析），构造 DFA 后每次判断只需 O(n)。
Q5: 验证 DFA 正确性的方法
最可靠的方法是交叉验证——对相同输入串，分别跑 NFA 模拟和 DFA 模拟，比较结果：
/* 验证DFA正确性 */
void verify_conversion() {
const char *tests[] = {
"", "a", "b", "ab", "ba",
"aa", "bb", "aab", "aba", "abb",
"aaab", "aabb", "abab", "abbb",
"aaaab", "aaaaab", "baaa", NULL
};
for (int i = 0; tests[i] != NULL; i++) {
bool nfa_result = NFA_simulate(tests[i]);
bool dfa_result = DFA_simulate(tests[i]); // 需自行实现
printf("%-10s NFA=%s DFA=%s %s\n",
tests[i],
nfa_result ? "✓" : "✗",
dfa_result ? "✓" : "✗",
nfa_result == dfa_result ? "OK" : "MISMATCH!");
}
}DFA 模拟很简单——从初态 D0 出发，逐字符查转移表，最后检查是否在标记的接受态中。不需要ε-闭包，不需要维护状态集——这正是 DFA 的优势。
Q6: 位掩码的局限性与扩展
单个 int（32 位）最多表示 32 个状态，unsigned long long 最多 64 个。当 NFA 状态数超过 64 时，需要更通用的表示：
/* 位数组: 适合大量状态的通用方案 */
#include <stdint.h>
#include <stdlib.h>
typedef struct {
uint64_t *bits; // 每个uint64存64位
int nwords; // 需要多少个uint64
} Bitset;
/* 关键操作 */
void bitset_add(Bitset *bs, int s) {
bs->bits[s / 64] |= (1ULL << (s % 64));
}
int bitset_contains(Bitset *bs, int s) {
return (bs->bits[s / 64] >> (s % 64)) & 1;
}
int bitset_is_empty(Bitset *bs) {
for (int i = 0; i < bs->nwords; i++)
if (bs->bits[i] != 0) return 0;
return 1;
}位掩码的本质是"集合的二进制编码"，位运算是"集合操作的硬件加速"。当状态数增长时，只需要将单个 int 扩展为位数组即可，算法逻辑完全不变。
课后练习
实现 DFA 模拟器。基于子集构造产生的 DFA 转换表，实现
DFA_simulate(input)，不需要ε-闭包，逐字符查表转移即可。验证对"aab"和"aba"的结果与 NFA 模拟一致。知识点提示：DFA 模拟只需一个循环——
current = dfa_trans[current][char_to_idx(ch)]。比 NFA 模拟简单得多，这正是 DFA 的优势。扩展支持任意 NFA。当前 NFA 是硬编码的。修改程序，从 stdin 读取 NFA 定义（状态数、字母表、转移表），然后执行ε-闭包、NFA 模拟和子集构造。
知识点提示：将状态数从 4 泛化为变量 N，转移表动态分配。注意子集构造中 DFA 状态上限为 2^N。
实现 NFA 的并运算。编写
NFA_union(NFA a, NFA b)，用 Thompson 构造法生成识别L(a) ∪ L(b)的新 NFA。新增一个初态，通过ε转移连接到 a 和 b 的初态。知识点提示：新 NFA 的初态通过ε转移分叉到两个子 NFA，新接受态由两个子 NFA 的接受态通过ε转移汇聚。这是正则表达式引擎的基础构件。
参考资料
- Rabin, M. O. & Scott, D. (1959). "Finite Automata and Their Decision Problems". IBM Journal of Research and Development, 3(2), 114–125. — 子集构造的原始论文
- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). — 第 2 章：有限自动机
- Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). — 第 3 章：词法分析中的 DFA 构造
- Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). — 正则语言与有限自动机
- Russ Cox. "Regular Expression Matching Can Be Simple And Fast". — RE2 正则引擎 到 DFA 的应用
"In theory, there is no difference between theory and practice. In practice, there is." — Yogi Berra