简介面向高校「编译原理」课程实验的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::vectorint epsEdge[MAXN]; // epsEdge[u] u 经 ε 边可达的状态列表 // 求状态集合 s 的 ε-闭包从 s 里每个点出发做一次图遍历 std::bitsetMAXN epsClosure(const std::bitsetMAXN s) { std::bitsetMAXN res s; // 闭包必须包含自身 std::vectorint 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 转移表。算法本身就是在这个结构上跑一次广度优先搜索把 NFA 初始状态的 ε-闭包作为 DFA 的初始状态登记编号 0入队每次从队列取出一个集合 T对每个输入字符 c 计算 ε-closure(move(T, c))如果结果集合为空说明这个字符在 T 上没有后继转移记成死状态 -1如果结果集合没登记过就给它分配新编号并入队把转移表里 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::bitsetMAXN。它的比较是按位字典序天然可以作为std::map的键不需要自己写哈希。代价是每次比较是 O(MAXN/64) 而不是 O(1)当 DFA 状态数上千时map 的 log 因子会开始显形。std::mapstd::bitsetMAXN, int id; // 集合 - DFA 状态号 std::vectorstd::arrayint, 26 trans; // DFA 转移表-1 表示死状态 std::vectorchar isFinal; // DFA 终态标记 std::queuestd::bitsetMAXN work; // 初始集合NFA 起点的 ε-闭包 std::bitsetMAXN 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 状态集合的表示方式对比表示方式比较/哈希代价适用规模备注std::bitsetNstd::mapO(N/64) 比较log 因子状态数几百到几千代码最短无需自定义哈希std::bitsetN 自定义哈希O(N/64) 哈希均摊 O(1)状态数上万要处理哈希碰撞代码量翻倍排序后的std::vectorintO(k log k) 比较集合稀疏时更省必须保证有序否则同一集合会有两个键位图 手写开放寻址最低极限性能场景调试成本高课程实验没必要第三种方案是坑最多的vectorint作为键必须保证元素有序且去重否则 {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::vectorint 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::mapstd::vectorint, int sig2id; std::vectorint nxt(n, -1); for (int s 0; s n; s) { if (cls[s] 0) continue; // 不可达状态不参与 std::vectorint 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::vectorint表示状态集合并直接塞进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 上跑接受结果必须完全一致。方案实现成本适用状态数主要风险朴素划分细化低几百以内轮数多时变慢但结果正确Hopcroft中上千以上分裂者队列维护错会导致漏分裂Brzozowski 双重最小化高任意反转确定化的实现容易出边界错误随机串对拍很低任意只能证伪不能证明我自己的血泪经验是最小化写完之后一定要用「最小化前后随机串对拍」跑一遍而且随机串里必须包含空串和长度很短的串。有一次我把初始划分的终态标记写反了长串测试全过因为长串基本都会落到确定的终态上偏偏是所有涉及空串和单字符的用例集体翻车而我当时的测试集里最短的串长度是 3。从那以后我每次做完自动机相关的转换都强制走一遍「空串 长度 1 到 3 的全枚举 随机长串」三段式验证不管前面手算得多有把握。希望帮到你。本文还有配套的精品资源点击获取