简介这份资源面向高校『编译原理』课程学习者尤其是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, keylambda 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 这两个函数如果一开始就写错后面子集构造和最小化全是连锁反应调试起来像在黑匣子里摸。后来我养成的习惯是每加一个功能就先跑空串和单字符确认基础路径通了再往下走。希望帮到你。本文还有配套的精品资源点击获取