★ FEATURED ARTICLE 简介这份资源面向高校「编译原理」课程学习者尤其是ZZU的学弟学妹提供NFA转DFA并最小化实验的完整代码与实验报告帮助解决自动机理论中从非确定有限自动机到确定有限自动机转换及状态最小化的实践难题。压缩包共2个文件包含1个cpp源码和1个doc实验报告整体约722KB源码对应子集构造法与DFA最小化算法的C实现报告则记录实验目的、步骤、问题与解决方案两者配合便于对照理解算法细节。目前已有415人学习下载适合需要完成课程实验、巩固有限自动机知识或锻炼C算法实现能力的读者参考可据此快速搭建实验框架、复盘转换流程并掌握状态合并与冗余消除的排错思路。1. 从状态爆炸到确定化一份编译原理实验的完整落地记录如果你正在学编译原理大概率会在“词法分析”这一章卡住。老师讲子集构造法的时候黑板上画几个圈、连几条线看起来挺清楚但真让你写代码把 NFA 转成 DFA再最小化很多人就不知道从哪下手了。这份实验资源就是干这件事的它包含一套完整的 C 实现能把一个非确定性有限自动机NFA确定化再对生成的 DFA 做最小化最后输出状态转换表。适合正在做编译原理课程实验的同学也适合想补一补自动机理论落地实现的开发者。整个项目不依赖任何第三方库纯 C 手写代码量不大但数据结构设计得比较清晰拿来当模板改一改就能用到自己的实验里。2. 项目结构与环境准备先看清全貌再动手2.1 目录组织与文件职责拿到这份资源第一件事不是急着编译而是把目录结构看一遍。整个项目通常包含这几个部分src/目录核心源码一般拆成nfa.h、dfa.h、subset_construction.cpp、minimize.cpp、main.cpp这几个文件。头文件放数据结构和函数声明cpp 文件放具体实现。data/目录存放输入输出文件。输入是 NFA 的定义输出是 DFA 状态转换表和最小化后的结果。report/目录实验报告包含算法描述、测试用例和运行截图。Makefile或CMakeLists.txt构建脚本用来编译整个项目。这种拆分方式的好处是职责清晰NFA 和 DFA 各自有独立的数据结构子集构造和最小化是两个独立的算法模块main.cpp只负责读输入、调算法、写输出。你如果要改算法只需要动对应的 cpp 文件不会牵一发动全身。2.2 编译环境与构建命令项目用的是标准 C没有外部依赖所以编译很简单。如果你用 Makefile直接在项目根目录执行# 编译整个项目生成可执行文件 nfa2dfa make # 运行程序指定输入文件 ./nfa2dfa data/input.txt如果你用 CMake流程也差不多mkdir build cd build cmake .. make ./nfa2dfa ../data/input.txt这里要注意不同版本的编译器对 C 标准的支持不一样。项目里如果用了unordered_set或者auto这类特性编译时最好加上-stdc11或更高版本。我一般会在 Makefile 里直接写死-stdc17省得换台机器就翻车。2.3 输入文件格式说明输入文件定义了 NFA 的各个要素格式通常是这样的3 0 1 2 a b 0 2 0 a 0 1 0 b 0 1 a 2 2 b 2逐行解释一下第一行是状态总数第二行列出所有状态编号第三行是字母表第四行是初态第五行是终态集合后面每一行是一条转换规则格式是“当前状态 输入符号 下一个状态1 下一个状态2 …”。因为 NFA 的转换可以有多条所以一行里可能有多个目标状态。这个格式不是固定的你可以根据自己的实验要求改。关键是让程序能正确解析后面算法部分不用动。3. 核心算法拆解子集构造法与 DFA 最小化3.1 NFA 与 DFA 的数据结构设计先看 NFA 怎么存。因为 NFA 的转换关系是一对多的所以用map或者unordered_map来存比较自然// nfa.h struct NFA { int stateNum; // 状态总数 vectorint states; // 所有状态 vectorchar alphabet; // 字母表 int startState; // 初态 setint acceptStates; // 终态集合 // 转换函数当前状态 输入符号 - 目标状态集合 mappairint, char, setint transitions; };这里用setint存目标状态自动去重后面做子集构造的时候方便。DFA 的结构类似但转换关系是一对一的// dfa.h struct DFA { int stateNum; vectorint states; vectorchar alphabet; int startState; setint acceptStates; // DFA 转换当前状态 输入符号 - 唯一目标状态 mappairint, char, int transitions; };DFA 里每个状态其实对应 NFA 的一个状态子集所以实际实现的时候通常会给每个 DFA 状态分配一个编号同时用一个mapsetint, int记录子集到编号的映射。这个映射是子集构造法的关键后面会细说。3.2 子集构造法从 NFA 到 DFA 的确定化子集构造法的核心思想是DFA 的每一个状态对应 NFA 中若干个状态的集合。算法从 NFA 的初态闭包开始不断对每个未处理的子集和每个输入符号计算转移后的新子集直到没有新子集产生为止。先看闭包计算。NFA 里如果有 ε 转换需要先求 ε-闭包。这份实验里如果没有 ε 转换闭包就是状态本身。但为了通用性还是写一个闭包函数// 计算状态集合的 ε-闭包 setint epsilonClosure(const NFA nfa, const setint states) { setint closure states; stackint stk; for (int s : states) stk.push(s); while (!stk.empty()) { int cur stk.top(); stk.pop(); // 查找当前状态的所有 ε 转换 auto it nfa.transitions.find({cur, ε}); if (it ! nfa.transitions.end()) { for (int next : it-second) { if (closure.find(next) closure.end()) { closure.insert(next); stk.push(next); } } } } return closure; }这个函数用栈做深度优先遍历把能通过 ε 转换到达的状态全部加进闭包。参数states是初始状态集合返回值是扩展后的闭包集合。接下来是子集构造的主循环// 子集构造法NFA - DFA DFA subsetConstruction(const NFA nfa) { DFA dfa; dfa.alphabet nfa.alphabet; // 子集到 DFA 状态编号的映射 mapsetint, int subsetToId; queuesetint workQueue; // 初始子集NFA 初态的 ε-闭包 setint startSet epsilonClosure(nfa, {nfa.startState}); subsetToId[startSet] 0; workQueue.push(startSet); dfa.startState 0; int nextId 1; while (!workQueue.empty()) { setint curSet workQueue.front(); workQueue.pop(); int curId subsetToId[curSet]; // 如果当前子集包含 NFA 终态则对应 DFA 状态也是终态 for (int s : curSet) { if (nfa.acceptStates.count(s)) { dfa.acceptStates.insert(curId); break; } } // 对每个输入符号计算转移 for (char ch : nfa.alphabet) { setint nextSet; for (int s : curSet) { auto it nfa.transitions.find({s, ch}); if (it ! nfa.transitions.end()) { nextSet.insert(it-second.begin(), it-second.end()); } } if (nextSet.empty()) continue; // 求 ε-闭包 nextSet epsilonClosure(nfa, nextSet); // 如果新子集没出现过分配新编号并入队 if (subsetToId.find(nextSet) subsetToId.end()) { subsetToId[nextSet] nextId; workQueue.push(nextSet); } // 记录 DFA 转换 dfa.transitions[{curId, ch}] subsetToId[nextSet]; } } dfa.stateNum nextId; for (int i 0; i nextId; i) dfa.states.push_back(i); return dfa; }这段代码有几个关键点。第一用queue做广度优先遍历保证每个子集只处理一次。第二subsetToId这个映射既用来判重也用来给新子集分配编号。第三每次计算转移后都要再求一次 ε-闭包因为 NFA 的转换可能经过 ε 到达更多状态。第四终态判断是看子集里有没有 NFA 的终态有的话对应的 DFA 状态就是终态。参数方面nfa是输入的 NFA 对象返回值是构造好的 DFA。整个过程不需要额外配置只要 NFA 数据正确算法就能跑通。3.3 DFA 最小化Hopcroft 算法的简化实现DFA 最小化的目标是合并等价状态让状态数最少。常用的方法是划分法先把状态分成终态和非终态两组然后不断细分直到每个组内的状态都不可区分。先定义两个状态等价的含义对于所有输入符号两个状态转移到的目标状态都在同一个组里。基于这个定义算法流程是初始划分终态集合一组非终态集合一组。对每个组检查组内状态是否对所有输入符号都等价。如果不等价就按转移目标所在的组进行细分。重复步骤 2直到没有组可以再分。每个组选一个代表状态重建 DFA。代码实现// DFA 最小化划分法 DFA minimizeDFA(const DFA dfa) { // 初始划分终态一组非终态一组 vectorsetint partitions; setint acceptSet dfa.acceptStates; setint nonAcceptSet; for (int s : dfa.states) { 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; vectorsetint newPartitions; for (auto group : partitions) { // 按转移目标所在组对当前组进行细分 mapvectorint, setint splitMap; for (int s : group) { vectorint signature; for (char ch : dfa.alphabet) { auto it dfa.transitions.find({s, ch}); int target (it ! dfa.transitions.end()) ? it-second : -1; // 找到 target 所在的组编号 int groupId -1; for (int i 0; i partitions.size(); i) { if (partitions[i].count(target)) { groupId i; break; } } signature.push_back(groupId); } splitMap[signature].insert(s); } if (splitMap.size() 1) changed true; for (auto kv : splitMap) { newPartitions.push_back(kv.second); } } partitions newPartitions; } // 重建 DFA每个划分选一个代表状态 DFA minDfa; minDfa.alphabet dfa.alphabet; mapint, int stateToRep; // 原状态 - 代表状态 int repId 0; for (auto group : partitions) { int rep *group.begin(); for (int s : group) stateToRep[s] repId; if (group.count(dfa.startState)) minDfa.startState repId; for (int s : group) { if (dfa.acceptStates.count(s)) { minDfa.acceptStates.insert(repId); break; } } repId; } minDfa.stateNum repId; for (int i 0; i repId; i) minDfa.states.push_back(i); // 重建转换关系 for (auto kv : dfa.transitions) { int from stateToRep[kv.first.first]; char ch kv.first.second; int to stateToRep[kv.second]; minDfa.transitions[{from, ch}] to; } return minDfa; }这段代码的核心是splitMap它用转移目标的组编号作为签名把组内状态分成若干子组。如果签名相同说明这些状态对所有输入符号的行为一致可以留在同一组。changed标记用来控制循环只要还有组被细分就继续迭代。参数说明dfa是待最小化的 DFA返回值是最小化后的 DFA。注意重建转换关系时要把原状态映射到代表状态这样新 DFA 的转换表才是正确的。4. 避坑与常见问题那些年我踩过的坑4.1 输入解析失败格式对不上现象程序运行后直接报错提示“无法读取状态数”或者“转换规则格式错误”。原因输入文件的格式和程序里parseInput函数的预期不一致。比如状态数后面多了一个空格或者转换规则里用了中文逗号。解决先打开输入文件逐行对照程序里的解析逻辑。我一般会在解析函数里加一行日志把读到的每一行打印出来这样一眼就能看出是哪一行出了问题。另外输入文件最好用纯文本编辑器保存避免编码问题。4.2 子集构造死循环ε-闭包没算对现象程序卡在子集构造阶段一直不输出结果CPU 占用很高。原因ε-闭包函数写错了导致每次计算闭包都得到不同的集合subsetToId里不断有新子集加入队列永远不空。解决检查epsilonClosure函数确保它只做一次深度优先遍历不会重复访问已经处理过的状态。可以在函数里加一个visited集合每次访问新状态前先判断是否已经访问过。另外如果 NFA 里没有 ε 转换闭包函数应该直接返回原集合不要做多余操作。4.3 DFA 最小化结果不对终态判断有误现象最小化后的 DFA 状态数比预期多或者终态集合不对。原因在重建 DFA 的时候终态判断写成了“组内所有状态都是终态”但实际上只要组内有一个终态这个组对应的新状态就是终态。解决检查重建部分的代码终态判断应该是“组内存在终态”而不是“组内全部是终态”。另外初始划分的时候终态和非终态一定要分开否则后面细分会出错。4.4 编译报错C 标准不匹配现象编译时提示unordered_set未定义或者auto类型推导失败。原因编译器默认的 C 标准太低不支持 C11 的特性。解决在 Makefile 或 CMakeLists.txt 里显式指定标准比如-stdc17。如果用的是 IDE在项目设置里找到编译选项把标准调高。4.5 输出结果可读性差状态编号混乱现象输出的 DFA 状态转换表里状态编号是 0、1、2 这种但看不出和 NFA 子集的对应关系。原因程序只输出了 DFA 的编号没有输出每个编号对应的 NFA 子集。解决在输出的时候把subsetToId映射也打印出来这样就能看到每个 DFA 状态对应哪些 NFA 状态。调试的时候特别有用能快速定位问题。5. 二次开发与扩展把这套代码用到自己的实验里5.1 改造输入输出格式如果你老师要求的输入格式和这份资源不一样改起来很简单。找到parseInput函数把解析逻辑改成你需要的格式就行。比如有的实验要求用邻接矩阵表示 NFA那你就把读取部分改成读矩阵然后转换成transitions映射。输出部分同理printDFA函数里改一下打印格式就能输出成老师要求的样子。5.2 增加 ε 转换支持这份资源的代码里已经预留了 ε 转换的处理逻辑但输入文件里可能没有体现。如果你需要支持 ε-NFA只要在输入文件里加上ε符号的转换规则然后在字母表里也加上ε程序就能自动处理。注意 ε 闭包的计算要正确否则子集构造会出问题。5.3 可视化输出如果你想让实验结果更直观可以加一个 Graphviz 输出功能。把 DFA 的状态和转换关系写成 DOT 格式然后用 Graphviz 生成图片。代码不复杂就是在输出的时候多写一个函数// 输出 DFA 的 DOT 格式用于 Graphviz 可视化 void printDot(const DFA dfa, const string filename) { ofstream out(filename); out digraph DFA {\n; out rankdirLR;\n; out start [shapepoint];\n; out start - dfa.startState ;\n; for (int s : dfa.states) { string shape dfa.acceptStates.count(s) ? doublecircle : circle; out s [shape shape ];\n; } for (auto kv : dfa.transitions) { out kv.first.first - kv.second [label\ kv.first.second \];\n; } out }\n; out.close(); }这个函数会生成一个.dot文件然后用dot -Tpng output.dot -o dfa.png就能得到状态图。实验报告里放一张这样的图比纯文字表格好看多了。5.4 验证方法用已知结果反推改完代码之后怎么确认结果是对的我一般会准备几个简单的测试用例手动算一遍预期结果然后和程序输出对比。比如一个只有两个状态的 NFA手动做子集构造看看 DFA 状态数对不对。如果结果一致再换复杂一点的用例。另外最小化之后的 DFA 可以用一个性质来验证对于任意两个状态如果它们不等价那么一定存在某个输入串使得一个状态接受而另一个不接受。写个简单的测试函数就能验证。5.5 性能优化状态数多的时候怎么办如果 NFA 状态数很多子集构造可能会产生大量 DFA 状态内存和速度都会成问题。这时候可以考虑用位集bitset来表示状态集合比setint快很多。另外subsetToId的键可以用哈希值代替减少比较开销。不过对于课程实验来说状态数一般不会太大这些优化不是必须的但了解一下没坏处。从那以后我每次做自动机相关的实验都会先把输入输出格式确认清楚再动手写算法。因为格式不对后面调半天都是白费功夫。希望这份资源能帮你顺利跑通编译原理实验少走点弯路。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
