企业官网建设流程全解析

简介：面向编译原理课程中 NFA 转 DFA 并最小化实验的代码与报告资源，由 ZZU 学生整理，适合计算机相关专业本科生对照实现与复习备考。压缩包共 2 个文件，其中 C++ 源文件实现了子集构造法将 NFA 转为 DFA，并通过合并等价状态完成 DFA 最小化；Word 实验报告详细记录了实验目的、步骤、遇到的问题及解决方案，便于理解自动机理论在词法分析中的应用。资源包仅 722KB，轻量易用，已有 413 人学习浏览。代码注重算法流程清晰，报告结构完整，既可作为课设提交模板，也能用于巩固子集构造、状态等价划分等重点难点，对正在完成编译原理实验的学生具有直接参考价值。 编译原理课在ZZU有一个很经典的实验：NFA转DFA并最小化。我把这个实验拆开看，其实就是两件事——先用子集构造法把不确定的自动机变成确定的，再用划分法把确定自动机里行为完全一样的等价状态合并掉。代码量说实话不大，核心逻辑加起来两百行左右，但每年都有不少人栽在ε-closure和划分法的细节上。这篇文章把我整理过的完整实现思路、实验报告写法、以及我踩过的坑都写出来，适合正在做这个实验、或者想彻底搞懂NFA和DFA之间转换关系的人。

1. 这实验到底考什么：一条线串起三个算法

1.1 题面拆解

ZZU的编译原理实验指导书通常会给出这样的要求：输入一个正则表达式，经过一系列转换，输出一个等价的最小化DFA。这个流程在教材上被分成三个算法——从正则表达式构造NFA（Thompson构造法）、NFA转DFA（子集构造法）、DFA最小化（划分法）。

我在做的时候发现，很多人把时间耗在第一步的正则解析上，反而忽略了后面两个核心算法。这里先说明白：本文重点讲后两段，也就是"如何写出NFA转DFA的代码"和"如何写出最小化DFA的代码"。如果你实验指导书要求从正则表达式开始，那只需要把Thompson构造法的NFA输出对接上即可，我下面定义的数据结构完全兼容。

1.2 为什么需要这三步

NFA对"人"友好，因为从正则表达式构造NFA的过程完全机械，几乎不需要思考。但NFA对"机器"不友好，比如字符串abb在NFA里可能同时存在多条匹配路径，词法分析器如果直接照着NFA跑，每一步都需要回溯，性能完全不可控。

DFA就不一样了，它每个状态在某个输入符号下有且只有一个转移目标，匹配字符串就是一次线性扫描。所以编译器后端宁可要一个状态更多但确定性的自动机，也不要一个状态更少但充满不确定性的自动机。

而最小化DFA就更有工程味道了。子集构造法生成的DFA状态数往往是原来的好几倍，但这些状态里有很多是"行为一致"的，它们可以合并。状态少了，查表空间就小了，词法分析器的运行效率也会提升。说白了，这个实验不只是让你背算法，而是在演示一个典型的编译优化过程。

1.3 一个通用的NFA数据结构

在写代码之前，先把NFA的存储方式定下来。我选择用字典表示转移函数，原因很简单：(状态, 符号) -> 目标状态集合天然就是字典的key-value结构，查起来又快又直观。

nfa = { "states": {0, 1, 2, 3}, "alphabet": {"a", "b"}, "transitions": { (0, "a"): {1}, (1, "ε"): {2}, (2, "b"): {3}, }, "start": 0, "accepting": {3}, }

这里的ε我用一个普通字符串表示，你放心，它不会和输入字母表里的真实符号冲突，因为正规的字母表里不会允许 ε 作为输入字符。转移函数里查不到某个(state, symbol)的key时，就说明该状态在当前符号下没有转移，目标集合为空集，代码里直接当空处理就行。

2. 子集构造法实现：核心是两个基本函数

2.1 ε-closure和move这两个操作先搞明白

子集构造法的理论很绕，但落到代码上，真正的核心就两个操作。

第一个是eps_closure(states)：从当前状态集合出发，沿着所有的 ε 边能够到达的所有状态的集合。这个操作本质是一个图上遍历问题，用BFS或者DFS都能实现。注意它必须把传入的状态本身也包含在结果里，因为一个状态通过零条ε边到达的还是它自己。

第二个是move(states, symbol)：从当前状态集合出发，沿着某条具体的输入符号边能到达的所有状态的集合。这个操作很简单，就是把这组状态每一个都在转移表里查一遍，把目标合并。

这两个操作的关系是这样：NFA转DFA时，对某个DFA状态（它本身是一个NFA状态集合），读取符号a后的目标状态，不是直接等于move(current, 'a')，而是eps_closure(move(current, 'a'))。因为到达目标后，还能继续沿ε边往下走，必须把ε闭包也包进来才是完整的后继状态。当时我就是漏了这层包裹，导致结果差一截。

2.2 子集构造主循环：一个队列清空为止

有了上面两个函数，主循环的思路就清晰了：

1. 先把NFA的起始状态的ε闭包算出来，它作为DFA的起始状态。
2. 把这个状态标记为"未处理"，进入待处理队列。
3. 每次从队列里取出一个状态，对字母表里的每个符号，计算eps_closure(move(current, symbol))，得到一个新的NFA状态集合。
4. 如果这个集合之前没见过，就分配一个新DFA状态名，放进待处理队列。
5. 记录(当前DFA状态, 符号) -> 目标DFA状态的转移关系。
6. 重复直到队列为空。

这本质上是对所有可达的NFA状态子集做一次全图遍历。这里有个容易剩的细节：DFA状态必须用不可变的frozenset作为字典key，因为普通set在Python里不可哈希，没法作为key。

2.3 核心代码：从NFA到DFA

我直接用Python写一套可运行的版本，你如果实验要求用C/C++，逻辑完全一样，把set换成std::set或bitset即可。

def eps_closure(nfa, states): stack = list(states) closure = set(states) while stack: s = stack.pop() nxt = nfa["transitions"].get((s, "ε"), set()) for t in nxt: if t not in closure: closure.add(t) stack.append(t) return closure def move(nfa, states, symbol): result = set() for s in states: nxt = nfa["transitions"].get((s, symbol), set()) result.update(nxt) return result def nfa_to_dfa(nfa): start_set = frozenset(eps_closure(nfa, {nfa["start"]})) state_map = {start_set: "A"} unmarked = [start_set] dfa_transitions = {} while unmarked: current = unmarked.pop(0) cur_name = state_map[current] for sym in nfa["alphabet"]: if sym == "ε": continue nxt_set = frozenset(eps_closure(nfa, move(nfa, current, sym))) if len(nxt_set) == 0: continue if nxt_set not in state_map: state_map[nxt_set] = chr(ord("A") + len(state_map)) unmarked.append(nxt_set) dfa_transitions[(cur_name, sym)] = state_map[nxt_set] dfa_accepting = set() for st_set, name in state_map.items(): if any(s in nfa["accepting"] for s in st_set): dfa_accepting.add(name) return state_map, dfa_transitions, dfa_accepting

2.4 状态命名与接受状态判断

状态命名我用A、B、C这样递增的字符。这里的顺序有一个事实上的规律：先分配的状态，往往就是距离起始状态较近的状态，输出起来比较自然。

接受状态判断要特别注意一个原则：只要DFA状态对应的NFA状态集合里，包含任意一个NFA接受状态，这个DFA状态就是接受状态。反过来不对——不是说"所有NFA状态都必须是接受状态"。这个细节理解错了，最小化后会得到完全错误的划分结果。

3. DFA最小化：划分法的代码落地

3.1 先做一次可达性清洗

最小化之前，强烈建议先做一步预处理：删除不可达状态。子集构造法理论上不会产生不可达状态，但如果你是自己手工构造的DFA，或者从前一步接的数据有问题，这一步能帮你节省大量排查时间。

做法本身很简单：从起始状态出发，沿所有符号跑一遍BFS，能遍历到的状态就是可达的。然后把可达状态之外的转移和状态列表全部删掉。我遇到过同学拿着一个有不可达状态的DFA做最小化，初始划分把不可达状态也放进去了，结果新DFA里凭空多出几个没人能到达的状态，整个最小化结果看起来非常奇怪。

3.2 初始划分：接受和非接受先分开

最小化的理论依据是"等价状态"：如果两个状态在任意输入下，最终的接受/拒绝行为完全一致，那它们就可以合并。Hopcroft算法虽然是更优的划分方式，但工程和实验层面，"划分细化法"反而更好写、更好验证。

第一步永远是把DFA状态集划分成两个组：接受状态组和非接受状态组。为什么要这么分？因为等价状态有个最底层的约束：接受状态和非接受状态在空串下行为就不同，不可能等价。

3.3 迭代细化：用行为指纹分裂组

划分法的核心是反复检查每个组里的状态，看它们在某个符号下是否"跳出了本组"。具体做法是：对组内每个状态，计算它分别在每个输入符号下到达的目标状态，记录这些目标状态各自属于当前划分的第几组，形成一个"行为指纹"。如果组内某两个状态的行为指纹不同，说明它们在某个符号输入后走到了不同性质的组，必须分裂开。

举个最直观的例子：某组里有状态X和Y，在输入a时，X跳到组0，Y跳到组1，那X和Y绝对不可等价，因为后面发生的事完全不同。

3.4 最小化完整代码

def minimize_dfa(state_map, dfa_transitions, dfa_accepting, alphabet): states = set(state_map.values()) symbols = [s for s in alphabet if s != "ε"] partition = [set(dfa_accepting), set(states) - set(dfa_accepting)] partition = [g for g in partition if g] while True: new_partition = [] for group in partition: fingerprint = {} for st in group: behavior = [] for sym in symbols: target = dfa_transitions.get((st, sym)) group_index = None for idx, g in enumerate(partition): if target in g: group_index = idx break behavior.append(group_index) key = tuple(behavior) fingerprint.setdefault(key, set()).add(st) new_partition.extend(fingerprint.values()) if len(new_partition) == len(partition): partition = new_partition break partition = new_partition return partition

这个写法里有个小trick：对每个状态生成行为指纹后，用字典的setdefault把指纹相同的状态塞进同一集合，一句话就完成了按指纹分组。你如果写C++，可以用map<vector<int>, vector<int>>达到同样效果。

3.5 重命名状态并输出新DFA

划分完成后，需要把每个组映射成一个新状态，重新生成转移表。我的做法是给组按顺序编号S0, S1, S2...，然后遍历原DFA的每一条转移，把源状态和目标状态都替换成组编号。

这里还有一个容易忽略的细节：最小化后的DFA的起始状态，就是原起始状态所在的组；接受状态是那些"整个组都属于原来接受集合"的组。由于初始划分已经保证了接受态和非接受态不会在同一个组里，所以这一步判断非常简单。

4. 怎么验证程序对不对：这类实验的测试玄学

4.1 手工可算的经典用例

写完了代码，怎么确信它是对的？我的习惯是找一个能手工推演的用例，把程序输出和手算结果逐行对照。

推荐使用正则表达式(a|b)*abb对应的NFA。这个例子在龙书里出现过，也是我实验时拿来做验证的标准用例。手工推导的结果是：转换后的DFA有5个状态（记为A到E），其中E是接受状态；最小化之后变成4个状态，因为有两个状态在行为上等价的。如果你跑出来的结果和这个对不上，那一定哪里出了问题。

为什么这个用例好？因为它既包含了ε转移，又有多个不同的可达子集，还真的存在可合并的等价状态。一个用例能同时检验NFA转DFA和最小化两个阶段的正确性。

4.2 逐步打印调试法

调试这类算法，我强烈建议写一个"调试输出函数"，每一步都打印当前队列内容、当前状态集合、计算出的ε闭包。比如在子集构造的主循环里，把每个当前状态和它产生的所有后继集合都打出来。

很多bug本质上是状态集合算错了，但如果你只盯着最终DFA看，根本看不出是哪个中间步骤出了问题。把每一步的eps_closure(move(...))结果都打印出来，对照教材上手工推导的每一步，几秒钟就能定位到问题。

4.3 边界情况清单

我整理了一份经常被忽视的边界情况，做实验前先自查：

• NFA只有一个状态，且没有转移，空串可接受。这时DFA应当只有一个状态，而且它是接受状态。
• 某个DFA状态在某符号下没有任何转移。代码里要允许target不存在，行为指纹里记为None。
• 全体状态都是接受状态。初始划分里"非接受组"是空集合，代码要先过滤空组。
• 存在不可达状态。这个前面提过，先删再最小化。

这些边界情况看着不起眼，但往往是验收老师最喜欢问的"你这个程序能处理吗"的问题。

5. 实验报告怎么写老师才会给高分

5.1 报告不是代码粘贴板

我见过很多人把实验报告写成"代码打印版"，一个类图都没有，DFS讲解也没有，全是代码。这种报告在ZZU的编译原理实验里，一般只能拿个及格分。

老师的评分逻辑其实很简单：实验核心算法你是否真的理解了。这种理解没法通过代码体积证明，只能通过文字、图表、步骤推演来传递。所以报告里一定要有算法流程图（手画或截图都行）、关键数据结构说明、以及至少一个用例的完整推导过程。

5.2 一份高分报告的结构

我在最终提交时用的是这个结构，你可以直接参考：

• 实验目的：两句话点明"掌握子集构造法和划分法"。
• 算法设计：分别说明NFA转DFA和最小化的核心思想，最好有一个状态集合转换的例子。
• 数据结构设计：解释为什么用字典存转移、为什么用frozenset作为状态key。
• 核心代码：只贴关键函数，不要贴完整文件，代码里要有充分注释。
• 测试与分析：给出(a|b)*abb的完整推演结果，包含每一步的状态集合。
• 遇到的问题：我在报告里写的是"ε-closure计算时遗漏了起始状态本身"和"最小化时初始划分忘记过滤空组"，这些真实的踩坑记录反而很加分，说明你真的调过、想过。

5.3 让"测试与分析"部分更有说服力

写测试部分时，不要只贴一张控制台截图。更好的做法是给一个三列表格：输入字符串、手动推导结果、程序输出结果。比如"abb -> 接受"、"abba -> 不接受"、"babb -> 接受"等等。

字符串覆盖要讲究：最短接受串、最长拒绝串、包含死循环的回退串、空串。把这些结果整理成表格，老师一眼就看出你程序的行为是对的，比你在报告里夸自己十句都管用。

6. 我踩过的坑和编写心得

6.1 三个隐蔽bug，每一个都能让你调试到怀疑人生

第一个是move和eps_closure的顺序问题。有人写成move(eps_closure(...), sym)，有人写成eps_closure(move(...))。这两种语义完全不同。正确顺序一定是先move再closure，因为ε边可能在符号边之后继续延伸，但绝不会在符号边之前帮你读入一个符号。这个顺序我当时混淆过一次，输出的DFA状态弧全乱套了。

第二个是frozenset使用问题。Python的字典key必须是可哈希的，普通set不可哈希，要是一不小心用set当key，程序一运行就报TypeError: unhashable type: 'set'。解决办法是统一转成frozenset。

第三个是死状态的处理。DFA最小化时，如果一个状态在某个符号下没有转移，它的行为指纹里该符号对应的组编号就会是None。两个状态同样没有转移，它们在这个符号下的指纹应当一致，都是None，这样它们才可能等价。一开始我在处理这种行为时用了不同的默认值，导致两个等价状态没合并成功，状态数多了一个。

6.2 对性能的一点点扩展思考

实验本身对性能要求不高，但如果后续往下做词法分析器，状态表的存储方式就要重新考虑了。我当时实验用的是"矩阵式"转移表，也就是用二维数组存状态和符号的交叉表，查起来复杂度O(1)。而子集构造法里用字典存稀疏转移，在实验规模下更方便调试。

还有一个扩展方向是Hopcroft算法。划分法在实验层面足够用，但Hopcroft算法把待处理组用栈或队列管理，能在O(n log n)时间内完成最小化。有兴趣的话，可以在实验报告的"改进方向"里提两笔，老师对这个比较有兴趣，但代码主体不要换，否则出了问题反而得不偿失。这个实验做完之后，我最大的感受是：编译原理里最抽象的"自动机"概念，其实是可以用几百行代码、几十个状态集合、一张转移表来摸得着的东西。如果你现在正被 ε-closure 绕晕，或者最小化结果总差一个状态，别急着怀疑自己，把每一步集合都打印出来手推一遍，基本都能找到原因。

本文还有配套的精品资源，点击获取