企业官网建设流程全解析

简介：本资源面向高校『编译原理』课程学习者，聚焦自动机理论中的核心实验环节，解决从非确定有限自动机（NFA）到确定有限自动机（DFA）的转换及最小化问题。资源包共2个文件，含1份doc实验报告与1份cpp源代码，压缩包约722KB，报告用于记录实验目的、步骤、遇到的问题与解决方案，源码则用C++实现子集构造法与状态等价合并的完整流程。已有416人学习下载。读者可从中获得可直接编译运行的实现代码，对照报告理解子集构造法如何以NFA状态子集构建DFA状态、如何识别并合并在任意输入串下行为一致的状态以消除冗余，并体会不可达状态与等价状态的处理思路。对于郑州大学等院校学生，这份材料贴近课程实验要求，可作参考模板与排错对照，帮助把抽象理论落到编程实践，加深对词法分析中有限自动机设计的理解。

1. 从正则到状态机：为什么“确定化”这一步绕不过去

编译原理课设里最容易被当成填空题的一步，是 NFA 转 DFA。很多人照着教材把子集构造法抄完，跑通一条(a|b)*abb就交差，直到换一条带 ε 边的正则，状态数翻了三倍，才发现自己没搞懂这步在干什么。反直觉的地方在于：NFA 才是人能写出来的东西，它允许一个状态对同一个字符有多条出边，允许不读字符就跳走；DFA 每个状态对每个字符至多一条出边，执行时不用“猜”。用 C++ 写的词法分析器最终跑的是一张整数下标的二维转移表，那张表每个下标，其实是原 NFA 一堆状态的集合。把不确定性压成确定性、再把确定出来的冗余合并掉，就是这条链条要解决的事。搞懂它，你才知道词法分析工具生成的状态号背后到底是什么。

2. 子集构造法：一个 DFA 状态为什么必须是一堆 NFA 状态的集合

2.1 不确定性到底卡在哪：同一个字符两条出边

先看 NFA 的执行模型。给定当前状态 q 和输入字符 a，转移函数 δ(q, a) 返回的是一个状态集合而不是单个状态；再加上 ε 边这种不消耗输入就能走的边，一个 NFA 在读入任意前缀之后，所处的“位置”天然就是一组状态。模拟这种机器最直白的办法是回溯：遇到分支就存个现场，试不通再退回来。对(a|b)*abb这种小正则无所谓，可一旦分支嵌套，最坏情况下的尝试次数会指数增长——这正是血泪经验的来源，很多人第一次写正则引擎就翻在这里。

DFA 把这件事抹平了：δ(q, a) 是单值函数，读一个字符走一步，全程不需要保存任何现场，扫描一个长为 n 的输入就是 O(n)。代价是 DFA 的转移表没法手写，哪怕只描述[a-z]+@[a-z]+\.com这种规则，人脑也拼不出那张表。所以工程上的固定套路是：人写正则或 NFA，机器负责确定化。子集构造法的核心洞察只有一句话——“我现在可能处在哪几个 NFA 状态”这个集合本身，就可以当作 DFA 的一个状态。把“可能性”实体化成一个编号，不确定性就消失了。

这样构造出来的 DFA，状态数上界是 2^n（n 为 NFA 状态数），因为每个 DFA 状态对应 NFA 状态集的一个子集。这个上界不是吓唬人的：像(a|b)*a(a|b)^{k}这类正则，最小 DFA 恰好需要 2^k 个状态，任何算法都压不下去。所以“状态爆炸”不是你代码写错了，而是问题本身的性质，后面第 6 章会讲到工程上怎么绕。

2.2 ε-闭包：把“免费跳转”算进状态集合里

ε 边是 NFA 里最容易被写错的部分。它表示“不读任何字符就能过去”，所以在任何时刻，机器实际可能处在的位置，是从当前状态集合出发、沿任意条 ε 边能到达的全部状态。这个集合叫 ε-闭包，记为 closure(S)，它有三个必须记住的性质：

• 包含自身：closure(S) ⊇ S，S 里每个状态都在，这一点漏掉就会出现“初态少了一个”的玄学 bug。
• 对 ε 边封闭：closure(S) 里任何状态沿 ε 边走一步，落点仍在 closure(S) 里。
• 对并集可分配：closure(S ∪ T) = closure(S) ∪ closure(T)，这条性质后面能拿来换性能。

构造过程中，闭包要出现两次。第一次是确定初态：DFA 的起始状态不是 NFA 的起始状态 q0，而是 closure({q0})。第二次是每个转移：对 DFA 状态 T 和字符 a，先算 move(T, a)（只沿 a 边走一步，不取闭包），再对结果取 closure，得到的集合 U 才是转移目标。顺序不能反——先闭包再 move 会漏掉“走完 a 边之后才能免费跳过去”的那些状态，这是实验报告里被问得最多的一处。

2.3 工作列表算法：怎么保证有限步收敛

子集构造本质是一个在 2^n 空间里的图搜索：每个集合是一个节点，每个字符是一条出边。既然搜索空间有限，用“待处理队列 + 已访问集合”就能保证终止，这是标准的 BFS 骨架。下面是核心循环，用std::bitset表示集合、用std::map同时充当编号表和 visited 标记：

using StateSet = std::bitset<MAXN>; // 位图表示 NFA 状态集合，也就是一个 DFA 状态 std::map<StateSet, int> id; // 集合 -> DFA 状态编号，同时兼任 visited std::queue<StateSet> work; // 待处理队列，BFS 保证每个集合只展开一次 std::vector<std::array<int, SIGMA>> trans; // DFA 转移表，-1 表示无出边 StateSet start = epsilonClosure(oneHot(nfaStart)); id[start] = 0; trans.push_back(emptyRow()); // 先占位，编号 0 给初态 work.push(start); while (!work.empty()) { StateSet T = work.front(); work.pop(); int tid = id[T]; // T 的编号在入队时就已分配 for (int c = 0; c < SIGMA; ++c) { // 必须遍历整个字母表，不能只试出现过的字符 StateSet U = epsilonClosure(move(T, c)); if (U.none()) continue; // 空集不建状态，否则会凭空多出一个死状态 if (!id.count(U)) { // 只有全新集合才分配编号并入队 id[U] = (int)trans.size(); trans.push_back(emptyRow()); work.push(U); } trans[tid][c] = id[U]; } }

这段代码有三处容易改错。id.count(U)既是查编号也是查重，如果只在队列里查重，同一个集合可能被分配两次编号，最后最小化时状态数永远对不上。U.none()那一行决定了要不要保留死状态：直接跳过的写法得到的是部分 DFA（缺边即拒绝），保留空集则得到完全 DFA（多一个陷阱状态），两种都能跑，但最小化的输入不同，实验报告里必须写清楚你选的是哪种。trans必须在给编号之前 push 占位，否则trans[tid]会越界——这是 C++ 里典型的“编号先于容器扩容”的踩坑点。

2.4 状态数为什么会爆炸：2^n 上界与实际的差距

理论上界是 2^n，实际跑出来的状态数取决于正则的“记忆需求”。像标识符[a-zA-Z_][a-zA-Z0-9_]*这种，NFA 只有十几个状态，子集构造后也就十几个，因为任何时刻“可能处在的位置”几乎唯一。而(a|b)*a(a|b)^{k}这种要求“倒数第 k 个字符是 a”的规则，DFA 必须记住最近 k 个字符，状态数就是 2^k。下面这组量级是这类实验里常见的示意，不同实现会有出入，但趋势一致：

看这张表要抓住一点：最小化对“本身就已经最小”的 DFA 毫无作用，它压掉的是子集构造过程中产生的不可区分冗余，而不是问题固有的复杂度。所以别指望最小化能救状态爆炸，它救的是转移表体积和查表缓存命中率。

3. ε-闭包与 move 的源码级实现：闭包为什么必须用标记数组

3.1 图的存储：邻接表怎么分开存 ε 边和字符边

NFA 就是一张有向图，边分两类：带字符的边和不带字符的 ε 边。最省事的存法是把两类边分开，都做成邻接表：

std::vector<std::vector<int>> epsEdge; // epsEdge[q]: q 经 ε 边直达的状态 std::vector<std::array<std::vector<int>, SIGMA>> chEdge; // chEdge[q][c]: q 经字符 c 直达的状态

为什么不用邻接矩阵？因为 NFA 的边是稀疏的，一个状态平均出边不到两条，矩阵的 n² 空间里绝大部分是 0，而且矩阵没法直接表达“一个状态对同一字符有多条出边”这件事（除非你存 bool 矩阵再逐列扫描，那反而更慢）。用vector<vector<int>>还有一个隐性好处：遍历某个状态的全部 ε 出边时，内存是连续的，缓存友好；而array<vector<int>, SIGMA>把字符维度摊平成下标，省掉一次查 map 的开销，这对 26 个字母或 128 个 ASCII 字符的字母表来说非常划算。

需要留意的是SIGMA的定义方式。如果字母表直接从输入里扫出来，字符到下标要做一次映射（std::unordered_map<char,int>或直接unsigned char当下标）；如果偷懒按 ASCII 开 128 个槽，转移表会大一圈但代码简单得多。实验里的规则集通常很小，按 ASCII 开表是更稳的选择，代价只是内存。

3.2 闭包计算的不动点：栈加 visited 标记

ε-闭包本质是从一个集合出发做图可达性搜索，用 DFS 或 BFS 都行，关键是必须在入栈时就打标记，而不是出栈时：

StateSet epsilonClosure(const StateSet& S) { StateSet res = S; // 闭包一定包含自身，先并进来 std::stack<int> stk; for (int q = 0; q < n; ++q) if (S.test(q)) stk.push(q); // 集合里每个状态都是搜索起点 while (!stk.empty()) { int q = stk.top(); stk.pop(); for (int p : epsEdge[q]) { if (!res.test(p)) { // 没进过闭包才展开：既去重，也防止 ε 环死循环 res.set(p); stk.push(p); } } } return res; }

res同时承担两个角色：结果集合和 visited 数组。if (!res.test(p))这一行是整个函数的安全阀，NFA 里出现ε自环或者q1 -ε-> q2 -ε-> q1这种环非常正常（比如a*的构造），没有这行判断，栈会无限增长直到内存耗尽——这是实验里最经典的死循环，编译能过、运行挂死，调试器一停发现栈里全是重复状态。

为什么用显式栈而不是递归？NFA 状态数虽然一般不大，但学生写的构造器经常生成几百个状态的链式结构，递归深度等于最长 ε 链长度，在默认栈大小下不保险。显式栈把深度问题转移到了堆上，代价只是几行代码。

单次闭包的时间复杂度是 O(n + |E_ε|)，其中 |E_ε| 是 ε 边数。子集构造里每个 DFA 转移都要调一次，假设 DFA 有 m 个状态、字母表大小 σ，总代价就是 O(m·σ·(n+|E_ε|))。对教学规模的输入完全够用。

3.3 move 与 closure 的职责分离：为什么 move 不取闭包

move只做一件事：从集合 S 出发，沿字符 c 的边走恰好一步，把落点收集起来。

StateSet move(const StateSet& S, int c) { StateSet res; for (int q = 0; q < n; ++q) if (S.test(q)) for (int p : chEdge[q][c]) res.set(p); // 只走一步，不取闭包 return res; }

把闭包留给调用方补，是一个刻意的设计取舍。如果move内部顺手把闭包取了，那么“先算 move 再算 closure”和“先算 closure 再算 move”这两种顺序在代码里就分不清了，而它们在语义上差别巨大：前者才是子集构造需要的（先消耗字符，再免费跳转），后者会多算出一批“还没消耗字符就能到达”的状态，做出来的 DFA 会接受本该拒绝的串。函数职责单一，出错时定位范围就小——这也是我在写这类小工具时最看重的一点。

顺带说一句，move里对S的遍历是0..n-1全扫，虽然浪费，但 n 小的时候比维护一个“集合中元素列表”更省心。真要优化，可以在bitset上用_Find_first/_Find_next（MSVC）或手写按 64 位字扫描，跳过全零的字。

3.4 常数优化：利用闭包对并集的分配律预计算

前面提过 closure(S ∪ T) = closure(S) ∪ closure(T)，这条性质可以直接换成性能：每个单状态的 ε-闭包只跟图结构有关，与构造过程无关，完全可以预计算一次，之后任何集合的闭包就是若干位图或起来。

std::vector<StateSet> epsMemo(n); // epsMemo[q] = closure({q})，只算一次 for (int q = 0; q < n; ++q) epsMemo[q] = rawClosure(oneHot(q)); StateSet epsilonClosure(const StateSet& S) { StateSet r; for (int q = 0; q < n; ++q) if (S.test(q)) r |= epsMemo[q]; // 按位或，替代一次图搜索 return r; }

改动之后，每次求闭包从“一次图搜索”退化成“若干次位或”，在 n 上百、转移上万的情况下差别很明显。代价是 n 个 bitset 的内存（n × n/8 字节），n=500 时约 31KB，完全可接受。这个优化在教材里不会写，但它体现的是同一件事：闭包是图的性质，不是构造过程的性质，把与输入无关的计算提到循环外，是这类状态机构造的通用手法。

4. DFA 最小化：划分细化凭什么敢把两个状态合并成一个

4.1 等价状态的定义：任意后缀上的接受性都一致

最小化的目标是把“行为完全一样”的状态合并。什么叫完全一样？形式化地说，状态 p 和 q 等价，当且仅当对任意字符串 w ∈ Σ*，从 p 出发读完 w 停在接受态，与从 q 出发读完 w 停在接受态的结论相同。注意这个定义量化的是所有后缀串，包括空串，所以“p 是接受态、q 不是”这一条就足以判定二者不等价——这是初始划分的依据。

这个关系是等价关系（自反、对称、传递），所以能把状态集切成若干互不相交的等价类，最小 DFA 的状态数就是等价类的个数。这句话是整章的地基：最小化不是“试试看能不能合”，而是求一个等价关系的商集，结果唯一（同构意义下）。

实际算法不可能枚举所有后缀串。它用的是反过来的一步步逼近：先假设所有状态都等价，然后不断找出“能被区分”的对子，把划分越切越细，直到再也切不动为止。切不动时的划分，就是那个等价关系。

4.2 初始划分：接受态和非接受态为什么必须先分家

第一刀必须切在接受态集合 F 和非接受态 Q\F 之间。理由前面说过：空串就是一个合法的后缀，读完空串后接受态接受、非接受态拒绝，这两类状态立刻可区分。如果初始划分把接受态和非接受态混在一组，后面的裂分循环无论怎么迭代都不可能再把它们分开——因为裂分只根据“转移落点所在组号”来判断，而两类状态从一开始就共享同一个组号，等于把错误固化进了初始条件。这是最小化结果“看起来没错但状态数多了几个”的常见根源，也是避坑章节里要展开的一条。

如果 F 是空集或全集，最小 DFA 只有一个状态，这是合法的边界情况，代码里要能处理，别让sig2id之类的容器在空输入上崩掉。

4.3 裂分循环：按“转移落点所属组号”做签名

裂分的判据是：同一组内的两个状态 p、q，如果存在字符 c 使得 δ(p,c) 和 δ(q,c) 落在不同的组，那它们就能被“字符 c 加后续后缀”区分开，必须分家。把每个状态的“签名”定义为(是否接受态, δ(p,c1) 的组号, δ(p,c2) 的组号, …)，签名相同的状态属于同一新组，签名不同的立刻裂开。

std::vector<int> group(nDfa, 0); for (int i = 0; i < nDfa; ++i) group[i] = isAccept[i] ? 1 : 0; // 初始两分 while (true) { std::map<std::vector<int>, int> sig2id; // 签名 -> 新组号 std::vector<int> next(nDfa); for (int i = 0; i < nDfa; ++i) { std::vector<int> sig; sig.push_back(isAccept[i] ? 1 : 0); // 接受性也是签名的一部分 for (int c = 0; c < SIGMA; ++c) { int t = trans[i][c]; sig.push_back(t == -1 ? -1 : group[t]); // 死转移单独占一类 } auto it = sig2id.find(sig); if (it == sig2id.end()) { // 新签名，分配新组号 int g = (int)sig2id.size(); sig2id[sig] = g; next[i] = g; } else { next[i] = it->second; } } if (sig2id.size() == countGroups(group)) break; // 组数不再增长即收敛 group = next; }

三个细节决定成败。第一，签名里必须显式带上接受性，虽然初始划分已经用过了，但在后续轮次里group会变，靠group[i]间接携带接受性并不可靠。第二，t == -1必须映射成独立的-1，不能映射成某个具体组号，否则“缺边”和“指向某组”会被混为一谈，最小化后可能出现本该拒绝的串被接受。第三，循环退出条件比较的是组数，不是“next和group逐元素相同”——后者在这种重新编号的实现里几乎永远不成立，会死循环。

收敛性来自一个单调性：每一轮划分只会更细，不会更粗，而状态数有限，所以最多迭代 n 轮。每轮代价 O(n·σ·log)，整体 O(n²·σ·log)，对教学规模毫无压力。

4.4 从划分到新转移表：状态重编号与不可达状态剔除

划分稳定后，每个等价类成为新 DFA 的一个状态。重建转移表的动作是：给每个组选一个代表元，用代表元的转移行查目标组号。

std::map<int, int> gid2new; // 组号 -> 新状态编号 std::vector<int> rep; // 每组的代表元 for (int i = 0; i < nDfa; ++i) if (!gid2new.count(group[i])) { gid2new[group[i]] = (int)rep.size(); rep.push_back(i); } std::vector<std::array<int, SIGMA>> newTrans(rep.size()); for (size_t g = 0; g < rep.size(); ++g) { int i = rep[g]; for (int c = 0; c < SIGMA; ++c) { int t = trans[i][c]; newTrans[g][c] = (t == -1) ? -1 : gid2new[group[t]]; // 目标组号翻译成新编号 } }

注意这里没做的一件事：剔除不可达状态。最小化算法本身不认识“从初态能不能走到”，它只看等价关系，所以子集构造时如果保留了陷阱状态或者残留了孤立组，最小化输出里一定多出来一个。正确顺序是先在原 DFA 上做一次从初态的 BFS 标记可达，删掉不可达状态后再最小化；或者最小化完再按新表做一次可达性裁剪。两种顺序都行，但必须做一次，否则实验报告里“最小化后状态数”永远比参考答案多。

4.5 朴素裂分和按字符分桶：复杂度上的取舍

上面这段是“每轮全量重算签名”的朴素写法，好写好调，缺点是每轮都要对整个状态集扫一遍，还要给每个状态构造一个长度 σ+1 的 vector 做 map 的 key，内存分配很碎。真要对大输入优化，思路是换一种迭代方式：维护一张“状态对可区分表”，初始标记接受/非接受对，然后反复扫描所有对子，把“某个字符下转移落进已知可区分对”的对子也标成可区分，直到一轮扫下来没有新增。这种做法实现更繁琐，但常数更小，也更容易解释“为什么它能收敛”。

更进一步的优化是按字符给状态分桶，把每轮 O(n·σ) 的签名比较降下来，得到接近 O(σ·n log n) 的复杂度。对编译原理实验这种规模，朴素版跑几十毫秒就完了，追这个复杂度意义不大；但知道有这条路，能让你在别人问“最小化能不能更快的”时候不至于卡壳。取舍点很实际：代码可读性和调试成本，比一个只在十万级状态才体现出来的渐进优势值钱。

5. 避坑：最小化结果对不上时先查这五处

5.1 坑一：ε-闭包漏算起点自身

现象：用一条带 ε 分支的正则测试，DFA 拒绝了一个本该接受的串，而换一条不带 ε 的正则一切正常；把 NFA 状态一个个打印出来看，闭包结果里少了初态本身。

原因：闭包实现里res初始化成空集，然后靠遍历 ε 边往里加状态。如果某个状态没有任何 ε 出边，它永远进不了res，闭包就变成了“严格后继集合”。对S = {q0}且 q0 无 ε 边的情况，闭包直接是空集，初态都没了。

解决：StateSet res = S;一开始就并进自身，这是闭包定义的第一条。如果用了预计算版本，epsMemo[q]在初始化时必须包含 q 自己，rawClosure(oneHot(q))里也要先res = oneHot(q)。

5.2 坑二：只对出现过的字符建转移列

现象：最小化之后，某些字符列整列是 -1，或者转移表维度比字母表小，扫描输入时下标越界；更隐蔽的情况是表能跑，但某些串被错误接受。

原因：为了省事，子集构造的内层循环写成“遍历 chEdge 里出现过的字符”，而不是遍历整个字母表。字母表里那些在当前集合下没有出边的字符，就压根没写进转移行，重编号之后列对不齐。

解决：内层一律for (int c = 0; c < SIGMA; ++c)，无出边就写 -1（或指向陷阱状态）。字母表大小不超过 128 的时候，这点开销可以忽略，换来的是表结构永远规整，后面重编号、最小化、生成扫描器代码都不会错位。

5.3 坑三：不可达状态没删，最小化多出一个组

现象：参考实现输出 4 个状态，你输出 5 个，把两边的转移表打印出来逐个比对，发现多出来的那个状态没有任何入边，也从初态走不到。

原因：子集构造时把空集也当成了一个合法状态保留下来（即保留陷阱状态的写法），或者调试过程中手动加了几个状态忘了删；最小化只看等价关系，不管可达性，于是这个状态自成一个组。

解决：最小化前后任意一个时点做一次从初态的 BFS/DFS 可达标记，把所有未标记的状态连同相关转移行一起删掉。建议把这个裁剪写成独立函数，在子集构造输出后立刻调一次，这样后续所有统计都以裁剪后的规模为准。

5.4 坑四：签名里把死转移和“指向某组”混为一谈

现象：最小化后串的接受性判断错了，常见表现是前缀匹配本该失败却通过，或者尾部字符被忽略。

原因：签名构造时写成sig.push_back(group[t])，而t == -1时访问了group[-1]。有的实现侥幸没崩（vector 的负下标恰好落在别的内存上），返回一个看似合理的组号，于是“没有转移”被当成“转移到某组”，两个本来可区分的状态被错误合并。

解决：签名里显式区分三类落点——-1表示无转移、具体的组号表示落进该组，并确保-1不与其他组号冲突（用负数最省事）。如果选了完全 DFA 的表示法，就不存在-1，但陷阱状态必须单独成组，不能和普通非接受态合并。

5.5 坑五：用未排序的 vector 当集合 key，导致同一集合被判成两个

现象：DFA 状态数比预期多，两个状态的转移行完全一致，但编号不同；最小化后它们才被合并，于是“最小化前多、最小化后正常”，让人误以为是子集构造的锅。

原因：集合用std::vector<int>存，std::map的 key 比较按字典序，{1,2}和{2,1}被当成两个不同的 key。只要闭包或 move 的构造顺序不稳定（比如遍历 ε 边的顺序依赖于输入顺序），同一个状态集就会拿到两个编号。

解决：要么在插入 map 之前对 vector 排序去重，要么直接用std::bitset<N>做 key（按位比较，天然规范）。用 bitset 还有个附带好处：调试时能一眼看出这个 DFA 状态对应哪几个 NFA 状态，比看一串数字直观得多。

6. 设计取舍：子集构造为什么在工程里常常“按需”而不是“全量”

写到这里，这条链的每个环节都摊开了：NFA 用邻接表存，闭包用位图预计算，子集构造用工作列表，最小化用划分细化。整套流程跑通之后，回头看会发现一个有点尴尬的事实——最耗时的往往不是算法本身，而是状态数。子集构造的 2^n 上界不是理论摆设，真实的词法规则集（几十条正则、含大量关键字前缀共享）经确定化后状态数上千很常见，全量构造再最小化，内存和启动时间都不好看。

工程上的主流做法是“按需确定化”：不预先展开整张 DFA 表，而是从初态的闭包开始，读到一个字符时才计算这一格转移，把结果缓存起来；跑一段输入之后，实际被访问到的 DFA 状态只是全量的一小部分。这就是所谓的惰性构造，它在保持 DFA 线性扫描优点的同时，把“最坏情况要 2^n 个状态”摊薄成了“实际用到几个算几个”。另一种思路是符号化：不以单个字符为转移单位，而以字符区间或字符类为单位，把转移表压成区间表，配合二分查找，表体积能小一个数量级。

那最小化还有没有用？有，但收益要算清楚。它换来的是更小的表、更好的缓存局部性，代价是一次全量分析。对于编译原理实验这种规模，最小化几乎是纯赚；对于一个要嵌入到编辑器里、每次击键都要重建状态机的场景，最小化就未必值得，惰性构造加缓存反而更划算。这个取舍没有标准答案，取决于你的状态机是“构造一次跑很久”还是“频繁重建跑很短”。

想验证自己的实现到底对不对，最省事的办法是写个几十行的对拍：随机生成长度 20 以内的字符串，分别用 NFA 的集合模拟和最终 DFA 的单状态模拟跑一遍，比对接受性；再拿最小化前后的 DFA 跑同一批串，确认接受性完全一致、状态数不增加。这个习惯我从第一次做这类实验就养成了——那会儿我图省事，直接拿一个样例串肉眼比对输出，结果交上去才发现带 ε 边的用例全错，连夜重写。从那以后我每次改完转移表，都强制走一遍随机对拍加可达性检查，宁可多花十分钟，也不吃回头改的后悔药。

如果你手上正缺一份能对着源码逐行看的实现，这份带实验报告的 NFA 转 DFA 并最小化的 C++ 代码，把上面这些结构、闭包、划分细化的细节都落成了可编译的代码，拿来对照着重写一遍，比自己从零试错快得多。希望帮到你。

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