企业官网建设流程全解析

简介：这组资源来自编译原理课程中“NFA转DFA并最小化”实验，适合高校计算机专业学生完成课内实验或复习自动机理论时参考，郑州大学相关课程的同学可直接选用。资源以C++实现子集构造法完成NFA到DFA的转换，并通过合并等价状态实现DFA最小化，可帮助理解编译器前端的词法分析原理。包内含2个文件，1份doc实验报告和1份cpp源代码，压缩包大小约722KB，内容覆盖实验目的、步骤、核心算法思路及问题排查过程。报告中还结合具体案例说明了可达状态处理与等价状态判定细节，适合对照代码逐行梳理实现逻辑。当前已有415人学习下载，属于小而精的课设型资源，可直接运行并依据自身实验要求做少量扩展。

1. 编译原理实验里最折磨人的一步：用这份C++工程把NFA转DFA并最小化一次跑通

期末做编译原理实验，最折磨人的不是写词法分析，而是对着状态转换图手工推导NFA转DFA：一个带 ε 边的小例子，子集构造法推完状态就有八九个，再做最小化分组，笔误几乎不可避免。这份标题为“NFA转DFA并最小化，代码+实验报告”的C++工程，就是用来终结这种手算痛苦的。它把 ε-闭包、move 操作、子集构造法、DFA划分最小化全部做成了一段能直接编译运行的代码，输入NFA的描述文件，终端就会输出每个 DFA 状态对应的 NFA 状态集合，以及最终最小化之后的迁移表。适合正在赶编译原理大作业、想对照实验报告快速验证自己推导结果的同学，也适合想把自动机转换链路当模板复用的开发者。

2. 整体设计与数据结构：用C++把NFA状态集合、迁移表、划分组建模成什么样

2.1 实验目标与输入输出约定：NFA怎么描述，DFA怎么输出

这份实验代码解决的是编译原理前端的经典问题：给定一个不确定有穷自动机 NFA，求一个与之等价且状态数最少的确定有穷自动机 DFA。课程教材里通常把流程分成两步，第一步用子集构造法去 ε，第二步用等价类划分做最小化。代码里的处理顺序也是这两步，先得到没有 ε 边的 DFA，再对 DFA 状态分组，把同组状态合并成最小化 DFA。

输入格式是这份资源里比较关键的约定。常见的做法是让程序从命令行读一个文本文件，文件内容按固定规则描述 NFA。我一般会把格式定义成下面这个样子：

• 第一行：状态总数、字母表大小、字母表字符，用空格分隔；
• 第二行：NFA 初态编号；
• 第三行：终态数量及所有终态编号；
• 之后 N 行：每行描述一个状态的迁移，格式为“状态编号 迁移条数 符号 目标状态1 目标状态2 ...”。

epsilon 边在输入里用#占位，因为直接输入 ε 字符在终端和文件里都容易出乱码。输出则分成三段：第一段是子集构造得到的每个 DFA 状态，用花括号打印其对应的 NFA 状态集合；第二段是 DFA 迁移表；第三段是经过最小化后的等价类编号和迁移表，这样正好可以贴进实验报告的结果对比部分。

2.2 数据结构设计：用vector<map<char, vector<int>>>建模NFA迁移

NFA 和 DFA 看起来都是状态图，但数据结构上差别不小。NFA 的一个状态在一个输入符号下可能迁到多个状态，还可能存在 epsilon 迁移，所以不能用一个int当目标。这份代码里，NFA 迁移表用的是嵌套容器：

// nfaTrans[状态编号][输入符号] = 目标状态列表 vector<map<char, vector<int>>> nfaTrans; int stateCount; // NFA 总状态数 char epsilon = '#'; // 输入文件里用 # 代替 ε set<char> sigma; // 字母表 int startState; // NFA 初态 set<int> acceptStates; // NFA 终态集合

外层 vector 的下标就是 NFA 状态编号，内层 map 的 key 是输入符号，value 是目标状态数组。用map而不是vector<char>是为了让符号表可以任意扩展，输入字母表是a b c还是0 1都不用改代码。接受状态用set<int>存，后面判断“DFA 状态是否为终态”时，只需要检查交集是否为空。

DFA 一侧的结构更直白：DFA 的每个状态本质上是一个 NFA 状态集合，所以用一个vector<set<int>>保存所有 DFA 状态，再用一个vector<map<char, int>>保存迁移。这个vector的下标就是 DFA 状态编号，map的 key 是符号，value 是转移到的 DFA 状态编号。对比之下，NFA 的迁移目标是多个，DFA 的迁移目标是唯一一个，这个差别直接反映在容器类型上。

vector<set<int>> dfaStates; // 每个 DFA 状态对应的 NFA 状态集合 vector<map<char, int>> dfaTrans; // DFA 迁移表：编号 -> (符号 -> 编号) vector<bool> dfaAccept; // DFA 终态标记，和 dfaStates 对齐

最小化阶段的数据结构则是groups和stateGroup两个。groups是一个vector<vector<int>>，代表当前划分出的全部等价类；stateGroup是一个vector<int>，数组下标是 DFA 状态编号，值是该状态所属的组号。实际编码的时候，用map<vector<int>, int>做分桶是整段代码里最容易卡住的地方，后面第 3 章会逐行讲。

2.3 模块划分：一份C++工程该拆成几个函数

拿到压缩包解压后，核心就是一份 C++ 源文件加一份实验报告。源文件没有拆成多个.h和.cpp，这是课程实验里的常见做法——单文件编译、单文件交付，避免交叉引用带来的编译问题。功能上按流程拆成几个独立函数，每个函数都能单独打印中间结果调试：

这种拆法最大的好处是：哪一步结果不对，就在哪个函数里加一行打印，不用从头开始查。实验报告里对每个函数都有对应的算法描述和复杂度分析，子集构造最坏情况下会产生指数级状态，最小化部分用的是反复划分细化的思路，实现简单且适合在报告里展示。

3. 核心算法拆解：ε-闭包、move操作、子集构造法、划分最小化的逐段实现

3.1 两个基础函数：ε-闭包和move操作

NFA 转 DFA 的根基就是两个操作：ε-闭包和 move。闭包是“从当前状态出发，只走 ε 边能到达的所有状态”，move 是“从当前状态集合出发，走一条指定符号边能到达的所有状态”。很多同学写出来的 DFA 状态缺一截，问题基本都出在闭包实现漏掉了“闭包的闭包”。

单个状态的 ε-闭包用广度优先遍历写起来最稳：

vector<int> epsilonClosureOne(int s, const vector<map<char, vector<int>>>& nfaTrans) { vector<bool> visited(nfaTrans.size(), false); queue<int> work; vector<int> closure; work.push(s); visited[s] = true; while (!work.empty()) { int cur = work.front(); work.pop(); closure.push_back(cur); // 如果当前状态存在 epsilon 迁移，就把目标继续入队 auto it = nfaTrans[cur].find('#'); if (it != nfaTrans[cur].end()) { for (int next : it->second) { if (!visited[next]) { visited[next] = true; work.push(next); } } } } return closure; }

这个函数最关键的一点是用visited数组防重复入队。NFA 的 ε 边可能成环，比如状态 1 能 ε 到状态 2、状态 2 又能 ε 回状态 1，如果不用visited，队列永远清不空。closure里保存的顺序不是重点，后面集合比较时统一排序即可。

对状态集合求闭包时，不要一个个状态分别求再合并，那样会多出不少重复遍历。标准做法是把整个集合一起入队，一次 BFS 搞定：

vector<int> epsilonClosureSet(const vector<int>& stateSet, const vector<map<char, vector<int>>>& nfaTrans) { vector<bool> visited(nfaTrans.size(), false); queue<int> work; vector<int> closure; for (int s : stateSet) { if (!visited[s]) { visited[s] = true; work.push(s); } } while (!work.empty()) { int cur = work.front(); work.pop(); closure.push_back(cur); auto it = nfaTrans[cur].find('#'); if (it != nfaTrans[cur].end()) { for (int next : it->second) { if (!visited[next]) { visited[next] = true; work.push(next); } } } } sort(closure.begin(), closure.end()); return closure; }

这里我特意把结果排了序，方便后面比较两个状态集合是否相等。排序之后两个vector<int>可以直接用==比较，如果直接拿set<int>当集合也可以，但打印和比较没有 vector 直观，所以我选择 vector 加排序。

move 操作比闭包简单，它不需要递归，只要在给定状态集合里逐个查迁移表：

vector<int> move(const vector<int>& states, char ch, const vector<map<char, vector<int>>>& nfaTrans) { vector<int> result; for (int s : states) { auto it = nfaTrans[s].find(ch); if (it != nfaTrans[s].end()) { for (int next : it->second) { if (find(result.begin(), result.end(), next) == result.end()) { result.push_back(next); } } } } return result; }

move 只收集直接目标，不去管目标状态还能走哪些 ε 边。先 move 再闭包，顺序不能反，这是第一处最容易踩的坑，第 4 章的避坑清单里我会单独展开。

3.2 子集构造法主体：未标记状态队列如何生成完整 DFA

子集构造法的核心思想是：DFA 的每个状态就是一个 NFA 状态集合。算法从一个初始状态集合出发，每看到一个未处理的 DFA 状态，就对字母表中每个符号计算 move 和闭包，得到的新集合如果不在已知状态列表里，就新增一个 DFA 状态。

vector<set<int>> dfaStates; // DFA 状态编号对应的 NFA 集合，这里用 set 保证唯一 vector<map<char, int>> dfaTrans; vector<bool> dfaAccept; // 1. 构造初始 DFA 状态：NFA 初态的 ε-闭包 vector<int> initialVec = epsilonClosureSet({startState}, nfaTrans); set<int> initialSet(initialVec.begin(), initialVec.end()); dfaStates.push_back(initialSet); dfaTrans.push_back(map<char, int>()); dfaAccept.push_back(isAccept(initialSet, acceptStates)); // 2. 用一个队列维护“未标记”的 DFA 状态 queue<int> pending; vector<bool> processed(dfaStates.size(), false); pending.push(0); while (!pending.empty()) { int cur = pending.front(); pending.pop(); if (processed[cur]) continue; processed[cur] = true; // 对字母表中每个符号求 move + 闭包 for (char ch : sigma) { vector<int> afterMove = move({dfaStates[cur].begin(), dfaStates[cur].end()}, ch, nfaTrans); if (afterMove.empty()) continue; // 没有迁移，DFA 表中不记录该符号 vector<int> afterClosure = epsilonClosureSet(afterMove, nfaTrans); set<int> newSet(afterClosure.begin(), afterClosure.end()); // 判断这个状态集合是否已经存在 int target = -1; for (int i = 0; i < (int)dfaStates.size(); ++i) { if (dfaStates[i] == newSet) { target = i; break; } } if (target == -1) { target = dfaStates.size(); dfaStates.push_back(newSet); dfaTrans.push_back(map<char, int>()); dfaAccept.push_back(isAccept(newSet, acceptStates)); processed.push_back(false); pending.push(target); } dfaTrans[cur][ch] = target; } }

isAccept的实现是拿新状态集合和 NFA 终态集合求交集，只要交集非空，这个 DFA 状态就是终态。注意我这里是先 move 得到afterMove，再对它求闭包，不能反过来。如果你先闭包再 move，就会把“目标状态经过 ε 边可达的状态”全部漏掉，生成的 DFA 会缺边。

这段代码里还留了一个很实用的调试钩子：把dfaStates[i] == newSet这个比较循环改成打印两个集合的元素，就能看到为什么某个状态被认为重复了。实际写作业时，我习惯在每个循环结尾输出cur与target的编号，能直观看到 DFA 状态是逐步膨胀的。

3.3 最小化算法：等价类划分逐轮细化

DFA 最小化不引入新的理论，而是把已有的 DFA 状态按“行为是否一致”分组。两个状态等价的前提是：它们同为终态或同非终态，而且在任意输入符号下跳到的目标状态属于同一个组。这个过程从接受态和非接受态两组开始，反复分裂，直到任何组都不能再分裂。

int stateCount = dfaStates.size(); vector<int> stateGroup(stateCount, -1); vector<vector<int>> groups(2); // 初始划分：组0 放非终态，组1 放终态 for (int s = 0; s < stateCount; ++s) { stateGroup[s] = dfaAccept[s] ? 1 : 0; groups[stateGroup[s]].push_back(s); } bool changed = true; while (changed) { changed = false; vector<vector<int>> newGroups; map<vector<int>, int> bucket; for (int g = 0; g < (int)groups.size(); ++g) { for (int s : groups[g]) { // 用“每个符号下目标状态所在组号”的组合作为分桶 key vector<int> key; for (char ch : sigma) { auto it = dfaTrans[s].find(ch); int target = (it == dfaTrans[s].end()) ? -1 : it->second; key.push_back(target == -1 ? -1 : stateGroup[target]); } if (bucket.find(key) == bucket.end()) { bucket[key] = newGroups.size(); newGroups.push_back(vector<int>()); } newGroups[bucket[key]].push_back(s); } } if ((int)newGroups.size() > (int)groups.size()) { changed = true; groups = newGroups; for (int ng = 0; ng < (int)groups.size(); ++ng) { for (int s : groups[ng]) stateGroup[s] = ng; } } }

这个算法的关键在分桶 key 的构造：假设字母表是 a、b，一个状态在 a 下跳到组 2，在 b 下跳到组 1，另一个状态在 a 下跳到组 1，在 b 下跳到组 2，那么它们的 key 分别是[2,1]和[1,2]，必然分到不同的桶，说明它们可区分。如果两个状态所有符号下的目标组号都相同，它们才可能被合并。

注意这里的-1哨兵。我的 dfaTrans 里没有迁移的符号不会写入map，最小化时统一按-1处理。没有迁移和有迁移到非终态组的行为不同，-1参与比较才能区分这两种情况。

得到最终分组后，输出最小化 DFA 还需要做一次状态重编号：把每个组当做一个新状态，重新生成迁移表和接受表。这一步很机械，但容易出错，常见做法是建一个vector<int> groupToNewState(groups.size(), -1)，遍历旧状态时按组号依次分配新编号，然后再扫一遍旧的 dfaTrans 完成映射。

3.4 输出与结果校验：打印状态集合让错误无处藏身

这份代码在输出上的特点是“看得见中间过程”。很多实验代码只打印最终迁移表，出错了根本不知道是子集构造不对还是最小化不对。这份工程把中间结果全部打印出来：

void printDfa() { printf("DFA states:\n"); for (int i = 0; i < (int)dfaStates.size(); ++i) { printf("D%d = {", i); int idx = 0; for (int s : dfaStates[i]) { printf("%s%d", idx++ ? ", " : "", s); } printf("}%s\n", dfaAccept[i] ? " (accept)" : ""); } printf("DFA transition:\n"); for (int i = 0; i < (int)dfaTrans.size(); ++i) { for (auto& p : dfaTrans[i]) { printf(" D%d --%c--> D%d\n", i, p.first, p.second); } } }

打印格式里，D0 = {0, 1, 3}这样的集合表示法可以直接和教材上的手写推导结果对照。我这边对照时发现过最典型的问题：手推时漏掉 ε 闭包，导致某个 DFA 状态少了状态编号；代码一行打印就能定位是哪个状态集合不完整。

最小化之后，代码还会打印一遍新编号和旧编号的对应关系，比如“等价类0 包含原 DFA 状态 {0, 2}”。实验报告写结论时，这段对应关系比迁移表还有说服力，证明你确实合并了哪些状态。

4. 运行、排查与避坑：从编译到验收的完整流程

4.1 编译运行与输入文件格式

拿到源码后在 Linux 或 Windows 的 GCC 环境下直接编译即可，依赖只有标准库：

g++ nfa2dfa.cpp -O2 -o nfa2dfa ./nfa2dfa nfa_input.txt

假设你要处理经典的(a|b)*abb对应的 NFA，我一般会准备这样一份输入文件。状态编号从 0 开始，第三行的格式是“终态个数”加终态编号列表，注意实际使用时要替换成你课程要求的格式：

11 2 a b 0 1 10 0 2 # 4 1 1 a 1 2 1 b 2 3 1 a 1 4 1 b 5 5 1 b 6 6 1 a 7 7 1 b 8 8 1 a 9 9 1 b 10 10 0

这里每一行对应一个状态的迁移，“4”出现在第一行迁移里表示从状态 0 通过#可以到达状态 4。程序跑完后，终端先输出所有 DFA 状态及其 NFA 状态集合，再输出最终最小化的迁移表，整个过程不需要交互输入。

如果你的课程要求从标准输入读取而不是文件，改一行就行：把std::ifstream换成std::cin。我建议保留文件读取的方式，因为实验报告里可以贴多组用例反复验证，不需要每次重新敲输入。

4.2 实验报告里写什么：从算法描述到复杂度对比

这份资源里附带的实验报告，内容上不必夸大，但对不上代码会减分。正常情况下，报告应该包含算法流程、数据结构说明、运行结果、复杂度分析四个部分。子集构造法的复杂度最坏是 O(2^|S|)，因为 DFA 状态数可能指数增长；最小化部分用的是划分细化，每一轮需要扫描所有状态和所有符号，最坏可能跑很多轮，整体复杂度高于 Hopcroft 算法的 O(n log n)。报告里如果能指出“本实现选用划分细化，虽然效率不是最优，但逻辑直观，适合展示等价类分裂过程”，会比硬吹自己写了 Hopcroft 更可信。

结果部分要把代码输出截图和手推过程对照。比如最小化之后原状态 0 和 2 合并成一个等价类，报告里应该画出合并前后的两张迁移表。代码里打印的D0 = {0, 1, 3}这类集合，正好就是截图里的标注来源。

4.3 避坑清单：现象、原因、解决方案

我整理了几条这次实验里最容易翻车的点，每条都是我在实际调试中踩过的。

现象一：输出的 DFA 状态少了很多，某些符号根本没有迁移边。

原因是 move 之后没有继续求 ε-闭包。move 拿到的是“走一步符号到达的状态”，这些状态如果再走 ε 边能到更多状态，那 DFA 状态集合必须是闭包后的结果。解决方法是严格执行“move 完再闭包”的固定顺序，并且在 move 函数里不递归查 ε 边，把这两个操作完全拆开。

现象二：程序读入输入文件后直接崩溃，看到 vector 越界。

原因是对输入格式理解不一致，最常见的是状态编号从 1 开始的文件被强制当 0 开头处理，导致最后一个状态的下标超过nfaTrans.size()。解决方法是读入时做一层映射：文件里的状态编号统一减 1 存进nfaTrans，输出时再加 1。不要一边读一边直接用原始编号当 vector 下标。

现象三：最小化没有合并任何状态，输出结果和子集构造一模一样。

原因是初始划分写反了，把接受态和非接受态放进了同一组。最小化的第一步必须严格把终态和非终态分开，否则后面的分桶判断永远认为所有状态可区分。解决方法是打印初始stateGroup数组，检查是否满足“终态全为 1，非终态全为 0”。另外还有一种隐蔽情况：分桶 key 里没有包含无迁移的-1哨兵，导致两个都有无迁移符号的状态被认为等价，这部分要单独检查。

现象四：比较 DFA 状态集合时用vector<int>直接==，排序顺序不一致导致判断失败。

原因是手动添加新状态时没有统一排序。解决方法是所有闭包函数返回前都执行一次sort，或者统一改用set<int>存储 DFA 状态集合，让比较行为天然一致。我在dfaStates里用set<int>，闭包函数的中间结果用排序后的vector<int>，两边都稳。

调试时如果还是找不到问题，我一般会在子集构造循环里临时加一行输出：打印当前 DFA 状态编号、当前符号、move 结果集合、闭包结果集合。四列输出一出来，问题定位几乎不靠猜。

5. 二次开发：把这份实验代码扩展成一个小型正则匹配器

这份工程的价值不止于交一份实验报告。把 NFA 转 DFA 的链路反转过来，就是一个极简正则引擎的核心骨架。我做课程设计时就在这个基础上把代码扩展成了能对输入串做匹配的程序，改造点很清晰。

第一步是去掉中间状态集合，给 DFA 状态一个稳定的整数编号，然后写一个纯粹的模拟器：

// 输入串从初态开始逐字符走，走不动就匹配失败，走完查终态 bool simulate(const string& input, const vector<map<char, int>>& dfaTrans, int startState, const vector<bool>& dfaAccept) { int cur = startState; for (char ch : input) { auto it = dfaTrans[cur].find(ch); if (it == dfaTrans[cur].end()) { return false; // 当前状态下没有该符号的迁移 } cur = it->second; } return dfaAccept[cur]; }

这个函数就是词法分析器里“识别一个 token”的核心逻辑。配合第 3 章的子集构造，你只需要把输入字符串跑一遍模拟器，就能判断它是否被原正则接受。要注意的点是，模拟器只能判断整串匹配，如果要做“最长匹配”和“回退”，还得记录最近一次经过的终态位置，很多词法分析器的手写实现里都有这段逻辑。

第二步是支持字符类。课程实验的字母表往往是a、b这种单字符，但真实场景里需要[a-z]、.这类模式。常见做法是在读入 NFA 时做一次展开：把字符类拆成多个单字符迁移，字母表相应扩充。比如[a-z]展开成 26 条边。代价是状态数变大，但这正好能测出子集构造法的抗压能力。

第三步可以加 Thompson 构造法。写一个递归下降的语法分析器，把正则表达式解析成语法树，再按优先级转 NFA，最后复用现有的subsetConstruct和minimizeDfa。这个方向做完，你就拥有了一条完整的“正则表达式到最小化 DFA”流水线，后续做编译原理的词法分析课设就只是换输入输出格式的事。

我自己的习惯是改完代码后跑三组固定测试：空串、单字符、带闭包的长串，再对照原始 NFA 手推结果查一遍最小化表。从那以后，我每次做自动机相关实验都会强制走一遍“先验证闭包计算、再造 DFA、最后核对最小化等价类”的顺序，这套顺序救了我好几次期末周的命。如果你也在对着状态转换图手算到怀疑人生，希望这份代码能帮你省下那些本不该花的时间，希望帮到你。

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