企业官网建设流程全解析

简介：面向高校「编译原理」课程实验的NFA转DFA并最小化配套资料，内含可运行的C++实现与一份实验报告文档，适合正在完成课程实验、需要对照子集构造法与DFA最小化算法实现思路的本科生参考。压缩包共2个文件，以1份doc实验报告和1个cpp源文件为主，整体约722KB；报告记录实验目的、操作步骤与问题分析，源文件对应状态子集构造、状态合并及冗余状态消除等关键环节。已有416人学习下载。读者可据此获得从NFA到DFA再到最小化的完整实现路径，结合报告理解子集构造中状态数量膨胀的成因与优化取舍，并借鉴实验记录的组织方式与排错思路，用于课程提交前的自查和期末算法复习。

1. 状态集合的来源

编译原理课上用 C++ 写「NFA 转 DFA 并最小化」，第一次跑通的人常有同一个错觉：以为自己是在简化自动机，结果拿到的是一个比原图大好几倍的状态表——五六个状态的 NFA 转完变成二十几个 DFA 状态，最小化之后又缩回十几个。这个反差恰好说明整件事的性质：子集构造不是图变换，而是一次状态空间的展开，它把 NFA 里「同时可能在多个状态」这种不确定性，硬编码成 DFA 的一个个「状态集合」，确定性是用规模换来的；最小化则是把这笔规模账重新合并，把未来行为完全一致的状态压成一个。

这条链路上有两个问题必须搞清楚：不确定性到底是怎么被消掉的，状态等价到底是怎么被判定出来的。前者落在 ε-闭包和子集构造主循环上，后者落在划分细化上。下面从 ε-闭包为什么必须做成不动点、2 的 n 次方爆炸从哪儿来、Hopcroft 划分凭什么收敛，一路讲到代码里最容易翻车的几行。

2. ε-闭包：一条空边如何放大状态数

2.1 一个串在 NFA 上跑，跑出来的是一组状态

DFA 的语义是「给定当前状态和输入字符，下一个状态唯一」。NFA 不是这样：δ(q, a) 返回的是一个状态集合，而 ε 边允许在不消耗任何输入的情况下继续转移。所以对 NFA 来说，「当前配置」从来不是一个整数，而是一个状态集合。判定一个串是否被接受的规则是：从初始状态集合出发，每读一个字符就做一次集合到集合的迁移，读完之后这个集合与终态集有交集，就接受。

这就解释了为什么 DFA 的状态数会涨：DFA 要把「可能的当前集合」本身当成一个状态来对待，NFA 里 n 个状态能组合出的子集最多 2^n 个，DFA 的状态上界就是这么来的。

举一个具体例子。正则 (a|b)*abb 用 Thompson 构造法展开后大概有十几个状态，每条 ε 边都表示「不读字符也能走」。读完第一个 a 之后，你可能同时停在 3 到 5 个位置上，这些位置合起来才构成一次「合法的运行状态」。如果只取其中一个，下一步的迁移就会漏掉分支，接受串就会莫名其妙地少掉一批。

2.2 ε-闭包的本质是图上可达，而非反复迭代

ε-闭包 closure(S) 的定义是：从 S 中的任意状态出发，只经过 ε 边能够到达的所有状态的集合，且 S 本身必须包含在内。形式化地写，它是满足下面两条性质的最小集合：

• S ⊆ closure(S)；
• 若 p ∈ closure(S) 且存在 ε 边 p → q，则 q ∈ closure(S)。

很多人的第一反应是实现成「反复扫描所有 ε 边，直到某一轮没有新状态加入」，这个写法完全正确，但没必要。因为 ε 边构成一张有向图，closure(S) 就是这张图上从 S 出发的可达点集，一次深度优先或广度优先遍历就能求完，复杂度是 O(状态数 + ε 边数)。可达性天然满足「不动点」，因为你遍历到的每个点都会被处理一次，处理过的点不会再被压栈。

课程实验里 NFA 状态数一般不超过一两百，这个差别看不出来；但如果把同一套代码挪去做正则引擎，一个带几百个状态、上千条 ε 边的模式，反复扫描就会变成 O(n·m) 的重复劳动。

C++ 里的实现大致是这样：

const int MAXN = 256; // NFA 状态数上限，课程实验足够 std::vector<int> epsEdge[MAXN]; // epsEdge[u] = u 经 ε 边可达的状态列表 // 求状态集合 s 的 ε-闭包：从 s 里每个点出发做一次图遍历 std::bitset<MAXN> epsClosure(const std::bitset<MAXN>& s) { std::bitset<MAXN> res = s; // 闭包必须包含自身 std::vector<int> stk; for (int i = 0; i < MAXN; ++i) if (s[i]) stk.push_back(i); // 把所有起点压栈 while (!stk.empty()) { int u = stk.back(); stk.pop_back(); for (int v : epsEdge[u]) { if (!res[v]) { // 第一次到达才入栈 res[v] = 1; stk.push_back(v); } } } return res; // 已经是不动点，不需要再迭代 }

关键在if (!res[v])这一句：它保证每个状态最多入栈一次，栈的整体代价被压在 O(n + m)。把res初始化成s而不是全零，是另一个容易漏的点——如果忘了这一步，closure({q}) 可能不包含 q，后面判断终态时就会莫名其妙地漏。

2.3 move 和闭包的复合顺序不能反

消耗一个字符的完整语义是两步：先算出 move(T, a)，也就是集合 T 里每个状态经字符 a 的直接后继的并集；再对这个并集求 ε-闭包。写成公式就是 δ'(T, a) = ε-closure(move(T, a))。

顺序不能反的原因很直接：move 只走字符边，得到的集合可能立刻又能通过 ε 边走到别的状态，这些状态在下一步是被允许的，所以必须补上闭包。反过来的 move(closure(T), a) 在 T 本身已闭的情况下是等价的，但如果 T 没有闭过（比如你从某个中间变量直接拿来用），就会漏掉一批「先走 ε 再走 a」的路径。

在子集构造里，每个已经登记进 DFA 的状态集合都保证是闭的，所以 move 之前不需要再补一次闭包。这个不变量值得在代码里用注释标出来，否则后面加功能时很容易破坏它。

2.4 ε-闭包的幂等性，是后面所有正确性的地基

closure(closure(S)) = closure(S)，这条幂等性看着是废话，但它是子集构造能收敛的前提。因为子集构造每生成一个新集合都要补闭包，如果闭包不幂等，同一个「实际等价」的集合会被反复算成不同的位图，工作队列就永远排不空。

另一条性质是单调性：S ⊆ T 蕴含 closure(S) ⊆ closure(T)。它保证了子集构造的状态集合只增不减，也让后面做等价判定时能放心地用集合包含关系做剪枝。这两条性质在实验报告里往往被一句话带过，但它们才是「为什么这个算法一定能停机」的真正理由。

3. 子集构造法：DFA 状态如何被一组状态组合算出来

3.1 worklist 主循环：发现即编号

子集构造的核心结构只有三个：一张「状态集合 → DFA 编号」的映射表、一个待处理集合的队列、一张 DFA 转移表。算法本身就是在这个结构上跑一次广度优先搜索：

1. 把 NFA 初始状态的 ε-闭包作为 DFA 的初始状态，登记编号 0，入队；
2. 每次从队列取出一个集合 T，对每个输入字符 c 计算 ε-closure(move(T, c))；
3. 如果结果集合为空，说明这个字符在 T 上没有后继，转移记成死状态 -1；
4. 如果结果集合没登记过，就给它分配新编号并入队；
5. 把转移表里 T 对应的那一行填上目标编号。

关键在于「发现即编号」：编号是在第一次遇到某个集合时分配的，因此最终每个可达集合恰好对应一个 DFA 状态，不会重复也不会遗漏。遍历顺序只影响编号的先后，不影响最终识别的语言，这一点在做实验报告的状态对照表时很有用——换个顺序跑，表里的编号会变，但最小化之后的等价类划分是唯一的（后面会讲为什么）。

3.2 2 的 n 次方上界从哪儿来，现实中为什么没炸

理论上界 2^n 是紧的。经典构造是 L_k = {w | w 的倒数第 k 个字符是 a}，这个语言的最小 DFA 需要 2^k 个状态：因为它必须记住最近 k 个字符的完整历史。用 Thompson 构造出对应的 NFA 只有 O(k) 个状态，子集构造做完就会实打实地炸出 2^k 个状态。

现实里的词法规则不会这么写。标识符、数字、关键字、注释这些模式的结构都很「局部」，ε 边的分支深度有限，实际生成的 DFA 状态数通常只比 NFA 大几倍。但了解这个上界不是学术洁癖：它解释了为什么词法分析器生成器宁可把 DFA 完整算出来再压成表，也不在运行时现场算——因为现场算的最坏情况是不可控的，而词法分析是每个字符都要走一遍的热路径。

顺带说一句，最小化在这里的作用不只是「让状态表小一点」。子集构造会产生大量「行为相同但集合不同」的状态，比如两个集合只在某些永远走不到的 ε 分支上有差异，它们对任何输入后缀的反应完全一样。这些冗余状态如果不合并，转移表的每一行都要多存一份，cache 命中率会明显变差。

3.3 C++ 实现：用位图当 key 的取舍

状态集合最省事的表示是std::bitset<MAXN>。它的比较是按位字典序，天然可以作为std::map的键，不需要自己写哈希。代价是每次比较是 O(MAXN/64) 而不是 O(1)，当 DFA 状态数上千时，map 的 log 因子会开始显形。

std::map<std::bitset<MAXN>, int> id; // 集合 -> DFA 状态号 std::vector<std::array<int, 26>> trans; // DFA 转移表，-1 表示死状态 std::vector<char> isFinal; // DFA 终态标记 std::queue<std::bitset<MAXN>> work; // 初始集合：NFA 起点的 ε-闭包 std::bitset<MAXN> s0; s0[nfaStart] = 1; s0 = epsClosure(s0); id[s0] = 0; work.push(s0); trans.push_back({}); trans[0].fill(-1); isFinal.push_back((s0 & nfaFinal).any()); while (!work.empty()) { auto cur = work.front(); work.pop(); int u = id[cur]; for (int c = 0; c < sigma; ++c) { auto nxt = epsClosure(moveSet(cur, c)); // 先 move 再闭包 if (nxt.none()) { trans[u][c] = -1; continue; } // 无后继，记死状态 if (!id.count(nxt)) { // 新集合，登记并入队 int v = (int)id.size(); id[nxt] = v; trans.push_back({}); trans[v].fill(-1); isFinal.push_back((nxt & nfaFinal).any()); // 与终态集有交集即终态 work.push(nxt); } trans[u][c] = id[nxt]; } }

这里有几个细节值得单独看：

isFinal的判定用的是(nxt & nfaFinal).any()，也就是「集合里存在至少一个 NFA 终态」。写成「全部都是终态」或者「取集合里编号最小的那个判断」都会错，因为 NFA 的接受定义是存在一条路径，不是所有路径。

trans[u][c] = -1表示死状态。有的实现会专门造一个「陷阱状态」把所有缺失转移都指向它，好处是转移表变整齐、最小化时可以把它一起参与划分；坏处是多一个状态，而且如果这个陷阱状态不可达（比如某些字符在初始集合上就没有后继），它反而会干扰最小化的结果。

如果实验规模大一点，可以把std::map换成std::unordered_map配自定义哈希：把 bitset 按 64 位分块，用to_ullong逐块取出后拼一个哈希值，或者干脆to_string()之后哈希字符串。后者写起来最快，代价是每次查找都要分配一个长度 MAXN 的字符串，实测在几千状态的规模下反而不如 map。

3.4 状态集合的表示方式对比

第三种方案是坑最多的：vector<int>作为键必须保证元素有序且去重，否则 {1,3} 和 {3,1} 会被当成两个不同的集合，DFA 状态数会凭空翻倍。这个坑后面还会单独说。

4. DFA 最小化：划分细化为什么能收敛到唯一结果

4.1 等价状态的定义：未来行为完全一致

两个 DFA 状态 p、q 等价，当且仅当对任意输入串 w，δ(p, w) 是终态与 δ(q, w) 是终态同时成立或同时不成立。换句话说，从 p 和 q 出发，接受的语言完全相同。

这个定义有一个非常重要的性质：它是「右不变」的。也就是说，如果 p 和 q 等价，那么对任意字符 a，δ(p, a) 和 δ(q, a) 也必须等价。这条性质直接给出了最小化的算法骨架——先把状态分成「显然不等价」的粗块，再反复利用右不变性把块切细，直到不能再切。

最小 DFA 的唯一性来自 Myhill-Nerode 定理：一个正则语言对应的右不变等价关系的索引（等价类的个数）是唯一的，所以最小 DFA 在同构意义下唯一。这也解释了为什么前面说遍历顺序不影响最终结果——子集构造出来的 DFA 可能长得不一样，但最小化之后一定是同一张图，只是状态编号可能不同。

4.2 初始划分：为什么终态和非终态必须分开

初始划分只有两块：终态集合 F 和 非终态集合 Q\F。理由是对空串 ε 的接受性不同——终态接受 ε，非终态不接受。而 ε 也是一个合法的输入串（长度为零），所以这两块的状态一定不等价，必须分开。

如果这一步偷懒，把所有状态放进一个块里再从转移上细分，算法仍然能跑出正确结果，因为细分过程本身会发现终态和非终态的区别，但会多跑几轮。

不可达状态要在这之前就删掉。一个状态如果从初始状态出发永远走不到，它参不参与划分都不影响语言，但会影响「最小 DFA 状态数」这个指标。实验报告里如果写了「最小化后状态数从 24 降到 11」，而这个 24 里含了 3 个不可达状态，那这个数字就是不准确的。删不可达的标准做法是从起点做一次 BFS，标记所有能到达的状态，其余的直接丢弃。

4.3 划分细化的实现：用签名重新编号

最直观的实现是每一轮给每个状态算一个「签名」，签名相同就归为同一类，然后用签名重新编号。签名由两部分组成：当前所属的组号，以及对每个输入字符的去向状态所属的组号。

// cls[s] = 状态 s 所属的等价类编号，-1 表示不可达 // 初始：可达终态 = 1，可达非终态 = 0 std::vector<int> cls(n, -1); for (int s = 0; s < n; ++s) if (reach[s]) cls[s] = isFinal[s] ? 1 : 0; int groupCnt = 0; for (int s = 0; s < n; ++s) groupCnt = std::max(groupCnt, cls[s] + 1); while (true) { std::map<std::vector<int>, int> sig2id; std::vector<int> nxt(n, -1); for (int s = 0; s < n; ++s) { if (cls[s] < 0) continue; // 不可达状态不参与 std::vector<int> sig; sig.push_back(cls[s]); // 第一维带旧组号：保证只细分不合并 for (int c = 0; c < sigma; ++c) { int t = trans[s][c]; sig.push_back(t < 0 ? -1 : cls[t]); // 去向为空则统一记 -1 } auto it = sig2id.find(sig); if (it == sig2id.end()) { int k = (int)sig2id.size(); sig2id[sig] = k; nxt[s] = k; } else { nxt[s] = it->second; } } if ((int)sig2id.size() == groupCnt) break; // 组数不再增加，划分稳定 cls.swap(nxt); groupCnt = (int)sig2id.size(); }

sig.push_back(cls[s])这一行是正确性的关键。如果签名里不带旧组号，算法就变成「按转移去向重新归类」，两种原本已经分开的状态可能因为去向恰好相同而被合回一类，划分就不再单调细化，可能反复震荡不收敛。带上旧组号之后，签名相同必然意味着旧组号也相同，所以新划分一定是对旧划分的细分，组数单调不减，最多 n 轮必然稳定。

收敛判据用的是「组数不再增加」，而不是「新编号和旧编号完全相同」。原因是每轮重新编号是从 0 开始按签名首次出现的顺序分配的，编号本身会变，但划分结构不变。比较组数是可靠且便宜的判断方式。

4.4 Hopcroft 的 O(n log n)：只处理较小的一块

上面这个写法的复杂度是 O(n²·|Σ|·log)，因为每一轮都要遍历所有状态，而轮数最多 n。Hopcroft 的改进思路是把「分裂者」放进一个待处理集合里，并且每次分裂时只把较小的那一块加入待处理集合。

为什么只处理较小的一块是对的：假设一个块 P 被字符 a 分裂成 P1 和 P2，那么对于任何需要靠 a 来区分状态的其他块 Q，用 P1 当分裂者还是用 P2 当分裂者，得到的分裂结果是相同的——因为 Q 的状态要么经过 a 落到 P1，要么落到 P2，两者互补。所以只保留小的那一块，信息不丢失。

复杂度分析的关键在于：每个状态每次被「较小的那一块」处理时，它所在块的大小至少翻倍，所以每个状态最多被处理 O(log n) 次，总复杂度 O(|Σ|·n log n)。这个证明在实验报告里值得单独写一段，因为它体现了「用划分大小做摊还」这个思路，和并查集的按秩合并是同一类技巧。

在这个规模下，朴素划分和 Hopcroft 的实测差距其实不明显（状态数几百时都是毫秒级），但如果把代码留下来当工具用，处理几千个状态的自动机时差距会拉到几十倍。

5. 避坑与排查：五个让实验返工的地方

5.1 坑一：ε-闭包只算了一层

现象：用几个短串测试都对，换成带嵌套分支的正则就漏接受，具体表现是某些本该被接受的串被判成拒绝，而且漏的串往往和「连续两个 ε 边」有关。

原因：把闭包实现成了「遍历 S 中每个状态的直接 ε 后继」，只做了一层扩展。可 ε 边是可以串联的，q1 →ε q2 →ε q3 这种路径只走一层就到不了 q3。

解决：改成栈式图遍历（就是 2.2 那段代码），并且用一个 visited 位图防止重复入栈。验证方法是手工构造一条长度大于 2 的 ε 链，检查 closure 的结果是否包含链尾。

5.2 坑二：初始状态忘了求闭包

现象：所有以空串开头的匹配全错，比如正则 a* 居然不接受空串，或者接受串集合整体偏移了一个字符。

原因：直接把 NFA 的起始状态当成 DFA 的初始集合，写成s0[nfaStart] = 1之后就登记入队，忘了外面再套一层epsClosure。如果 NFA 的起始状态有一条 ε 边直接通向终态（Thompson 构造里 a* 就会有这种情况），这个终态就永远不会出现在初始集合里。

解决：初始集合一定要写成epsClosure(singleton(nfaStart))。这条在代码里最好单独抽一行加注释，因为它只出现一次，出错之后很难通过读代码发现。

5.3 坑三：终态判定写成了「全部都是终态」

现象：DFA 的终态数量明显偏少，很多应该被接受的串被判成拒绝，而且测试用例里凡是「同时停在多个状态」的情况都出错。

原因：判断一个状态集合是不是终态时，写成了遍历集合、要求每个元素都在 NFA 终态集里。但 NFA 的接受定义是「存在一条到达终态的路径」，只要集合里有一个终态就够了。

解决：改成(set & nfaFinal).any()或者等价的「存在性判断」。这个 bug 的隐蔽之处在于，简单的正则（没有分支）跑起来完全正常，只有出现 | 运算产生分支之后才暴露。

5.4 坑四：最小化前没删不可达状态

现象：最小化之后的状态数比手算结果多，而且多出来的那些状态在转移表里全是死循环，从起点出发根本走不到。

原因：子集构造时如果对空集也做了登记（比如把nxt.none()的情况也当成一个合法集合分配了编号），或者 NFA 本身就含有从起点不可达的状态，DFA 里就会混入不可达状态。划分算法会把这些状态也分到某个等价类里，导致最终状态数偏大。

解决：最小化之前先做一次从起点的 BFS，标记所有可达状态，不可达的直接标成 -1 排除在划分之外。另外，如果确实需要陷阱状态（为了转移表整齐），要明确它是「可达的」还是「人为补的」，两者在统计状态数时不能混为一谈。

5.5 坑五：用 vector 当 key 却没排序

现象：DFA 状态数比预期多出一大截，而且仔细看转移表，会发现有两行内容完全一样，只是编号不同。最小化之后它们会被合并，但最小化之前的状态数统计就完全失真了。

原因：用std::vector<int>表示状态集合并直接塞进std::map，没有保证元素有序。{1, 3} 和 {3, 1} 在 vector 的字典序比较下是不相等的，于是同一个集合被登记了两次。

解决：在插入 map 之前统一std::sort加std::unique，或者干脆换成std::bitset/std::set。这类 bug 最麻烦的地方是它不会让结果错，只会让规模错，所以靠「跑测试用例」是发现不了的，必须靠打印状态数并和手算对照。

6. 设计取舍：全量构造还是按需构造，以及如何验证最小性

子集构造有两种用法，取舍完全不同。全量构造就是前面写的做法：把所有可达集合一次性算完，得到完整转移表。词法分析器生成器走的是这条路，因为生成的代码要能在 O(1) 时间里查表跳转，表必须在编译期就准备好。另一种是按需构造（惰性构造），只在真正遇到某个字符时才计算下一个集合，正则表达式引擎大多这么做——因为实际输入往往只覆盖状态空间的一小部分，全量算出来纯属浪费，而按需构造能把内存压到和输入长度相关。

按需构造的代价是每次状态迁移都要现场算闭包，热路径上会有额外开销，所以通常会配一层缓存（用集合的哈希值做键）。这也是为什么很多引擎在长文本上跑得飞快，在短文本上反而不如查表——缓存还没热起来，构造的开销就占了大头。

最小化这边也有取舍。朴素划分细化写起来十行代码，正确性一眼能看懂，几百个状态以内完全够用；Hopcroft 的常数更大，实现里要维护分裂者队列和「较小块」的判断，一旦写错很难调试，只有在状态数上千时才有明显收益。课程实验里我更倾向先写朴素版跑通，再用 Hopcroft 做一次对拍，两边结果的状态数必须一致——这本身就是最好的正确性验证。

验证最小性有几个可操作的手段。最直接的是检查每个等价类内部的一致性：对每个类里的任意两个状态，对每个输入字符，它们的目标状态必须落在同一个类里，且终态标记相同。这个检查是 O(n·|Σ|) 的，写起来只要几行。另一个手段是 Brzozowski 的双重最小化：把 DFA 反转成 NFA、确定化、再反转、再确定化，得到的一定是最小 DFA，和直接最小化的结果做同构比较。这个方法在理论上很漂亮，但实现里要处理反转后多起点的确定化，代码量不小，一般只在写工具时才值得。最省事的还是随机对拍：生成一批随机串，分别在最小化前后的 DFA 上跑，接受结果必须完全一致。

我自己的血泪经验是：最小化写完之后，一定要用「最小化前后随机串对拍」跑一遍，而且随机串里必须包含空串和长度很短的串。有一次我把初始划分的终态标记写反了，长串测试全过，因为长串基本都会落到确定的终态上；偏偏是所有涉及空串和单字符的用例集体翻车，而我当时的测试集里最短的串长度是 3。

从那以后我每次做完自动机相关的转换，都强制走一遍「空串 + 长度 1 到 3 的全枚举 + 随机长串」三段式验证，不管前面手算得多有把握。希望帮到你。

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