企业官网建设流程全解析

简介：这是一份针对大学《编译原理》课程的“NFA转DFA并最小化”实验配套资料，适用于需要完成自动机相关实验的计算机专业学生，尤其对郑州大学（ZZU）的学弟学妹更具针对性。资料包含完整的 C++ 实现代码与实验报告：cpp 文件演示了子集构造法转换及 DFA 最小化的核心算法，doc 报告则覆盖实验目的、步骤、问题分析与结果讨论，可直接作为实验参考或模板。压缩包共 2 个文件，大小约 722KB，体量小巧、结构清晰。目前已有 414 人学习/浏览。通过该资源，读者可以快速理解 NFA 到 DFA 转换、不可达状态消除与等价状态合并等关键知识点，同时借鉴一份规范的实验报告写作思路，提升编译原理实践与文档撰写能力。

1. 把 NFA 转成 DFA 并最小化：编译原理实验里最绕不过去的一个坎

编译原理这门课，很多学校都会让学生亲手实现一遍词法分析的前置环节：正则表达式到 NFA，NFA 到 DFA，再对 DFA 做最小化。我最早做这个实验的时候，花在理解子集构造法上的时间比写代码的时间还多——教材上的形式化定义太抽象了，一眼看过去全是集合和闭包的符号推演，根本不知道代码该从哪里下手。后来我把这份代码和实验报告完整地跑了一遍，才意识到这个资源真正值钱的地方在于：它把 ε-闭包的计算、状态集合的编号、DFA 状态转移表的构建、以及最小化时的状态划分迭代都拆成了可以直接运行的 C++ 代码，并且每一步都对应着实验报告里的推导过程。如果你正在应付课程设计，或者想回头补一补自动机这块的基础，这份资源能帮你省掉大量踩坑时间。

2. 子集构造法与 ε-闭包：NFA 转 DFA 的核心实现思路

2.1 NFA 的数据结构设计：状态、边和终结标记怎么存

动手写代码之前，最先要解决的是数据结构。NFA 里有几个核心概念：状态集合、输入符号表、转移函数（一个状态读一个字符可能到达多个状态，也可能读 ε 直接跳转）、起始状态和接受状态。这份资源里用了一种比较直观的做法：用整数给状态编号，转移关系用二维的 vector 存，每个元素是一个 int 集合。

struct NFA { int start; // 起始状态编号 set<int> acceptStates; // 接受状态集合（可能有多个） vector<int> symbolTable; // 输入符号表，0 表示 ε map<pair<int, int>, set<int>> trans; // 转移表：<当前状态, 输入符号> -> 目标状态集合 };

这段代码的逻辑不复杂：trans是一个以<当前状态, 输入符号>为键、以目标状态集合为值的字典。为什么不用vector<vector<set<int>>>？因为 NFA 的转移表往往是稀疏的，很多状态对某些符号根本没有出边，用map可以避免浪费大量内存。symbolTable里把 0 约定为 ε 也是一个常见做法，因为后面算 ε-闭包的时候需要反复判断当前符号是否为 0，用整数比用字符更干净。

这里有个容易踩的细节：NFA 的接受状态不是单点，而是一个集合。很多同学初学时会默认“NFA 只有一个终态”，但实际构造时（比如从正则表达式用 Thompson 构造法）往往会出现多个终态，所以一开始就用set存着，后面转 DFA 时只需要判断“DFA 状态对应的 NFA 状态集合里有没有包含某个 NFA 终态”即可，逻辑上非常顺畅。

2.2 ε-闭包和 move 操作：两个最基础的工具函数

子集构造法其实就两个核心操作：一个是求某个状态集合的 ε-闭包，一个是求某个集合在某个输入符号下的 move 结果。代码里把这两个函数单独拎出来，后面所有逻辑都复用它们，这也是这份代码我觉得最值得学习的地方——不是把子集构造法写成一个巨大的 if-else 嵌套，而是拆成可测试的小函数。

// 计算 [stateSet] 的 ε-闭包：从集合中每个状态出发，把所有能通过 ε 到达的状态都加进来 set<int> epsilonClosure(const NFA& nfa, const set<int>& stateSet) { set<int> closure = stateSet; queue<int> worklist; for (int s : stateSet) worklist.push(s); while (!worklist.empty()) { int cur = worklist.front(); worklist.pop(); // 查所有标号为 0（ε）的转移 auto range = nfa.trans.equal_range({cur, 0}); for (auto it = range.first; it != range.second; ++it) { for (int next : it->second) { if (closure.find(next) == closure.end()) { closure.insert(next); worklist.push(next); } } } } return closure; }

这个实现用的是工作列表算法，本质上是一层 BFS：把初始集合里的状态先放进结果，再逐个检查它们有没有 ε 出边，把新状态加进来并继续扩展。之所以用equal_range而不是trans[{cur, 0}]直接取值，是因为map的operator[]在键不存在时会给插入一个空集合，这会污染数据——写工程代码时这种细节很重要。

move 操作更直白：对集合里每个状态，找到它在某个非 ε 符号下的所有出边目标，所有目标并起来就是结果。注意 move 的结果不需要做 ε-闭包，闭包是在后面调用时另外做的。很多初学版本把这两个步骤混在一起写，导致状态集合多算或少算，最后 DFA 状态表怎么都对不上。

2.3 子集构造主流程：状态集合编号与避免重复计算

有了上面两个函数，DFA 的构建就剩一个骨架：从初始状态集合（NFA 起始状态的 ε-闭包）出发，用一个队列保存待处理状态，对每个待处理状态逐一尝试所有输入符号，算出 move 再求 ε-闭包，得到一个新集合；如果这个集合以前没见过，就分配一个新的 DFA 状态编号。

pair<DFA, vector<set<int>>> subsetConstruction(const NFA& nfa) { DFA dfa; map<set<int>, int> stateToId; // NFA状态集合 -> DFA状态编号 queue<set<int>> pending; // 待处理的 NFA状态集合 set<int> initSet = epsilonClosure(nfa, {nfa.start}); stateToId[initSet] = dfa.start = 0; dfa.states.push_back(initSet); pending.push(initSet); while (!pending.empty()) { set<int> current = pending.front(); pending.pop(); int curId = stateToId[current]; for (int sym : nfa.symbolTable) { if (sym == 0) continue; // ε 不参与 DFA 的转移 set<int> moved = moveSet(nfa, current, sym); set<int> closure = epsilonClosure(nfa, moved); if (closure.empty()) continue; int targetId; if (stateToId.find(closure) == stateToId.end()) { targetId = dfa.states.size(); stateToId[closure] = targetId; dfa.states.push_back(closure); pending.push(closure); // 新状态必须继续展开 } else { targetId = stateToId[closure]; } dfa.trans[{curId, sym}] = targetId; } } // 判断哪些 DFA 状态是接受状态 for (size_t i = 0; i < dfa.states.size(); ++i) { for (int accept : nfa.acceptStates) { if (dfa.states[i].count(accept)) { dfa.acceptStates.insert(i); break; } } } return {dfa, dfa.states}; }

逻辑说明：map<set<int>, int>是子集构造法的核心数据结构，它保证了两个不同的 NFA 状态集合不会拿到同一个 DFA 编号，从而避免了重复计算。pending队列保证算法能遍历到所有从初始集合可达的子集，直到没有新状态产生为止。

参数说明上有两个细节值得留意。第一，symbolTable里包含了 0（ε），主循环里必须continue跳过，否则会把 ε 当作真正的输入符号建出错误的状态转移。第二，dfa.trans里的curId和targetId都是 DFA 状态编号，不是 NFA 状态编号——初学时常在这里把两层编号混用，结果最小化时怎么都分不清哪些状态该合并。

3. DFA 的最小化：划分迭代法与接收状态的初始分组

3.1 为什么不能直接合并“看上去一样”的状态

DFA 最小化这件事，我在做实验时一度觉得很简单：把那些出边完全一样的状态合并不就行了？直到我处理一个含有 8 个状态的 DFA 时发现，按“出边是否一致”合并完以后，原本能接受的语言居然变了——因为我忽略了一个关键条件：最小化必须保证划分后的自动机与原自动机等价，而这个等价性的判定不能只看出边，还要看状态是否可区分。

可区分的定义是：存在某个字符串 w，使得从状态 p 读入 w 后到达接受状态，而从状态 q 读入 w 后到达非接受状态（或反过来）。如果两个状态不可区分，它们才能合并。判断不可区分最常用的办法就是划分迭代法：先把状态集分成“接受状态组”和“非接受状态组”，然后反复检查每组中各个状态在某个符号下的转移目标是否属于同一组，如果不在同一组就拆分。直到连续两轮划分不再变化，就得到最细划分。

3.2 迭代划分的代码实现

下面这份代码是模拟项目 X 里最典型的划分迭代实现（很多教材把它叫填表法，实际上做的是同一件事，只是数据组织方式不同）。这份资源里用的是纯粹的字典分组法，我觉得面试或答辩时讲解起来最直观。

vector<set<int>> minimizeDFA(DFA& dfa, vector<set<int>>& originalSets) { vector<int> groupId(dfa.states.size(), -1); // 初始分组：接受状态一组（组 1），非接受状态一组（组 0） for (int i = 0; i < (int)dfa.states.size(); ++i) { groupId[i] = dfa.acceptStates.count(i) ? 1 : 0; } bool changed = true; while (changed) { changed = false; // 记录每个状态在当前划分下的签名 vector<vector<int>> signatures(dfa.states.size()); map<vector<int>, int> sigToGroup; // 签名 -> 新组编号 int nextGroupId = 0; for (int s = 0; s < (int)dfa.states.size(); ++s) { vector<int> sig; sig.push_back(groupId[s]); // 状态自身的组号作为签名第一元素 for (int sym : dfa.symbolTable) { if (sym == 0) continue; auto it = dfa.trans.find({s, sym}); if (it != dfa.trans.end()) { sig.push_back(groupId[it->second]); // 目标状态所在组号 } else { sig.push_back(-1); // 无转移用 -1 占位 } } signatures[s] = sig; if (sigToGroup.find(sig) == sigToGroup.end()) { sigToGroup[sig] = nextGroupId++; } } // 用新签名更新组号，检查是否发生变化 for (int s = 0; s < (int)dfa.states.size(); ++s) { int newGroup = sigToGroup[signatures[s]]; if (groupId[s] != newGroup) changed = true; groupId[s] = newGroup; } } // 按组号聚合状态 map<int, set<int>> grouped; for (int s = 0; s < (int)dfa.states.size(); ++s) { grouped[groupId[s]].insert(s); } vector<set<int>> result; for (auto& kv : grouped) result.push_back(kv.second); return result; }

逻辑说明：这里每个状态的“签名”由两部分组成——它自己当前所在组的编号，以及它在每个输入符号下转移目标的状态所在组的编号。如果两个状态的签名完全一致，说明在当前划分下它们的“表现”完全相同，可以留在同一组；如果不一样，它们就会分到不同的新组里。迭代到最后，每一组内部的状态都不可区分，此时每组压缩为一个最小化后的 DFA 状态。

参数说明：-1表示某个符号下没有转移，这个占位符很重要——如果一个状态在符号 a 下有出边，另一个没有，两者的签名必然不同，它们就不能合并。这正是“出边不一致不能合并”这个直觉在算法里的正式表达。

3.3 最小化后的状态转移表重建

拿到分组结果之后，还要把最小化 DFA 的状态转移表重新建出来。这个过程实际上是一个“压缩映射”：把原来 DFA 中每个状态映射到它所在组的代表编号，然后将所有转移边按新编号重写。

DFA buildMinimizedDFA(const DFA& oldDFA, const vector<set<int>>& groups) { DFA newDFA; int newStart = -1; map<int, int> oldToNew; // 旧状态编号 -> 新状态编号 for (int g = 0; g < (int)groups.size(); ++g) { int representative = *groups[g].begin(); // 取组内最小状态作为代表 oldToNew[representative] = g; newDFA.states.push_back(groups[g]); if (oldDFA.acceptStates.count(representative)) { newDFA.acceptStates.insert(g); } } newStart = oldToNew[oldDFA.start]; for (auto& edge : oldDFA.trans) { int oldFrom = edge.first.first; int sym = edge.first.second; int oldTo = edge.second; // 映射到新编号 int fromId = oldToNew[oldFrom]; int toId = oldToNew[oldTo]; // 去重：多个旧状态可能映射到同一个新状态 if (newDFA.trans.find({fromId, sym}) == newDFA.trans.end()) { newDFA.trans[{fromId, sym}] = toId; } } newDFA.start = newStart; return newDFA; }

这段代码里有几个值得琢磨的地方。oldToNew只映射每个组的代表状态，而不是组内所有状态——因为组内其他状态不会再出现在最小化 DFA 的转移表里。为什么去重？因为旧 DFA 里可能有两条不同的边(p, a) -> q和(r, a) -> q，其中p和r属于同一组，映射后旧状态会被同一组的代表顶替，如果不判断是否已存在就会覆盖出错。

我在实际帮同学排查代码的时候发现，最常见的问题不是最小化算法本身写错，而是buildMinimizedDFA里忘了处理“组内多个状态对同一符号有出边”的情况。比如组内有状态 2 和 3，2 在符号 a 下跳到状态 5，3 在符号 a 下跳到状态 7，而 5 和 7 恰好也在同一组——理论上这两个转移在最小化后应该变成同一条边，但如果代码不加判断直接赋值，后写的边会把前写的覆盖掉，造成转移表缺失。

4. 实验报告的组织：从输入样例到转移表再到等价性验证

4.1 实验报告中需要覆盖的关键内容

很多同学拿到代码以后只想着跑通，却忽视了实验报告本身也是这份资源的重要组成部分。我翻了这份报告的结构，发现它对“怎么把代码结果组织成一份能拿高分的报告”这件事想得很清楚：先交代实验目的和输入输出形式，再描述数据结构设计和核心算法流程，最后给出一个完整的运行样例以及多组测试结果。这三层结构缺一不可——第一层说明你做的是什么，第二层说明你是怎么做的，第三层证明你做的结果是对的。

报告中用了一个非常典型的三状态 NFA 作为样例输入，我记不清具体状态数量了，但它覆盖了 ε 转移、多出边和多个接受状态这些常见特征。这些特征如果没有全部走一遍，你的程序很容易在看似简单的例子上通过，一换输入就翻车。

4.2 用表格呈现转换过程和最小化迭代

我认为实验报告里最有说服力的部分是那张 DFA 状态转移表，以及最小化过程中的划分迭代表。这类表格用 Word 里简单的三线表就能做出来，但内容上要遵循以下形式：

最小化划分迭代也可以用表格记录每一轮分组情况：

我看到这份报告里把最小化的每一轮划分都画出来了，这一点非常值得学习。因为在答辩时老师最常问的问题就是“你的最小化为什么会在这一轮停下来”“这两轮之间划分变化了什么”，如果你只贴最终分组结果，根本答不上来；但有了迭代表，就能指着每一轮说清楚哪个状态因为转移目标不在同一组而发生了分裂。

4.3 等价性验证：用几组正反测试用例证明正确性

光有转换表和迭代表还不够，报告的最后通常要放几组测试用例。这几组用例不能只给输入和输出，还应该说明“预期是什么，实际得到什么，两者是否一致”。我一般会这样组织测试部分：

• 第一组：一个能被接受的字符串（比如ab），验证 DFA 运行在接收状态
• 第二组：一个不能被接受的字符串（比如ba），验证 DFA 停在非接收状态
• 第三组：一个空字符串，验证起始状态是否也是接受状态（如果语言包含空串的话）

这三组用例分别对应了 DFA 模拟的三种边界情况。第一组和第二组验证了基础的正确性，第三组验证起始状态的特殊处理——因为最小化以后起始状态的组号可能变了，空串是否被接受取决于新起始状态是否在最小化 DFA 的接受状态集合里，这是最容易出错的地方。

5. 避坑指南：NFA 转 DFA 实验最容易翻车的四个地方

5.1 现象：DFA 状态数无限增长，程序陷入死循环

第一次跑这个实验的同学经常会遇到一个诡异情况：程序运行了很久也不停止，状态数一个接一个地冒出来。我排查过的一个案例里，同学构造了一个含有 ε 环的 NFA（比如状态 0 读到 ε 能回到状态 0 自己），然后子集构造法的 epsilonClosure 里没有判断“这个状态是否已经在 closure 集合中”就直接入队，结果同一个状态被反复处理，闭包永远算不完。

原因也很简单：工作列表算法依赖“已访问集合”来保证终止，而 ε 环会让一个状态从多个路径到达，如果不查重，它就会被无限地重新加入队列。解决方法是参考 2.2 的代码——在插入 closure 之前先检查closure.find(next) == closure.end()，没有查重逻辑的闭包计算无论如何都是有 bug 的。

5.2 现象：最小化后接受状态和非接受状态被合并了

这是一个“看似不可能但就是会发生”的错误。有一次我帮某同学检查最小化代码，发现他把初始分组写成了“所有状态一组”，而不是分成接受组和非接受组。这样一来状态 0（非接受）和状态 4（接受）只要出边相似就会合并到一起，最终得到的最小化 DFA 和原 DFA 不等价。

原因是划分迭代法必须从“接受状态 vs 非接受状态”这个初始划分开始，如果一开始就把所有状态放进同一个组，算法永远不可能再拆分出这个区别，因为签名里只包含组号和出边目标组号，而这两个信息在无区分的初始分组中看不出任何差异。解决方法是先执行一次强制性分组：接受状态组编号为 1，非接受状态组编号为 0，然后再进入迭代。这和我在 3.2 的代码里写的groupId初始化方式一致。

5.3 现象：状态转移表里出现“指向空集”的边

NFA 转 DFA 时，某个状态集合在读入某个符号后可能没有可到达的状态，也就是 move 结果为空集。很多同学的代码在这种情况下会往 DFA 转移表里写一个targetId = -1或者直接跳过。如果把-1写进转移表，后面模拟 DFA 读字符串时就会去访问trans[{-1, sym}]，轻则返回错误结果，重则数组越界崩溃。

正确处理是像 2.3 代码里那样：if (closure.empty()) continue;——空集不构成新的 DFA 状态，也不产生转移边。DFA 的定义要求每个状态对每个输入符号有且仅有一个转移，但“没有转移”在实际实现中通常等价于“进入一个死状态”，而死状态在最小化过程中会被当作战术状态处理，可以不显式地画出。

5.4 现象：实验报告上的状态编号和代码输出对不上

这个坑不在代码逻辑，而在演示环节。做过答辩的同学都知道，老师会让你现场跑一个输入，然后对照实验报告里的状态转移表去验证。如果你在报告里手工推演时用了 A、B、C 这样的状态命名，而代码输出的是 0、1、2、3，老师一眼就能看出你报告里贴的状态数和实际输出不一致，这在成绩评定上会明显减分。

解决方法是从一开始就让代码输出的编号同步到报告写作：代码里stateToId全局使用整数，报告的表格也按“状态 0 = NFA 集合 {…}”来写，不要另起一套命名。这份资源里的实验报告就是直接截图代码运行结果再配旁注的，这种形式最稳妥——即使编号顺序和你自己推导时的顺序不同，只要旁边的 NFA 集合说明清楚，老师一看就明白了。

6. 用随机生成的 NFA 做大规模验证：比手算用例高效得多

手动验证三个状态的 NFA 容易，但代码拿去给老师检查时，往往会被要求现场跑一个比教材复杂得多的例子。我后来养成的一个习惯是写一个随机 NFA 生成器，用程序自动检查转换和最小化是否正确，并且每次调试完都强制走一遍这个流程。生成器的思路不复杂：随机生成 5 到 10 个状态，随机选一组状态作为接受状态，随机给状态对之间添加转移边，其中有 15% 的概率把边标成 ε。然后用同一个运行器分别喂给原 DFA 和最小化后的 DFA，比较若干个随机字符串的输出是否一致。

NFA generateRandomNFA(int numStates, int numSymbols, unsigned seed) { mt19937 rng(seed); NFA nfa; for (int i = 0; i < numStates; ++i) { nfa.symbolTable.push_back(i + 1); // 符号从 1 开始，0 留作 ε } // 为了测 ε 闭包，固定加入两条 ε 边 for (int i = 0; i < numStates; ++i) { int from = rng() % numStates; int to = rng() % numStates; nfa.trans[{from, 0}].insert(to); } // 随机加非 ε 边 for (int from = 0; from < numStates; ++from) { for (int sym = 1; sym <= numSymbols; ++sym) { if (rng() % 100 < 30) { int to = rng() % numStates; nfa.trans[{from, sym}].insert(to); } } } nfa.start = 0; nfa.acceptStates.insert(numStates - 1); return nfa; }

这段生成器的代码有几个设计点值得说明。符号表从 1 开始，把 0 预留给 ε，这是整个实验代码里反复出现的约定。固定加入两条 ε 边是为了确保 ε-闭包的计算不会因为“没有 ε 边”而偷懒跳过——很多 bug 只在 ε 转移出现时才暴露，随机生成时不能靠运气。接受状态只设一个，是为了后续验证方便：只检查最小化后的 DFA 在某个字符串上是否接受即可，不需要处理多终态的复杂判定。

验证用字符串的长度可以从 0 测到 6，因为语言是否等价在短字符串上最容易暴露差异。如果原 DFA 和最小化后的 DFA 对 0 到 6 长度的所有字符串判定结果都一致，基本可以认为两个自动机在短前缀上等价；如果这时候还出现不一致，往往是分组时把接受和非接受状态混到了一起，直接回到 5.2 的排查步骤。

从那以后我每次改完子集构造法的代码，都会强制用随机生成器跑一轮 500 组 NFA 的等价性测试，再把代表性的一组成果放进实验报告的附录里。这样做既能提前把 bug 全部消灭在提交之前，也能在答辩时拿出“生成 500 组随机 NFA 全部通过验证”这种硬核数据，比任何口头解释都有说服力。希望这份资源能帮你少走一些弯路，把时间和精力留给真正需要思考的部分。

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