企业官网建设流程全解析

简介：面向高校计算机专业「编译原理」课程的实验配套资料，聚焦正则表达式到确定有限自动机的完整实现链路，涵盖子集构造法由NFA转DFA、识别不可达与冗余状态、等价状态合并完成DFA最小化等核心环节，适合正在做课程实验或复习自动机理论的学生对照学习。压缩包共2个文件，含1份doc实验报告与1份cpp源码，整体约722KB，报告侧重实验目的、步骤记录、问题与解决方案的梳理，源码则以C++实现转换与最小化算法，二者配合便于理解算法细节并复现实验结果。已有416人学习。代码可直接编译调试，帮助读者把子集构造、状态合并等抽象理论落到可运行程序上，报告提供的分析思路也可作为撰写自身实验文档的参考，适合需要课设交付或想强化算法实现能力的读者。

1. 从一份实验报告说起：NFA 转 DFA 并最小化为什么值得单独做一套工具链

编译原理实验里，NFA 转 DFA 加最小化几乎是绕不开的一道题：正规式、自动机、子集构造、等价类划分，几块知识全压在一个实验里，不少人代码跑通却讲不清为什么这么写，报告写成了代码注释的复制粘贴。下面这套用 C++ 实现的方案，把 NFA 输入解析、ε 闭包、子集构造、划分细化、DFA 模拟五步拆成独立模块，配套一份能直接照着写进实验报告的文档结构，目标是交上去的东西不只是能跑的代码，而是讲得清、测得出、答辩经得起追问的完整方案。

2. 需求拆解与技术选型：为什么把一步拆成三阶段流水线

2.1 从实验要求反推真实需求

实验指导书上的要求通常只有一句话：读入一个 NFA，输出对应的最小化 DFA。但真正动手你会发现，这句话后面藏着至少五层需求，而每一层都可能成为卡住进度的地方。

第一层是输入。老师给的测试数据可能是正规式，也可能是文本描述的状态转移表，格式不统一，所以解析模块必须能吃下至少一种明确约定的格式，最好再内置一个 Thompson 构造，把正规式也接进来，这样自测时不用手写 NFA。

第二层是正确性。子集构造最容易出的错不是算法本身，而是 ε 闭包漏算或多算，导致 DFA 状态数偏大，最后跟标准答案对不上，而你又不知道错在哪一步。

第三层是可视化。实验报告里需要画出 NFA 图、DFA 转移表和最小化前后的对比，如果程序只输出一句"最小化完成"，报告就没法写。

第四层是可验证。最小化到底对不对，不能靠眼睛看状态数变少了就算成功，得有办法证明最小化前后的 DFA 识别同一个语言。

第五层是能讲。答辩时老师大概率会追问：为什么 ε 闭包用迭代不用递归？为什么划分细化能保证等价？这些问题在写代码时就要留下回答的位置。

提示：把这五层需求写成一张表格贴在报告的需求分析章节，比写一大段"本实验意义重大"有用得多，评阅的人一眼能看出你确实想过。

2.2 语言与数据结构选型：C++17、位图状态集与边表

语言选 C++，是因为自动机实验的状态集本质上是整数集合，需要频繁做交、并、查重和作为 map 的键，标准库里的std::set和std::map直接支持按字典序比较，天然能当哈希键用，换成脚本语言反而要自己处理集合的哈希。编译用 C++17 标准即可，主要是为了结构化绑定和std::optional这类让代码短一点的小特性，不涉及什么高深语法。

真正影响后面所有代码的是状态集的表示。状态数量在实验规模下一般不超过几十个，用std::set<int>足够，但如果想跑大一点的自动机，位图（std::bitset<128>或者uint64_t数组）会快一个量级。我一般会在方案里写清楚：默认用std::set<int>，因为可读性最好，报告里贴出来老师能看懂；如果状态数超过 64 再换位图，接口保持一致。

NFA 的存储用邻接边表，每个状态挂一个vector<pair<char,int>>，比邻接矩阵省空间，也方便处理 ε 边。DFA 的存储用转移表，因为 DFA 是确定性自动机，每个状态对每个符号最多一条出边，二维表最直观，也方便后面最小化时按列比较。

2.3 输入格式约定：让实验数据可复现

输入格式如果不提前定死，调试阶段会非常痛苦：今天手写一份 NFA，明天换成老师给的格式，解析代码改一次，前面的测试全部作废。我的做法是在方案里固定一种文本格式，同时提供正规式入口，两者最终都转成同一个NFA结构。

文本格式的设计原则是"人能手写、程序好解析、报告里好贴"。第一行状态数，第二行起始状态编号，第三行终态个数，第四行终态列表，第五行边数，之后每行一条边：源状态、符号、目标状态，符号位置写eps表示 ε 边。

5 0 1 4 6 0 a 1 0 eps 2 1 b 3 2 a 3 3 b 4 4 eps 1

对应的解析代码不复杂，关键是做好错误处理：状态编号越界、边数对不上、符号长度不为 1 且不是eps，这几种情况要直接报错并指出行号，而不是默默读进去然后算出一堆莫名其妙的结果。

// parse.cpp —— 按行读取 NFA 文本描述，出错时带上行号 NFA parseNFA(const std::string& path) { std::ifstream in(path); if (!in) throw std::runtime_error("无法打开输入文件: " + path); NFA nfa; int n = 0, start = 0, acceptCnt = 0, edgeCnt = 0; in >> n >> start >> acceptCnt; nfa.states.resize(n); for (int i = 0; i < n; ++i) nfa.states[i].id = i; nfa.start = start; for (int i = 0; i < acceptCnt; ++i) { int s; in >> s; if (s < 0 || s >= n) throw std::runtime_error("终态编号越界"); nfa.states[s].accept = true; } in >> edgeCnt; for (int i = 0; i < edgeCnt; ++i) { int from, to; std::string sym; in >> from >> sym >> to; if (from < 0 || from >= n || to < 0 || to >= n) throw std::runtime_error("第 " + std::to_string(i + 1) + " 条边状态编号越界"); char c = (sym == "eps") ? EPS : sym[0]; // EPS 为 '\0'，与可见字符区分 nfa.states[from].edges.emplace_back(c, to); } return nfa; }

这段代码的重点不在语法，而在两个约定：EPS用'\0'表示，这样普通字符和 ε 边在同一个char字段里就能区分，不用额外加标志位；状态编号从 0 连续分配，后面所有数组下标都可以直接用状态号，省掉一层映射。参数方面path是输入文件路径，返回的是值语义的NFA，调用方拿到的是一份完整拷贝，不用担心解析函数内部的临时对象被释放。

3. 总体架构设计：五个模块与两层数据结构的职责划分

3.1 模块划分与数据流

整套实现我拆成五个模块，每个模块一个头文件加一个源文件，编译产出一个可执行程序加一个测试程序。这么拆不是为了显得工程化，而是为了让报告里的"系统设计"章节有东西可写，答辩时也能顺着模块讲。

模块一负责解析，输入是文本文件或正规式字符串，输出是NFA对象。模块二负责子集构造，输入NFA和字母表，输出DFA。模块三负责最小化，输入DFA，输出新的DFA加上一张等价类映射表。模块四负责模拟运行，输入任意自动机和字符串，返回是否接受。模块五负责输出，把 NFA、DFA、最小化后的 DFA 分别打印成可读的转移表，必要时输出 DOT 格式用于画图。

数据流是一条单向链：解析 → 子集构造 → 最小化 → 输出，模拟运行作为工具函数被测试模块反复调用。单向链的好处是每一步都可以单独测试，子集构造算错了不用管最小化，最小化算错了不用怀疑解析。

// main.cpp —— 主流程只负责串联，不做任何算法 int main(int argc, char** argv) { if (argc < 2) { std::cerr << "用法: dfa_tool <nfa文件>\n"; return 1; } NFA nfa = parseNFA(argv[1]); std::vector<char> alphabet = collectAlphabet(nfa); // 扫描所有非 ε 边得到字母表 DFA dfa = subsetConstruct(nfa, alphabet); // 子集构造 DFA minDfa = minimizeDFA(dfa, alphabet); // 划分细化最小化 printDFA(std::cout, dfa, "子集构造结果"); printDFA(std::cout, minDfa, "最小化结果"); // 自检：最小化前后对所有长度 ≤ 6 的串判定必须一致 if (!languageEqual(dfa, minDfa, alphabet, 6)) { std::cerr << "最小化前后语言不等价，实现有误\n"; return 2; } return 0; }

这段主流程里最值得说的是最后那个自检。很多人的最小化代码写完，看一眼状态数从 5 变成 3 就认为对了，实际上可能把不该合并的状态合并了，得到的自动机识别的是另一个语言。加一段穷举比对的代码，长度 6 以内、字母表 2 个符号，也就一百多个串，跑起来是毫秒级，但能挡掉绝大多数低级错误。collectAlphabet的作用是扫描 NFA 所有边，收集非 ε 符号并去重排序，保证子集构造和最小化用的字母表完全一致——两边字母表不一致是最隐蔽的坑之一。

3.2 数据结构：NFA 边表、DFA 转移矩阵与划分表

三层数据结构对应三个阶段的产物，设计时要想清楚每一层"多存什么"，因为多存的字段往往就是报告里能写的设计点。

NFA 层存三个东西：状态数组、起始状态、每个状态的出边表。状态里除了 id 和 accept 标志，我在方案里还会加一个std::string tag字段，用来存这个状态对应的原始正规式子表达式，Thompson 构造时填进去，输出 DOT 时作为节点标签。实验报告里画出来的图带标签，比一堆圆圈好看得多，也更容易讲清每个状态从哪来。

DFA 层存四个东西：状态数组、转移表、起始状态、每个 DFA 状态对应的 NFA 状态集合。最后一个字段经常被忽略，但它是报告里"子集构造过程"那一节的素材来源——你可以直接把"DFA 状态 2 对应 NFA 状态集合 {3,5,7}"打印成表格，证明子集构造确实按定义在做。

最小化层不引入新结构，只是在 DFA 上维护一个group数组，表示每个状态当前属于哪个等价类。划分细化过程中只改这个数组的值，不改转移表，最后再根据group重建一个新的 DFA。这样做的好处是原始 DFA 始终完好，随时可以对比最小化前后。

// dfa.h —— DFA 的存储，subset 字段保留子集构造的中间结果 struct DFAState { int id; bool accept = false; std::set<int> subset; // 该 DFA 状态由哪些 NFA 状态合并而来 }; struct DFA { std::vector<DFAState> states; std::map<std::pair<int, char>, int> trans; // (源状态, 符号) → 目标状态 int start = 0; void setTrans(int from, char c, int to) { trans[{from, c}] = to; } int getTrans(int from, char c) const { // 缺失转移返回 -1，表示死路 auto it = trans.find({from, c}); return it == trans.end() ? -1 : it->second; } };

用map<pair<int,char>,int>而不是二维数组，是因为最小化过程中状态会被重新编号，二维数组要反复扩容和清空，map 则是插入即用，代价是常数大一点，实验规模下完全无所谓。getTrans返回 -1 表示该转移不存在，模拟运行时遇到 -1 直接判定拒绝，等价于进入了一个非接受状态的死状态，这样就不用显式构造陷阱状态，状态数更少，报告里的表也更好看。

4. 核心算法实现：从子集构造到划分细化的落地细节

4.1 ε 闭包与 move：子集构造法的两个原子操作

子集构造法看起来是一大段循环，其实拆开后只有两个原子操作：给定一个状态集合，求它的 ε 闭包；给定一个状态集合和一个符号，求经过该符号能到达的状态集合。这两个函数写对了，主循环几乎是照抄定义。

ε 闭包用迭代写，不用递归。原因是递归版本在 ε 边成环时会依赖访问标记，写漏一个标记就是无限递归，而迭代版本用一个显式的栈加一个集合，插入集合成功才入栈，天然处理环。递归版本在实验数据上通常也不会爆栈，但答辩时被问"如果 ε 环很长呢"，迭代版本更好回答。

// closure.cpp —— ε 闭包，迭代实现，天然处理 ε 环 std::set<int> epsilonClosure(const NFA& nfa, const std::set<int>& seed) { std::set<int> closure = seed; // 闭包至少包含种子集合本身 std::vector<int> stack(seed.begin(), seed.end()); while (!stack.empty()) { int s = stack.back(); stack.pop_back(); for (const auto& e : nfa.states[s].edges) { if (e.first != EPS) continue; // 只沿 ε 边走 if (closure.insert(e.second).second) { // insert 返回 second=true 说明是新状态 stack.push_back(e.second); } } } return closure; } // move.cpp —— 从状态集合出发，经过符号 c 能直接到达的状态集合 std::set<int> moveSet(const NFA& nfa, const std::set<int>& from, char c) { std::set<int> out; for (int s : from) { for (const auto& e : nfa.states[s].edges) { if (e.first == c) out.insert(e.second); } } return out; // 可能为空集，由调用方决定是否建状态 }

两个函数的参数含义要讲清：seed是起始状态集合，子集构造第一次调用时传{nfa.start}，之后传moveSet的结果；返回值是闭包后的集合，直接作为 DFA 状态的subset字段。moveSet返回空集是正常情况，表示该符号在该状态下没有出边，子集构造时跳过不建状态，这样生成的 DFA 是部分转移函数，比补全成完全转移函数状态数少，也更接近教材里画的样子。

有一点容易被忽略：epsilonClosure的种子集合本身可能包含多个状态，闭包要对每个种子都展开，所以初值直接拷贝seed，栈里压全部种子。如果只压第一个种子，多状态子集的闭包会算漏，而这种错误在单状态入口的测试里根本发现不了。

4.2 子集构造法：状态去重与转移表生成

子集构造的核心是一个工作队列加一张"状态集合 → DFA 状态编号"的映射表。映射表的作用是去重：同一个 NFA 状态集合可能从不同路径到达，如果没有这张表，就会为同一个集合生成多个 DFA 状态，状态数炸开，最后跟标准答案对不上，还查不出原因。

算法流程照定义走：初始集合取起始状态的 ε 闭包，编号为 0 并入队；每从队列取出一个集合 T，对字母表里每个符号 c，计算 U 等于 T 经 c 的 move 集合再取 ε 闭包；U 为空则跳过，U 未出现过则分配新编号并入队，最后记录 T 到 U 的转移。

// subset.cpp —— 子集构造，工作队列 + 集合到编号的映射去重 DFA subsetConstruct(const NFA& nfa, const std::vector<char>& alphabet) { DFA dfa; std::map<std::set<int>, int> idOf; // NFA 状态集合 → DFA 状态编号 std::queue<std::set<int>> work; auto s0 = epsilonClosure(nfa, {nfa.start}); idOf[s0] = 0; dfa.states.push_back({0, containsAccept(nfa, s0), s0}); dfa.start = 0; work.push(s0); while (!work.empty()) { auto T = work.front(); work.pop(); int from = idOf[T]; for (char c : alphabet) { auto U = epsilonClosure(nfa, moveSet(nfa, T, c)); if (U.empty()) continue; // 空集不建状态 auto it = idOf.find(U); if (it == idOf.end()) { // 新集合，分配编号 int id = static_cast<int>(dfa.states.size()); idOf[U] = id; dfa.states.push_back({id, containsAccept(nfa, U), U}); work.push(U); dfa.setTrans(from, c, id); } else { dfa.setTrans(from, c, it->second); } } } return dfa; }

containsAccept是个小工具函数，判断集合里是否含 NFA 终态，含则该 DFA 状态是终态。这里有个必须讲清的语义：DFA 状态是 NFA 状态的集合，只要集合中任意一个是终态，整个 DFA 状态就是终态，因为 NFA 的接受定义是"存在一条路径到达终态"。

状态编号的分配顺序直接影响输出表格的样子。上面代码按 BFS 顺序编号，起始状态固定为 0，之后按发现顺序递增，这样打印出来的转移表比较规整，和教材例题的编号顺序也基本一致，报告里贴表时省得解释。

4.3 Hopcroft 最小化：划分细化与等价状态合并

最小化的目标是合并等价状态。两个状态等价的意思是：从它们出发，对任意输入串，要么都到达终态，要么都到达非终态。工程上不去枚举所有串，而是用划分细化：先把状态分成终态和非终态两组，因为这两组显然不等价；然后反复检查每一组内的状态，如果对某个符号它们的转移落到了不同的组，就把这组拆开；直到所有组都无法再拆为止。

标准 Hopcroft 算法用工作集把复杂度压到 O(n log n)，但需要维护"哪些组被某个符号指向"的反向索引，代码量翻倍，调试成本高。实验规模下状态数最多几十个，用朴素的划分细化版本，复杂度 O(n²·|Σ|)，跑起来一样是瞬间，而且代码短、逻辑直观、报告里画得出流程图、答辩时讲得清。我的建议是实验阶段用朴素版，如果老师明确要求实现 Hopcroft，再在这个骨架上加工作集优化。

// minimize.cpp —— 划分细化：反复按符号分裂等价类，直到组数不再增加 DFA minimizeDFA(const DFA& dfa, const std::vector<char>& alphabet) { int n = static_cast<int>(dfa.states.size()); std::vector<int> group(n, 0); // 初始划分：终态一组（编号 1），非终态一组（编号 0） for (int i = 0; i < n; ++i) group[i] = dfa.states[i].accept ? 1 : 0; bool changed = true; while (changed) { std::map<std::pair<int, std::vector<int>>, int> sig2group; std::vector<int> next(n, 0); for (int i = 0; i < n; ++i) { std::vector<int> moves; moves.reserve(alphabet.size()); for (char c : alphabet) { int t = dfa.getTrans(i, c); moves.push_back(t < 0 ? -1 : group[t]); // -1 表示无转移，单独一类 } auto sig = std::make_pair(group[i], moves); // 旧组号 + 各符号落点组成签名 auto it = sig2group.find(sig); if (it == sig2group.end()) { int g = static_cast<int>(sig2group.size()); sig2group[sig] = g; next[i] = g; } else { next[i] = it->second; } } int before = countGroups(group), after = countGroups(next); group = next; // 用新编号覆盖旧编号 changed = (after > before); // 组数不再增加就收敛 } return rebuild(dfa, group); // 按等价类编号合并状态，重建转移表 }

这段代码的关键在签名构造：group[i]保证不同旧组的状态永远不会被合并到一起，moves记录每个符号的转移落在哪个旧组，二者拼起来就是划分细化的判据。收敛条件用"组数不再增加"而不是"group 数组不再变化"，因为每轮分组都从 0 重新编号，编号本身一直在变，拿数组比会陷入死循环。

rebuild负责把等价类映射回具体的 DFA：每个组选一个代表状态（组内编号最小的那个），组内任一状态是终态则新状态是终态，原来指向组内任意状态的转移统一改指向代表。这里还要处理一个细节：原 DFA 的起始状态所在的组，就是新 DFA 的起始状态，不能简单取编号 0 的组，否则起始状态可能错位，导致所有测试串的判定整体偏移一位，而且错得很隐蔽。

4.4 最小化 DFA 的模拟运行与结果输出

模拟运行有两个用途：一是自检，二是报告里演示用例。实现就是一个循环，从起始状态出发，每读一个字符查一次转移，查到 -1 直接拒绝，读完所有字符后看当前状态是不是终态。

// simulate.cpp —— 在 DFA 上跑一个字符串，返回是否接受 bool accepts(const DFA& dfa, const std::string& input) { int cur = dfa.start; for (char c : input) { int nxt = dfa.getTrans(cur, c); if (nxt < 0) return false; // 无转移等价于进入死状态 cur = nxt; } return dfa.states[cur].accept; } // 穷举 length 以内所有串，比对两个 DFA 的判定结果 bool languageEqual(const DFA& a, const DFA& b, const std::vector<char>& alphabet, int length) { std::function<bool(std::string&, int)> dfs = [&](std::string& s, int depth) { if (accepts(a, s) != accepts(b, s)) return false; // 发现反例立即失败 if (depth == length) return true; for (char c : alphabet) { s.push_back(c); if (!dfs(s, depth + 1)) return false; s.pop_back(); } return true; }; std::string buf; return dfs(buf, 0); }

accepts的参数是 DFA 引用和输入串，返回布尔值，逻辑上等价于"读完串之后状态是否终态"，但要特别注意空串：循环一次都不执行，直接返回起始状态是否终态，这个行为是对的，不要额外加特判。languageEqual用深度优先枚举所有长度不超过length的串，两个自动机对同一个串判定不同就立刻返回 false 并可以打印反例。长度取 6 是个经验值：对于实验规模的自动机，如果两个 DFA 状态数都在二十以内，长度 6 以内找不出反例基本可以认为等价，当然严格的等价判定要用乘积自动机做可达性分析，那是加分项，可以写进报告的"改进方向"。

输出模块不要小看。转移表用固定列宽打印，终态用*标记，起始状态用->标记，这些细节直接决定报告里的表格好不好看。再写一个 DOT 输出函数，把状态和边按 Graphviz 语法打印出来，粘到在线工具里就能出图，省掉手工画图的时间。

5. 避坑与排查：五个最容易翻车的点

5.1 ε 闭包漏算种子集合本身

现象是子集构造出来的 DFA 状态数明显偏多，或者某些本该接受空串的自动机不接受空串。原因通常是epsilonClosure只从种子集合的第一个状态开始展开，或者把种子集合当成"要扩展的起点"而没有先并入结果集。解决方法是让闭包结果集合的初值直接等于种子集合，栈里压入全部种子，扩展时只处理新插入的状态，这个写法在上面 4.1 的代码里已经固定下来了，改代码时不要动这个初值逻辑。

顺带一提，验证闭包写没写对，最简单的用例是只有一条 ε 边链的 NFA，比如 0 --ε--> 1 --ε--> 2，终态是 2，输入空串应该接受。如果这条用例挂了，基本可以确定是闭包的问题。

5.2 字母表不一致导致最小化结果错乱

现象是最小化之后的 DFA 转移表少了几列，或者自检时发现最小化前后对大写字母的判定不一致。原因是子集构造用的字母表是从 NFA 边里扫出来的，最小化时又另外扫了一遍，如果中间做过排序或去重的方式不同，两边字母表顺序或内容不一致，签名里的moves向量长度就不同，划分细化会把本该同组的状态拆开。

解决方法是字母表只生成一次，以参数形式一路传下去，子集构造、最小化、自检全部用同一个std::vector<char>。这条经验在多个模块共享配置时都适用：能传参就不要各自重算。

5.3 最小化收敛条件写错导致死循环

现象是程序卡在最小化那一步不动，或者 CPU 占满但没有任何输出。原因是收敛条件写成了"group 数组和上一轮完全相等"，而每轮分组都从 0 重新编号，编号顺序变化会让数组永远不相等。

解决办法是比较划分的组数而不是编号本身，组数不再增加就退出；或者改用规范化的编号方式，让编号只由签名决定，与遍历顺序无关。如果已经卡住，可以在循环里加一句打印当前组数的调试输出，跑一次就知道是不是组数在反复震荡。

5.4 起始状态在重建时错位

现象是所有测试用例的结果整体偏移，本该接受的串被拒绝，本该拒绝的被接受。原因是最小化后直接取编号为 0 的等价类作为新起始状态，而原起始状态可能属于别的组。

解决办法是重建时显式记录newStart = group[dfa.start]，再把这个组号映射成重建后的状态编号。这个问题特别值得写进实验报告的"调试记录"，因为它说明了一个通用道理：算法正确不代表实现正确，索引映射这类细节才是 bug 高发区。

5.5 空集与死状态混淆

现象是 DFA 状态数比标准答案多出若干，或者打印出来的转移表里出现了一个没有出边、也不是终态的孤立状态。原因是在子集构造时把空集也当作一个合法状态建了出来。

按子集构造的定义，空集确实是 DFA 的一个合法状态，但它是个陷阱状态，所有转移指向自己，加进去会让状态数膨胀，也让报告里的表变得难读。实践中的做法是空集不建状态，转移缺失即视为进入陷阱，getTrans返回 -1，模拟运行时直接拒绝。这个取舍要在报告里说明，别让老师以为你漏了情况。

6. 验收与答辩：用一组用例把实现讲清楚

验收这件事，很多人以为把程序跑通、截图贴上就完了，结果被问一句"你怎么知道最小化之后语言没变"就答不上来。我的建议是把验收做成三层，每层都有可展示的产物。

第一层是单点用例，验证每个原子操作。ε 闭包用只有 ε 边链的 NFA；moveSet用单符号单边的 NFA；子集构造用经典的正规式(a|b)*abb，它的 Thompson NFA 有十来个状态，子集构造后应该得到 4 个 DFA 状态，这个数字是可以背下来的，对不上就说明中间某一步错了。

第二层是合并用例，验证最小化确实有效。构造一个 NFA：起始状态 0 经a到终态 1，经b到终态 2，1 和 2 都没有出边。子集构造会得到 3 个状态：{0}、{1}、{2}，但{1}和{2}都是终态且无转移，显然等价，最小化后应该变成 2 个状态。这个用例小到可以手算，大到能体现划分细化的效果，是报告里最有说服力的一张对比表。

第三层是等价性自检，也就是 4.4 里那段穷举比对。这层的价值在于它不依赖你手算的标准答案，是程序自己证明自己。答辩时把这段代码打开，让老师随便给一个长度不超过 6 的串，现场跑一遍，比任何解释都硬。

讲的时候顺序也有讲究。不要一上来就讲 Hopcroft，先讲需求：为什么需要子集构造，因为 NFA 不确定；为什么需要最小化，因为子集构造会生成等价状态。然后讲数据结构，让老师知道你清楚每个字段为什么存在。最后讲验证，把三层用例的产物摆出来。整个过程控制在五分钟以内，留出时间回答问题。

我踩过最疼的一次坑，是报告里只写了算法步骤和最终结果，没写中间过程，被追问"这个 DFA 状态对应哪些 NFA 状态"时当场翻代码找。从那以后我每次做自动机相关的实验，都强制把subset字段打印成一张对照表放进报告，谁问都能直接指过去。希望这套结构能帮到你，少走一点弯路。

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