企业官网建设流程全解析

简介：面向编译原理课程核心实验的配套资源，内容紧扣“NFA转DFA并最小化”这一经典专题，适合计算机专业本科生、正在完成课程设计或需要夯实自动机理论的学习者。资源来自郑州大学编译原理课程实践，压缩包内共2个文件：一个C++源码文件和一个Word实验报告，整体仅722KB。C++代码基于子集构造法实现非确定有限自动机（NFA）到确定有限自动机（DFA）的转换，并通过合并等价状态完成DFA最小化，代码结构清晰，便于直接运行和二次修改；实验报告则完整记录了实验目的、实现步骤、算法思路、调试中遇到的问题及对应解决方案，可作为撰写实验报告的参考模板。目前已有413人学习，适合正在做同类实验的学生快速理解转换与最小化的核心流程，同时规范自己的实验材料。

1. 编译原理实验里，NFA 转 DFA 并最小化到底难在哪

这张实验卡住过很多次：子集构造法听得懂，一上手写ε-closure就把“状态自身”漏了；DFA 能转出来，最小化却不知道从哪切；实验报告里贴一张转移表，老师一问“你最小化之后状态数为什么不是最优”就说不清楚。这套 C++ 代码把 NFA 的数据结构、子集构造、分割法最小化和等价性校验串成一条完整链路，输入一份 NFA 转移表，直接输出最少状态数 DFA。适合正在做郑大《编译原理》实验、或者想抄一份能过验收的完整实现的从业者。你可以照着改自己的 NFA，也可以直接拿报告模板改图改表格。

2. 子集构造法：从 ε 闭包到 DFA 转移表的 C++ 实现

2.1 数据结构先立住，后面才不返工

我写这个实验的第一版代码，把 NFA 转移表简单存成vector<vector<int>>，结果每个字符对应的目标状态全挤在一起，后面move函数写得又臭又长。后来改成“状态用 int，转移用 set 和 map”，整套逻辑清爽很多。

#include <bits/stdc++.h> using namespace std; struct NFA { int start; // NFA 初态 vector<set<int>> eps; // eps[i]：从 i 走 ε 直接到的状态集合 vector<map<char, set<int>>> trans; // trans[i][ch]：从 i 读 ch 到的状态集合 set<int> accept; // NFA 接受状态集合 }; struct DFA { int start = 0; vector<char> alphabet; // 字母表，按下标顺序展开 vector<vector<int>> trans; // trans[state][ch_index]，-1 表示无转移 vector<bool> accept; // 与 trans 下标一一对应 };

NFA 的转移从“单个状态”变成“集合”，是因为同一个字符可以有多个目标状态。用set有两个好处：去重是自动的，后面子集构造里要求两个集合的并集时，直接insert就行。DFA 的转移天然是单值，所以存成vector<vector<int>>，每一行对应一个 DFA 状态，每一列对应字母表里的一个字符。

这里有个容易忽略的点：DFA.trans里我用-1表示“没有该字符的转移”。很多教材把这种情况画成指向“死状态”，但实验代码里用-1更省事，最小化时也容易处理。后面第 4 章我会专门说死状态补全的问题。

2.2 ε 闭包和 move 两个函数，是整个子集构造的心脏

子集构造法的标准步骤是：先算初态的 ε 闭包作为 DFA 初态；然后对每个 DFA 状态，对每个字符执行“先 move 再求闭包”。顺序不能反。

set<int> epsilonClosure(const NFA& nfa, const set<int>& S) { set<int> res = S; // 注意：先把状态自身放进去，这是最常见的坑 vector<int> stack(S.begin(), S.end()); while (!stack.empty()) { int u = stack.back(); stack.pop_back(); for (int v : nfa.eps[u]) { if (res.insert(v).second) { stack.push_back(v); } } } return res; } set<int> moveAndClose(const NFA& nfa, const set<int>& S, char ch) { set<int> target; for (int u : S) { auto it = nfa.trans[u].find(ch); if (it != nfa.trans[u].end()) { for (int v : it->second) target.insert(v); } } return epsilonClosure(nfa, target); }

epsilonClosure我用栈模拟 DFS，而不是写递归。因为 NFA 状态一多，递归深度可能撞上栈上限，实验环境里 g++ 默认栈大小往往不够。res.insert(v).second这一句是“插进去了吗”的意思，只有新状态才会继续往下推，避免环状 ε 转移死循环。

moveAndClose里有一个关键认知：参数S必须是“已经闭包”的状态集合。它只在 NFA 转移表里找字符ch的直接后继，再对新目标集合做一次闭包。如果你把闭包放在 move 前，结果其实一样，但后面状态集合会变小，逻辑上不统一。我习惯固定写“先 move 再 close”，这样实验报告里描述算法也更顺。

2.3 主循环：用 vector 做队列，避免迭代器失效

子集构造的经典写法是“worklist”：把新出现的状态集合编号，放进队列，不断取队首处理。很多同学用unordered_map<set<int>, int>，但 C++ 标准库没有默认的set<int>哈希函数，编译会报错。我直接用map<set<int>, int>，实验数据量下性能完全够。

DFA subsetConstruction(const NFA& nfa) { DFA dfa; for (const auto& mp : nfa.trans) { for (const auto& pr : mp) { if (find(dfa.alphabet.begin(), dfa.alphabet.end(), pr.first) == dfa.alphabet.end()) { dfa.alphabet.push_back(pr.first); } } } map<set<int>, int> id; vector<set<int>> all; auto addState = [&](const set<int>& s) { if (id.count(s)) return; int idx = (int)all.size(); id[s] = idx; all.push_back(s); dfa.trans.emplace_back(dfa.alphabet.size(), -1); dfa.accept.push_back(false); }; set<int> startClosure = epsilonClosure(nfa, {nfa.start}); addState(startClosure); dfa.start = id[startClosure]; for (int cur = 0; cur < (int)all.size(); ++cur) { for (int a = 0; a < (int)dfa.alphabet.size(); ++a) { set<int> ns = moveAndClose(nfa, all[cur], dfa.alphabet[a]); if (ns.empty()) continue; // 没有转移就保持 -1 addState(ns); dfa.trans[cur][a] = id[ns]; } } for (int i = 0; i < (int)all.size(); ++i) { for (int s : all[i]) { if (nfa.accept.count(s)) dfa.accept[i] = true; } } return dfa; }

主循环用for而不是while + queue的原因是：all在循环里会不断增长，cur < all.size()会让新加入的状态也被依次处理，这就天然实现了 worklist。注意addState里把新状态同时 push 进all、dfa.trans、dfa.accept三个容器，顺序必须一致，否则下标就错位了。

接受状态的判断放在最后统一做：只要子集里任意一个 NFA 状态是接受状态，这个 DFA 状态就是接受状态。这比在构造时单独判断更不容易漏。

举个例子，NFA 有 3 个状态：

接受状态是 2。子集构造结果如下：

这个例子很简单，但足够验证epsilonClosure和moveAndClose是否写对。你跑完这个样例再上实验用例，能省很多排查时间。

3. 分割法最小化：让 DFA 状态数真正压到最少

3.1 为什么我选分割法而不是填表法

填表法（可区分状态表）时间复杂度 O(n²)，思路直观，但代码要把所有状态对都枚举一遍，还要反复扫描字母表。分割法也差不多，但实现上更贴近“不可区分状态合并”的直觉：先分成接受和非接受两大组，再按“读入每个字符后进入哪个组”不断切分，直到任何一组都不能再分。

实验里状态数一般不超过几十个，两种方法都能过。我选分割法还有一个原因：它最后产生的分组，可以直接映射成最小化 DFA 的状态，报告里写“第 i 组合并为新状态 i”非常自然。填表法虽然能判断哪些状态等价，但要从等价关系重新构图，多一步。

下面用一个含 3 个状态的 DFA 做演示：

这个 DFA 接受“以 b 结尾的字符串”，状态 1 和 2 都接受，而且读a都去 0，读b都在接受组内部互相转，所以它们等价，最后应该合并成一个状态。

3.2 分割主循环代码，一轮一轮切到不动为止

分割迭代的核心是：对每个状态算一个“签名”，签名由两部分组成——当前状态属于哪个组，以及读入每个字母后落到的组编号。签名相同就留在同一组，签名不同就拆开。

bool splitOnce(const DFA& dfa, vector<vector<int>>& groups) { int A = (int)dfa.alphabet.size(); vector<int> gid((int)dfa.trans.size(), -1); for (int i = 0; i < (int)groups.size(); ++i) { for (int s : groups[i]) gid[s] = i; } vector<vector<int>> next; bool changed = false; for (const auto& group : groups) { map<vector<int>, vector<int>> buckets; for (int s : group) { vector<int> key; key.push_back(gid[s]); // 先把当前组 id 放进去 for (int a = 0; a < A; ++a) { int t = dfa.trans[s][a]; key.push_back(t == -1 ? -1 : gid[t]); } buckets[key].push_back(s); } for (auto& kv : buckets) { next.push_back(kv.second); if ((int)kv.second.size() < (int)group.size()) { changed = true; // 只要有一个组被拆开，就继续 } } } groups.swap(next); return changed; }

这里key.push_back(gid[s])是我个人的一个保险。因为buckets本来就是按组单独开的，不同旧组不会混，但加上它以后，即使以后改成全局 scan 的写法也不会出问题。t == -1 ? -1 : gid[t]处理缺失转移：无转移和进入任何状态都不同，把它当独立签名值看待，等价类就不会错判。

3.3 主函数：初始化划分、循环、重建新 DFA

分割法的主函数很固定：先把所有非接受状态放进一组，接受状态放进另一组；然后反复splitOnce；最后从每个组挑一个代表状态，重建转移表和接受状态数组。

DFA minimizeDFA(const DFA& dfa) { int n = (int)dfa.trans.size(); vector<vector<int>> groups; vector<int> reject, accept; for (int i = 0; i < n; ++i) { (dfa.accept[i] ? accept : reject).push_back(i); } if (!reject.empty()) groups.push_back(reject); if (!accept.empty()) groups.push_back(accept); while (splitOnce(dfa, groups)) {} vector<int> gid(n, 0); for (int i = 0; i < (int)groups.size(); ++i) { for (int s : groups[i]) gid[s] = i; } DFA minDfa; minDfa.alphabet = dfa.alphabet; minDfa.start = gid[dfa.start]; minDfa.accept.resize(groups.size(), false); minDfa.trans.assign(groups.size(), vector<int>((int)dfa.alphabet.size(), -1)); for (int g = 0; g < (int)groups.size(); ++g) { int rep = groups[g][0]; minDfa.accept[g] = dfa.accept[rep]; for (int a = 0; a < (int)dfa.alphabet.size(); ++a) { int t = dfa.trans[rep][a]; minDfa.trans[g][a] = (t == -1 ? -1 : gid[t]); } } return minDfa; }

用groups[g][0]当代表状态是安全的，因为迭代结束时，同一组内所有状态对每个字符的目标组编号一致，随便挑谁结果都一样。但如果你自己改了初始划分，比如接受、非接受混在一起了，这里就会出问题，第 4 章我会写这条坑。

上面那个 3 状态 DFA 跑完，初始分组是{0}和{1,2}。第一轮迭代，状态 1 和 2 的签名都是当前组 1 + a 去组 0 + b 去组 1，所以不拆。最终分组不变，最小化 DFA 只有两个状态：{0}和{1,2}。转移表变成：{0}读a回{0}，读b去{1,2}；{1,2}读a去{0}，读b留自己。状态数从 3 压到 2，和肉眼判断一致。

4. 避坑与常见问题：五个让我实验报告扣分的细节

4.1 ε 闭包把状态自身漏了

现象：子集构造出来的 DFA 状态编号从 1 开始，0 号状态像个空壳，所有转移都比预期少一个状态。你检查代码，epsilonClosure明明写了迭代，可就是不对。

原因：最常见的是把闭包的初始集合写成set<int> res;，然后只从S里找 ε 目标状态加进去。这样一来，状态自身没有进入结果集。NFA 里 0 没有 ε 转移时，闭包就空了，子集构造直接出错。

解决：严格按定义来，闭包结果集等于“给定集合 ∪ 从其中任意状态经 ε 能到达的所有状态”。代码里先set<int> res = S;，再去迭代，一行都不能省。

4.2 最小化 key 里没放当前组 id，导致状态越拆越多

现象：最小化函数跑完，状态数不减反增，或者在某些输入下死循环。

原因：分割法的“签名”必须保证不同旧组的状态不会被合并。如果你只把“读字符后落入的目标组编号”当 key，而没放当前状态所属组，可能会把两个本来该分开的组重新拉到同一个新桶里。下一轮迭代时又拆，形成震荡。

解决：每个 key 第一项先放gid[s]，然后再放各字符的目标组编号。这样两个状态只有“本来就同组”才可能进一步比较。这也是我写splitOnce时特意保留那行的原因。

4.3 把空集合也当成一个 DFA 状态加进去

现象：DFA 输出里突然多出一个“空状态”，所有转移都指过去，接受状态上乱七八糟。

原因：子集构造里，moveAndClose可能返回空集合，表示当前状态读某个字符没有路径。很多同学想偷懒，直接把空集合也 add 进去，编号当成真实状态。结果转移表里全是指向这个空状态的边，最小化时它还会参与分组，把结论搅浑。

解决：if (ns.empty()) continue;，这个我在 2.3 的代码里留过注释。缺失转移就用-1标记，不要造一个空集合状态。

4.4 死状态要不要补全，和实验报告打架

现象：自己程序跑出来转移表只有 2 行，老师给的参考答案转移表有 3 行，多了一个“死状态”。你拿样例对拍，怎么都不一致。

原因：子集构造默认不产生不可达状态，但很多教材为了方便画图，会显式补一个死状态，把所有缺失边都指向它。两种描述方式接受语言完全一样，但转移表形式不同。郑大实验报告一般要求贴完整 DFA，包括死状态，所以代码里要能切换。

解决：我一般给 DFA 加一个bool addDeadState参数。转出来之后，把所有-1的格子指向新状态n，trans[n][a] = n，accept[n] = false。最小化前如果内存充足也不急着删，反正死状态和无转移在算法里等价；但报告里两种格式要写清楚，别一张表里混用。

4.5 最小化后重建接受状态，只看了代表状态

现象：最小化后的 DFA 接受状态数量比原来少，或者某个接受状态变成非接受。

原因：重建时用minDfa.accept[g] = dfa.accept[rep];，如果初始分组没把接受和非接受严格分开，组里混了两种状态，代表状态是接受就把整组标成接受，代表状态非接受就把整组标成非接受。更隐蔽的是，有些同学在splitOnce里把 group 的划分破坏掉了。

解决：最小化之前先按接受状态粗暴分组，这个不能省。重建时最好加一个断言：遍历整个组，确认组内所有状态接受性一致。如果有不一致，一定是 splitOnce 的签名算错，别急着看别名，先查转移矩阵。

5. 最后一道保险：用积自动机校验最小化 DFA 等价性

5.1 积自动机对拍原理

最小化算法写完，光看状态数变少不够。状态数对，不代表语言没变。最稳妥的办法是构造两个 DFA 的积自动机：从两组初态开始，同步读每一个符号，同时看接受状态是否一致。如果 BFS 过程中发现某一对状态一个接受一个不接受，说明两个 DFA 接受的语言不一样；如果所有可达状态对都一致，就说明等价性成立。

这种方法比随机生成字符串再试靠谱。随机字符串只能证明“没找到反例”，积自动机 BFS 是严格证明“不存在反例”。

5.2 一个可以直接塞进 main 里的等价性校验函数

bool sameLanguage(const DFA& a, const DFA& b) { set<pair<int, int>> vis; queue<pair<int, int>> q; q.push({a.start, b.start}); vis.insert({a.start, b.start}); auto isAccept = [&](const DFA& d, int s) { return s != -1 && d.accept[s]; }; while (!q.empty()) { auto up = q.front(); q.pop(); int sa = up.first, sb = up.second; if (isAccept(a, sa) != isAccept(b, sb)) return false; for (int i = 0; i < (int)a.alphabet.size(); ++i) { int na = (sa == -1 || a.trans[sa][i] == -1) ? -1 : a.trans[sa][i]; int nb = (sb == -1 || b.trans[sb][i] == -1) ? -1 : b.trans[sb][i]; if (vis.insert({na, nb}).second) { q.push({na, nb}); } } } return true; }

这个函数把-1当作统一的拒收死状态：从-1出发再怎么读都还在-1，而且不接受。所以原始 DFA 若显式带死状态，最小化后没带，也能正确判断等价。注意两个 DFA 的字母表顺序必须一致，我一般在minimizeDFA里直接复制dfa.alphabet，保证不会错位。

把 2.3 节那个子集构造结果和 3.3 节最小化结果都塞进去，输出true，再跑一遍课程给的随机样例，基本就能放心写实验报告了。从那以后，我每次提交最小化代码之前，都会强制走一遍积自动机对拍，哪怕状态数只有两三个，也比肉眼盯着转移表靠谱得多。希望你也能少交几次返工版本，希望帮到你。

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