简介这份资源面向高校「编译原理」课程学习者尤其是ZZU的学弟学妹提供NFA转DFA并最小化实验的完整代码与实验报告帮助解决自动机理论中从非确定有限自动机到确定有限自动机转换及状态化简的实践难题。压缩包共2个文件包含1个cpp源代码和1个doc实验报告整体约722KB代码用C实现子集构造法与DFA最小化算法报告则记录实验目的、步骤、问题与解决方案两者配合便于对照理解算法细节。目前已有415人学习下载说明该实验在课程中具有较高参考价值。读者可借助代码直接运行验证转换结果通过报告梳理子集构造、不可达状态消除与等价状态合并等关键环节并参考其中的排错思路与实验总结将抽象理论落到编程实践适合需要完成同类实验或复习自动机内容的同学。1. 从手写词法分析器到自动机流水线这份编译原理实验资源到底能省多少事如果你正在上编译原理课大概率会在某个深夜对着“子集构造法”四个字发呆——老师讲的时候好像听懂了真让你把 Thompson 构造出来的 NFA 转成 DFA再跑一遍最小化手算状态表能算到怀疑人生。这份「NFA转DFA并最小化」的代码加实验报告资源就是冲着这个场景来的。它把编译原理里最经典也最容易翻车的自动机等价变换链路从理论推导到可运行代码完整串了一遍适合正在做课程实验的本科生、准备考研复试被问到自动机细节的选手以及想用 C 把算法真正落地一遍的开发者。核心价值不在于代码有多长而在于它把状态集合的表示、子集构造的迭代顺序、最小化时的等价类划分这些“老师默认你会、但你其实不会”的环节全部摊开写清楚了。2. 自动机变换的理论骨架为什么子集构造和最小化必须一起做2.1 NFA 到 DFA 的子集构造法到底在构造什么先把概念钉死。NFA 和 DFA 的唯一本质区别在于DFA 的每个状态对同一个输入符号最多只有一条出边而 NFA 可以有多条还可以有 ε 转移。子集构造法的核心思想是把 NFA 的“一组状态”打包成 DFA 的“一个状态”。具体来说DFA 的初始状态是 NFA 初始状态的 ε-闭包然后对每个 DFA 状态和每个输入符号计算从该状态集合出发经过该符号能到达的所有 NFA 状态的 ε-闭包如果这个新集合没出现过就作为新的 DFA 状态加入。这里有两个关键操作必须实现正确ε-闭包和 move 操作。ε-闭包指的是从某个状态集合出发只走 ε 边能到达的所有状态包括自身move 操作指的是从某个状态集合出发走一条标号为某输入符号的边能到达的状态集合。子集构造的每一轮迭代都是先 move 再求 ε-闭包。很多同学手算时容易漏掉“ε-闭包要递归展开”这一点导致状态集合少算最终 DFA 状态数对不上。用 C 实现时状态集合通常用std::setint或std::vectorint加排序去重来表示再用std::mapstd::setint, int建立“NFA 状态集合 → DFA 状态编号”的映射。这个映射就是整个算法的黑匣子所有查重和编号都靠它。2.2 DFA 最小化的等价类划分逻辑DFA 最小化的目标是合并等价状态得到状态数最少且功能等价的 DFA。经典算法是 Hopcroft 划分法或者更朴素的 Moore 算法。课程实验里通常用 Moore 算法就够了先按“终态”和“非终态”分成两个初始等价类然后反复检查每个等价类中的状态如果对某个输入符号它们转移到的目标状态落在不同的等价类中就把这个等价类拆开直到所有等价类都稳定为止。这里最容易翻车的地方是“死状态”的处理。如果 DFA 中存在某些状态对某些输入符号没有定义转移严格来说这不是一个完整的 DFA。常见做法是补一个死状态所有未定义的转移都指向它死状态对所有输入都指向自身。最小化时死状态通常会被单独归为一类最后可以选择保留或删除。实验报告里如果没提这一点代码跑出来的状态数可能和标准答案差一个。2.3 为什么这两步必须放在一起理解单独看子集构造你可能会觉得“不就是把集合当状态吗”单独看最小化你可能会觉得“不就是不断拆分吗”。但真正做实验时你会发现子集构造产生的 DFA 往往包含大量冗余状态如果不做最小化状态转移表又长又难验证。而最小化的正确性又依赖于子集构造输出的 DFA 是确定且完整的。所以这两步是一条流水线NFA →子集构造→ DFA →最小化→ 最小 DFA。实验报告里通常要求画出每一步的状态转移图或转移表这份资源把中间结果也保留下来了方便你对照检查。3. 用 C 把算法跑通数据结构、核心函数与编译命令3.1 状态与转移的存储结构设计先看数据结构。NFA 和 DFA 可以用同一套结构表示区别只在于 NFA 允许一个状态对同一符号有多条出边且允许 ε 边。我一般会这样定义// 自动机状态转移表state - (symbol - set of next states) // 对于 DFA每个 symbol 对应的集合大小最多为 1 struct Automaton { int startState; std::setint acceptStates; // transitions[state][symbol] 目标状态集合 std::mapint, std::mapchar, std::setint transitions; // 对于 NFAsymbol 为 \0 表示 ε 转移 };用std::map而不是固定数组是因为实验中的状态编号和符号集不一定是连续的用映射更省心。acceptStates用std::set是为了后续判断某个 DFA 状态是否包含 NFA 终态时方便做集合交集。3.2 ε-闭包与 move 操作的实现这两个函数是整个子集构造的地基写错了后面全错。ε-闭包用 DFS 或 BFS 都行我习惯用栈来写避免递归深度过大// 计算状态集合的 ε-闭包 std::setint epsilonClosure(const Automaton nfa, const std::setint states) { std::setint closure states; std::stackint worklist; for (int s : states) worklist.push(s); while (!worklist.empty()) { int cur worklist.top(); worklist.pop(); // 查找当前状态的所有 ε 转移 auto it nfa.transitions.find(cur); if (it nfa.transitions.end()) continue; auto epsIt it-second.find(\0); if (epsIt it-second.end()) continue; for (int next : epsIt-second) { if (closure.find(next) closure.end()) { closure.insert(next); worklist.push(next); } } } return closure; } // 计算从状态集合出发经过指定符号能到达的状态集合不包含 ε-闭包 std::setint move(const Automaton nfa, const std::setint states, char symbol) { std::setint result; for (int s : states) { auto it nfa.transitions.find(s); if (it nfa.transitions.end()) continue; auto symIt it-second.find(symbol); if (symIt it-second.end()) continue; result.insert(symIt-second.begin(), symIt-second.end()); } return result; }注意epsilonClosure里对\0的约定这是 NFA 中表示 ε 转移的常见做法。如果你的实验要求用其他符号表示 ε改掉这个字符即可。move函数不负责求闭包闭包在调用处再套一层这样职责清晰调试时也容易单独验证。3.3 子集构造的主循环与状态编号有了上面两个函数子集构造就是一个标准的 BFS 过程// 子集构造NFA - DFA Automaton subsetConstruction(const Automaton nfa, const std::setchar alphabet) { Automaton dfa; std::mapstd::setint, int stateMap; // NFA 状态集合 - DFA 状态编号 std::queuestd::setint workQueue; int nextId 0; // 初始状态NFA 初始状态的 ε-闭包 std::setint startSet epsilonClosure(nfa, {nfa.startState}); stateMap[startSet] nextId; workQueue.push(startSet); dfa.startState 0; while (!workQueue.empty()) { std::setint curSet workQueue.front(); workQueue.pop(); int curId stateMap[curSet]; // 如果当前集合包含 NFA 终态则对应 DFA 状态为终态 for (int s : curSet) { if (nfa.acceptStates.count(s)) { dfa.acceptStates.insert(curId); break; } } for (char sym : alphabet) { std::setint nextSet epsilonClosure(nfa, move(nfa, curSet, sym)); if (nextSet.empty()) continue; // 空集不生成新状态 if (stateMap.find(nextSet) stateMap.end()) { stateMap[nextSet] nextId; workQueue.push(nextSet); } dfa.transitions[curId][sym].insert(stateMap[nextSet]); } } return dfa; }这里有几个参数和逻辑需要说明。alphabet是输入符号集合不包含 ε需要从 NFA 的转移表中提取或手动指定。nextSet.empty()时直接跳过意味着不生成死状态如果你希望生成完整的 DFA可以在这里补一个死状态并统一编号。stateMap用std::setint作为键依赖std::set的字典序比较所以状态集合的插入顺序不影响结果这一点比用std::vector更稳妥。3.4 最小化算法的实现与等价类拆分最小化部分用 Moore 算法核心是维护一个划分partition每个划分是一个状态集合// DFA 最小化Moore 算法 Automaton minimizeDFA(const Automaton dfa, const std::setchar alphabet) { // 初始划分终态集合与非终态集合 std::setint allStates; for (auto p : dfa.transitions) allStates.insert(p.first); allStates.insert(dfa.startState); std::vectorstd::setint partitions; std::setint acceptSet dfa.acceptStates; std::setint nonAcceptSet; for (int s : allStates) { if (!acceptSet.count(s)) nonAcceptSet.insert(s); } if (!acceptSet.empty()) partitions.push_back(acceptSet); if (!nonAcceptSet.empty()) partitions.push_back(nonAcceptSet); bool changed true; while (changed) { changed false; std::vectorstd::setint newPartitions; for (auto group : partitions) { // 按转移目标所在的划分编号对 group 进行细分 std::mapstd::vectorint, std::setint splitter; for (int s : group) { std::vectorint signature; for (char sym : alphabet) { int target -1; auto it dfa.transitions.find(s); if (it ! dfa.transitions.end()) { auto symIt it-second.find(sym); if (symIt ! it-second.end() !symIt-second.empty()) { target *symIt-second.begin(); } } // 找到 target 属于哪个划分 int pid -1; for (size_t i 0; i partitions.size(); i) { if (partitions[i].count(target)) { pid (int)i; break; } } signature.push_back(pid); } splitter[signature].insert(s); } for (auto kv : splitter) { newPartitions.push_back(kv.second); } if (splitter.size() 1) changed true; } partitions newPartitions; } // 根据最终划分构建最小 DFA Automaton minDfa; std::mapint, int stateToPart; for (size_t i 0; i partitions.size(); i) { for (int s : partitions[i]) stateToPart[s] (int)i; } minDfa.startState stateToPart[dfa.startState]; for (size_t i 0; i partitions.size(); i) { for (int s : partitions[i]) { if (dfa.acceptStates.count(s)) { minDfa.acceptStates.insert((int)i); break; } } } for (auto p : dfa.transitions) { int from stateToPart[p.first]; for (auto symPair : p.second) { if (!symPair.second.empty()) { int to stateToPart[*symPair.second.begin()]; minDfa.transitions[from][symPair.first].insert(to); } } } return minDfa; }这段代码里signature是每个状态对字母表中每个符号的转移目标所属划分编号组成的向量。如果两个状态的 signature 不同它们就不等价必须拆开。changed标记控制迭代终止。最后构建最小 DFA 时把同一划分内的状态合并成一个新状态转移目标也映射到划分编号。3.5 编译命令与测试用例把上面的代码放进一个.cpp文件用 g 编译g -stdc17 -O2 -o nfa2dfa nfa2dfa.cpp ./nfa2dfa测试时建议先用一个简单的 NFA比如识别(a|b)*abb的 NFA手动构造好转移表输入程序然后对照教材上的 DFA 状态图检查。如果输出状态数比预期多优先检查 ε-闭包是否递归完整如果最小化后状态数不对检查死状态是否被单独划分。4. 实验报告里不会写但一定会踩的坑排查与避坑清单4.1 状态集合比较时顺序不一致导致重复状态现象子集构造输出的 DFA 状态数比理论值多仔细看转移表发现有两个状态其实是同一个集合只是元素顺序不同。 原因用std::vectorint存状态集合时{1,2}和{2,1}会被当成不同键。 解决统一用std::setint或插入后排序去重确保集合表示唯一。4.2 ε-闭包漏掉自身状态现象初始 DFA 状态不包含 NFA 初始状态本身后续转移全部错位。 原因ε-闭包实现时只遍历了 ε 边到达的状态忘记把起始状态加入闭包。 解决closure初始化时直接包含传入的states再对每个状态展开 ε 边。4.3 最小化时死状态处理不当现象最小化后的 DFA 缺少某些转移或者状态数比标准答案少一个。 原因子集构造时跳过了空集导致 DFA 不完整最小化时又把“无定义转移”和“转移到死状态”混为一谈。 解决要么在子集构造时补死状态要么在最小化前统一补全转移表明确死状态的编号和转移。4.4 字母表提取遗漏符号现象DFA 缺少某些输入符号的转移运行时报错或结果不对。 原因字母表是从 NFA 转移表中提取的如果某个符号只出现在 ε-闭包内部实际上不会或者手动指定时漏了符号就会出问题。 解决遍历 NFA 所有转移的符号排除 ε 后去重作为字母表。不要手动硬编码。4.5 终态判断时集合交集写反现象DFA 的终态集合完全不对识别结果全错。 原因判断 DFA 状态是否为终态时应该检查该状态对应的 NFA 状态集合是否与 NFA 终态集合有交集而不是判断是否包含全部终态。 解决用std::set_intersection或简单遍历只要有一个 NFA 终态在集合里就算终态。5. 进阶验证用最小 DFA 反推正则表达式与自动化测试代码跑通只是第一步真正检验你理解是否到位的方法是拿最小化后的 DFA 去反推正则表达式或者用一组测试字符串验证识别结果。我一般会写一个小型的测试驱动// 用 DFA 识别输入字符串 bool accepts(const Automaton dfa, const std::string input) { int cur dfa.startState; for (char c : input) { auto it dfa.transitions.find(cur); if (it dfa.transitions.end()) return false; auto symIt it-second.find(c); if (symIt it-second.end() || symIt-second.empty()) return false; cur *symIt-second.begin(); } return dfa.acceptStates.count(cur) 0; }然后用几组正例和反例跑一遍比如对(a|b)*abb的最小 DFA测试abb、aabb、babb应该返回 trueab、abba应该返回 false。如果结果不对回到最小化那一步检查等价类划分。另一个进阶技巧是状态编号重排。子集构造产生的 DFA 状态编号是 BFS 顺序最小化后的编号是划分顺序两者都不一定从 0 连续。如果你需要输出成 Graphviz 或教材格式可以在最后加一步重编号让状态从 0 到 n-1 连续排列转移表看起来会清爽很多。还有一个容易被忽略的点最小化后的 DFA 可能包含不可达状态。虽然子集构造从初始状态出发 BFS 不会产生不可达状态但如果你手动修改过转移表或者合并过程中引入了孤立划分最好在输出前做一次可达性分析把从初始状态出发不可达的状态删掉。这一步在实验报告里通常不要求但实际工程中很常见。从那以后我每次做自动机相关的实验都会先把 ε-闭包和 move 两个函数单独写测试用例跑一遍确认无误再往上搭子集构造。这个习惯帮我省下了大量调试时间也让我在给别人讲的时候更有底气。希望帮到你。本文还有配套的精品资源点击获取