简介：这份资源面向高校『编译原理』课程学习者，尤其是ZZU的学弟学妹，提供NFA转DFA并最小化实验的完整代码与实验报告，帮助解决自动机理论抽象、子集构造法实现困难、DFA状态冗余等实验痛点。压缩包共2个文件，包含1个cpp源码和1个doc实验报告，整体约722KB，源码可直接编译运行，报告则完整记录实验目的、步骤、问题与解决方案，便于对照理解算法细节。目前已有414人学习下载，说明该实验在课程中具有较高参考价值。读者可从中获得子集构造法将NFA转为DFA的具体实现思路、DFA最小化中识别并合并等价状态的方法，以及C++在算法密集型任务中的编程实践，适合作为课程实验的参考模板与排错对照，帮助将抽象理论落地为可运行代码。
1. NFA 转 DFA 并最小化：编译原理实验里最值得手写一遍的算法
如果你正在做编译原理实验，看到“NFA 转 DFA 并最小化”这个题目，大概率第一反应是：书上伪代码看懂了，真让我写代码又不知道从哪下手。这个实验的核心链路其实就三步——用子集构造法把非确定性有限自动机（NFA）转成确定性有限自动机（DFA），再用 Hopcroft 或填表法把 DFA 里等价的状态合并掉，最后用一组测试串验证语言是否一致。它解决的是词法分析器自动生成的关键一环：正则表达式先转 NFA，再转 DFA，最后最小化，才能得到状态数最少、查表最快的识别器。适合正在写编译原理实验、想自己实现一遍而不是调库的同学，也适合已经写完但结果对不上、想排查哪里出错的熟手。ZZU 的实验中通常要求同时提交代码和实验报告，所以下面既讲实现，也讲怎么把过程写清楚。
2. 子集构造法：从 NFA 到 DFA 的手写实现
2.1 为什么不能直接拿 NFA 做词法分析
NFA 的核心问题是“不确定性”：同一个状态面对同一个输入字符，可能有多条出边，还可能走空串 ε 跳转。词法分析器在扫描字符流时，每一步都必须知道“当前唯一的状态是什么”，否则就没法用一张二维表来驱动。子集构造法的思路很直接：把 NFA 里“所有可能同时处于的状态”打包成一个集合，这个集合就是 DFA 的一个状态。这样虽然状态数可能指数级膨胀，但至少是确定的。
我一般会先把 NFA 的数据结构定下来，再写三个基础函数：ε-闭包、move 集合、以及子集构造主循环。数据结构选错，后面全是坑。
# NFA 表示：状态用整数编号，转移表用 dict 嵌套 # transitions[state][char] = set of next states # char 为 '' 表示 ε 转移 nfa_transitions = { 0: {'': {1}, 'a': {2}}, 1: {'b': {1, 3}}, 2: {'a': {2}, 'b': {3}}, 3: {} } nfa_start = 0 nfa_accept = {3}这段结构里，''专门留给 ε 边，避免和真实字符混淆。状态编号用整数，方便后面做集合运算和排序输出。接受状态用 set，因为子集构造后一个 DFA 状态可能包含多个 NFA 接受状态。
2.2 ε-闭包和 move：两个必须写对的函数
ε-闭包的定义是：从某个状态集合出发，只走 ε 边能到达的所有状态，包括集合本身。move 则是：从某个状态集合出发，走一条指定字符边能到达的状态集合，注意这里不包含 ε 闭包，闭包要在外面单独套一层。
def epsilon_closure(states, transitions): """计算状态集合的 ε-闭包""" stack = list(states) closure = set(states) while stack: s = stack.pop() for nxt in transitions.get(s, {}).get('', set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return closure def move(states, char, transitions): """从状态集合走一条 char 边到达的状态集合""" result = set() for s in states: result |= transitions.get(s, {}).get(char, set()) return resultepsilon_closure用栈做深度优先遍历，避免递归深度过大。move只负责走一步，不负责闭包，这样职责清晰。参数transitions统一传入，方便后面替换成从文件读入的 NFA。
2.3 子集构造主循环：从初始闭包开始扩展
主循环的逻辑是：初始状态是epsilon_closure({nfa_start})，然后不断从队列里取一个 DFA 状态，对字母表中每个字符计算epsilon_closure(move(...))，如果这个新集合没出现过，就加入队列。字母表要从 NFA 的所有转移里收集，排除''。
def nfa_to_dfa(nfa_transitions, nfa_start, nfa_accept): alphabet = set() for s, trans in nfa_transitions.items(): for ch in trans: if ch != '': alphabet.add(ch) alphabet = sorted(alphabet) start_set = frozenset(epsilon_closure({nfa_start}, nfa_transitions)) dfa_states = [start_set] dfa_trans = {} queue = [start_set] state_index = {start_set: 0} while queue: current = queue.pop(0) idx = state_index[current] dfa_trans[idx] = {} for ch in alphabet: nxt_set = frozenset( epsilon_closure(move(current, ch, nfa_transitions), nfa_transitions) ) if not nxt_set: continue if nxt_set not in state_index: state_index[nxt_set] = len(dfa_states) dfa_states.append(nxt_set) queue.append(nxt_set) dfa_trans[idx][ch] = state_index[nxt_set] dfa_accept = { state_index[s] for s in dfa_states if s & nfa_accept } return dfa_trans, 0, dfa_accept, dfa_states这里用frozenset做字典键，因为普通 set 不可哈希。state_index同时承担去重和编号两个职责。dfa_accept的判断条件是“集合与 NFA 接受集有交集”，不是包含，这点容易写错。返回的dfa_states保留原始集合信息，方便调试时打印每个 DFA 状态对应哪些 NFA 状态。
2.4 用一组测试串验证转换是否正确
转换完不能只看代码跑通，要用测试串验证语言是否一致。我一般写一个简单的模拟器，分别跑 NFA 和 DFA，对比接受结果。
def simulate_dfa(dfa_trans, start, accept, text): state = start for ch in text: if ch not in dfa_trans.get(state, {}): return False state = dfa_trans[state][ch] return state in accept def simulate_nfa(nfa_transitions, start, accept, text): current = epsilon_closure({start}, nfa_transitions) for ch in text: current = epsilon_closure(move(current, ch, nfa_transitions), nfa_transitions) if not current: return False return bool(current & accept) tests = ['', 'a', 'ab', 'aab', 'abbb', 'b', 'ba'] for t in tests: r1 = simulate_nfa(nfa_transitions, nfa_start, nfa_accept, t) r2 = simulate_dfa(dfa_trans, 0, dfa_accept, t) print(t, r1, r2, 'OK' if r1 == r2 else 'MISMATCH')如果出现 MISMATCH，优先检查 ε-闭包是否在 move 之后又套了一层，以及接受状态判断是否用了交集。这两个地方是血泪经验里翻车最多的点。
3. DFA 最小化：填表法和 Hopcroft 怎么选
3.1 最小化的本质是合并等价状态
DFA 最小化的目标是：找到所有“行为等价”的状态，把它们合并成一个。两个状态等价，当且仅当对于任意输入串，从它们出发要么都接受要么都拒绝。实际算法不会真的枚举所有串，而是用“可区分”关系逐步细分：先标记接受状态和非接受状态可区分，然后不断迭代，如果两个状态在某个字符下转移到已标记可区分的状态对，那它们也可区分。
填表法（也叫划分法）适合状态数不多的实验场景，代码直观，报告里也好写。Hopcroft 算法效率更高，但实现复杂度大，ZZU 的实验一般用填表法就够。
3.2 填表法的三个步骤
第一步，去掉不可达状态。从 DFA 初始状态做一次 BFS，只保留能到达的状态。第二步，初始化可区分表，所有“一个接受一个不接受”的状态对标记为可区分。第三步，反复扫描所有未标记的状态对，如果它们在某个字符下转移到的状态对已被标记，则当前对也标记，直到没有新标记产生。
def minimize_dfa(dfa_trans, start, accept): # 1. 去掉不可达状态 reachable = set() stack = [start] while stack: s = stack.pop() if s in reachable: continue reachable.add(s) for ch, nxt in dfa_trans.get(s, {}).items(): stack.append(nxt) states = sorted(reachable) n = len(states) idx = {s: i for i, s in enumerate(states)} # 2. 初始化可区分表 distinguishable = [[False] * n for _ in range(n)] for i in range(n): for j in range(i + 1, n): if (states[i] in accept) != (states[j] in accept): distinguishable[i][j] = True # 3. 迭代标记 changed = True while changed: changed = False for i in range(n): for j in range(i + 1, n): if distinguishable[i][j]: continue for ch in set(dfa_trans.get(states[i], {})) | set(dfa_trans.get(states[j], {})): ni = dfa_trans.get(states[i], {}).get(ch) nj = dfa_trans.get(states[j], {}).get(ch) if ni is None or nj is None: if ni != nj: distinguishable[i][j] = True changed = True break else: a, b = idx[ni], idx[nj] if a > b: a, b = b, a if distinguishable[a][b]: distinguishable[i][j] = True changed = True break # 合并等价状态 parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x for i in range(n): for j in range(i + 1, n): if not distinguishable[i][j]: pi, pj = find(i), find(j) if pi != pj: parent[pi] = pj # 构建新转移表 new_trans = {} new_accept = set() group_map = {} for i, s in enumerate(states): root = find(i) if root not in group_map: group_map[root] = len(group_map) gid = group_map[root] if s in accept: new_accept.add(gid) new_trans.setdefault(gid, {}) for ch, nxt in dfa_trans.get(s, {}).items(): nroot = find(idx[nxt]) new_trans[gid][ch] = group_map.setdefault(nroot, len(group_map)) new_start = group_map[find(idx[start])] return new_trans, new_start, new_accept这段代码里，distinguishable只填上三角，比较时统一把小的索引放前面。合并用并查集，比反复扫描等价类列表更稳。group_map.setdefault那行要小心，如果目标组还没分配编号，会现场分配，保证转移表完整。
3.3 最小化前后的状态数对比与验证
最小化做完，必须验证两件事：语言是否一致，状态数是否真的减少。验证语言还是用前面的simulate_dfa，把最小化前后的 DFA 都跑一遍测试串。状态数对比可以直接打印。
print('DFA states:', len(dfa_trans)) print('Minimized states:', len(new_trans)) for t in tests: r1 = simulate_dfa(dfa_trans, 0, dfa_accept, t) r2 = simulate_dfa(new_trans, new_start, new_accept, t) print(t, r1, r2, 'OK' if r1 == r2 else 'MISMATCH')如果最小化后状态数没变，不一定是代码错，可能是原 DFA 本身已经最小。但如果语言验证出现 MISMATCH，优先检查并查集合并后接受状态的映射是否正确，以及转移目标是否用了根节点编号。
4. 实验报告怎么写才不被扣分：结构、数据和踩坑记录
4.1 报告里必须出现的三张表
ZZU 的实验报告通常要求写清楚算法过程。我建议至少放三张表：NFA 的原始转移表、子集构造过程中每个 DFA 状态对应的 NFA 状态集合、最小化后的状态合并关系。第一张表直接列状态 | 字符 | 目标状态，第二张表列DFA 状态编号 | NFA 状态集合 | 是否接受，第三张表列合并前状态 | 合并后组号。有这三张表，老师一眼就能看出你不是抄的。
| 表名 | 作用 | 数据来源 |
|---|---|---|
| NFA 转移表 | 说明输入自动机结构 | 题目给定或自己构造 |
| 子集构造对照表 | 证明 DFA 状态来源 | dfa_states列表 |
| 最小化合并表 | 证明等价类划分 | 并查集parent数组 |
4.2 测试用例要覆盖空串、单字符和混合串
测试串不能只写ab这种。空串用来验证 ε-闭包和初始状态接受性，单字符验证基本转移，混合串验证多步闭包。我一般会准备 8 到 10 个串，包含接受和拒绝两类，并在报告里列出每个串在 NFA、DFA、最小化 DFA 下的结果。如果三者一致，基本可以说明实现正确。
4.3 代码注释和变量命名直接影响报告分
实验报告里的代码片段不要直接贴一大坨，按功能分块贴，每块前面写一句“这一步在做什么”。变量名用epsilon_closure、distinguishable这种能自解释的，别用f1、arr2。老师看报告的时间有限，命名清晰能省很多事。
5. 避坑与排查：NFA 转 DFA 最小化最常见的 5 个翻车点
5.1 现象：DFA 状态数爆炸，跑半天不出结果
原因：NFA 的 ε 边太多，或者字母表收集时把''也当成普通字符，导致子集构造对空字符也做 move，产生大量无意义状态。解决：字母表收集时显式排除''，并且 ε-闭包只在 move 之后调用一次，不要在 move 内部递归调用闭包。
5.2 现象：测试串在 NFA 和 DFA 下结果不一致
原因：接受状态判断写成了“集合包含于 NFA 接受集”，正确应该是“集合与 NFA 接受集有交集”。解决：把s <= nfa_accept改成s & nfa_accept，并加一个空串测试用例专门验证初始状态。
5.3 现象：最小化后状态数没减少，但语言验证通过
原因：原 DFA 可能已经是最小 DFA，或者可区分表初始化时只标记了接受与非接受，漏掉了不可达状态。解决：先做可达性分析，把不可达状态从状态列表里删掉，再跑最小化。如果删完还是没减少，检查是否所有状态对都真的等价。
5.4 现象：并查集合并后转移表指向了错误的组号
原因：group_map.setdefault在构建转移表时动态分配组号，可能导致同一个根节点在不同转移里拿到不同编号。解决：先遍历所有状态，把每个根节点的组号固定下来，再构建转移表。或者用两遍扫描：第一遍分配组号，第二遍填转移。
5.5 现象：报告里贴的代码和实际跑的不一致
原因：调试过程中改了代码但忘了同步报告，或者报告里贴的是伪代码。解决：报告里的代码直接从最终版本复制，贴之前再跑一遍测试用例，确认输出和报告里的表格一致。这个坑看起来低级，但每年都有不少人栽。
6. 进阶技巧：用最小化 DFA 反推正则表达式并做词法分析器原型
最小化 DFA 不只是实验终点，它可以继续往下走。一个具体技巧是：把最小化后的 DFA 用状态消除法反推正则表达式，验证你实现的自动机是否真的对应题目给定的正则。状态消除法的规则是：对每个非初始非接受状态，把它从图中删掉，同时更新所有入边和出边之间的正则表达式，最后剩下初始到接受的一条边，就是结果。
# 状态消除法伪代码示意，实际实现需要处理正则表达式的并、连接和闭包 # 这里只展示消除顺序的选择逻辑 def eliminate_order(dfa_trans, start, accept): states = set(dfa_trans.keys()) order = [] candidates = states - {start} - accept # 优先消除入度和出度乘积最小的状态，减少表达式膨胀 while candidates: best = min(candidates, key=lambda s: ( sum(1 for u in dfa_trans for ch in dfa_trans[u] if dfa_trans[u][ch] == s) * len(dfa_trans.get(s, {})) )) order.append(best) candidates.remove(best) return order这个技巧的价值在于：如果你反推出来的正则和题目给定的一致，说明整个 NFA 转 DFA 再最小化的链路完全正确。另一个进阶方向是把最小化 DFA 直接转成词法分析器的转移表，用二维数组或字典驱动，扫描时每读一个字符查一次表，遇到接受状态就切词。这样你就能从实验代码过渡到一个能跑的小型词法分析器原型。
我自己做这个实验时，最大的教训是：不要等全部写完再测试，每写完一个函数就用小规模 NFA 验证一次。ε-闭包和 move 这两个函数如果一开始就写错，后面子集构造和最小化全是连锁反应，调试起来像在黑匣子里摸。后来我养成的习惯是，每加一个功能就先跑空串和单字符，确认基础路径通了再往下走。希望帮到你。
本文还有配套的精品资源，点击获取
