简介本资源面向高校『编译原理』课程学习者聚焦自动机理论中的核心实验环节解决从非确定有限自动机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^nn 为 NFA 状态数因为每个 DFA 状态对应 NFA 状态集的一个子集。这个上界不是吓唬人的像(a|b)*a(a|b)^{k}这类正则最小 DFA 恰好需要 2^k 个状态任何算法都压不下去。所以“状态爆炸”不是你代码写错了而是问题本身的性质后面第 6 章会讲到工程上怎么绕。2.2 ε-闭包把“免费跳转”算进状态集合里ε 边是 NFA 里最容易被写错的部分。它表示“不读任何字符就能过去”所以在任何时刻机器实际可能处在的位置是从当前状态集合出发、沿任意条 ε 边能到达的全部状态。这个集合叫 ε-闭包记为 closure(S)它有三个必须记住的性质包含自身closure(S) ⊇ SS 里每个状态都在这一点漏掉就会出现“初态少了一个”的玄学 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::bitsetMAXN; // 位图表示 NFA 状态集合也就是一个 DFA 状态 std::mapStateSet, int id; // 集合 - DFA 状态编号同时兼任 visited std::queueStateSet work; // 待处理队列BFS 保证每个集合只展开一次 std::vectorstd::arrayint, 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。下面这组量级是这类实验里常见的示意不同实现会有出入但趋势一致规则形态NFA 状态数子集构造后最小化后标识符、整数常量10 以内10 以内与 NFA 相当(a|b)*abb1154(a|b)*a(a|b)^4约 12约 32约 32带大量 ε 分支的关键字集合数十数十可压缩 30%50%看这张表要抓住一点最小化对“本身就已经最小”的 DFA 毫无作用它压掉的是子集构造过程中产生的不可区分冗余而不是问题固有的复杂度。所以别指望最小化能救状态爆炸它救的是转移表体积和查表缓存命中率。3. ε-闭包与 move 的源码级实现闭包为什么必须用标记数组3.1 图的存储邻接表怎么分开存 ε 边和字符边NFA 就是一张有向图边分两类带字符的边和不带字符的 ε 边。最省事的存法是把两类边分开都做成邻接表std::vectorstd::vectorint epsEdge; // epsEdge[q]: q 经 ε 边直达的状态 std::vectorstd::arraystd::vectorint, SIGMA chEdge; // chEdge[q][c]: q 经字符 c 直达的状态为什么不用邻接矩阵因为 NFA 的边是稀疏的一个状态平均出边不到两条矩阵的 n² 空间里绝大部分是 0而且矩阵没法直接表达“一个状态对同一字符有多条出边”这件事除非你存 bool 矩阵再逐列扫描那反而更慢。用vectorvectorint还有一个隐性好处遍历某个状态的全部 ε 出边时内存是连续的缓存友好而arrayvectorint, SIGMA把字符维度摊平成下标省掉一次查 map 的开销这对 26 个字母或 128 个 ASCII 字符的字母表来说非常划算。需要留意的是SIGMA的定义方式。如果字母表直接从输入里扫出来字符到下标要做一次映射std::unordered_mapchar,int或直接unsigned char当下标如果偷懒按 ASCII 开 128 个槽转移表会大一圈但代码简单得多。实验里的规则集通常很小按 ASCII 开表是更稳的选择代价只是内存。3.2 闭包计算的不动点栈加 visited 标记ε-闭包本质是从一个集合出发做图可达性搜索用 DFS 或 BFS 都行关键是必须在入栈时就打标记而不是出栈时StateSet epsilonClosure(const StateSet S) { StateSet res S; // 闭包一定包含自身先并进来 std::stackint 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_nextMSVC或手写按 64 位字扫描跳过全零的字。3.4 常数优化利用闭包对并集的分配律预计算前面提过 closure(S ∪ T) closure(S) ∪ closure(T)这条性质可以直接换成性能每个单状态的 ε-闭包只跟图结构有关与构造过程无关完全可以预计算一次之后任何集合的闭包就是若干位图或起来。std::vectorStateSet 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 字节n500 时约 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::vectorint group(nDfa, 0); for (int i 0; i nDfa; i) group[i] isAccept[i] ? 1 : 0; // 初始两分 while (true) { std::mapstd::vectorint, int sig2id; // 签名 - 新组号 std::vectorint next(nDfa); for (int i 0; i nDfa; i) { std::vectorint 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::mapint, int gid2new; // 组号 - 新状态编号 std::vectorint rep; // 每组的代表元 for (int i 0; i nDfa; i) if (!gid2new.count(group[i])) { gid2new[group[i]] (int)rep.size(); rep.push_back(i); } std::vectorstd::arrayint, 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::vectorint存std::map的 key 比较按字典序{1,2}和{2,1}被当成两个不同的 key。只要闭包或 move 的构造顺序不稳定比如遍历 ε 边的顺序依赖于输入顺序同一个状态集就会拿到两个编号。解决要么在插入 map 之前对 vector 排序去重要么直接用std::bitsetN做 key按位比较天然规范。用 bitset 还有个附带好处调试时能一眼看出这个 DFA 状态对应哪几个 NFA 状态比看一串数字直观得多。6. 设计取舍子集构造为什么在工程里常常“按需”而不是“全量”写到这里这条链的每个环节都摊开了NFA 用邻接表存闭包用位图预计算子集构造用工作列表最小化用划分细化。整套流程跑通之后回头看会发现一个有点尴尬的事实——最耗时的往往不是算法本身而是状态数。子集构造的 2^n 上界不是理论摆设真实的词法规则集几十条正则、含大量关键字前缀共享经确定化后状态数上千很常见全量构造再最小化内存和启动时间都不好看。工程上的主流做法是“按需确定化”不预先展开整张 DFA 表而是从初态的闭包开始读到一个字符时才计算这一格转移把结果缓存起来跑一段输入之后实际被访问到的 DFA 状态只是全量的一小部分。这就是所谓的惰性构造它在保持 DFA 线性扫描优点的同时把“最坏情况要 2^n 个状态”摊薄成了“实际用到几个算几个”。另一种思路是符号化不以单个字符为转移单位而以字符区间或字符类为单位把转移表压成区间表配合二分查找表体积能小一个数量级。那最小化还有没有用有但收益要算清楚。它换来的是更小的表、更好的缓存局部性代价是一次全量分析。对于编译原理实验这种规模最小化几乎是纯赚对于一个要嵌入到编辑器里、每次击键都要重建状态机的场景最小化就未必值得惰性构造加缓存反而更划算。这个取舍没有标准答案取决于你的状态机是“构造一次跑很久”还是“频繁重建跑很短”。想验证自己的实现到底对不对最省事的办法是写个几十行的对拍随机生成长度 20 以内的字符串分别用 NFA 的集合模拟和最终 DFA 的单状态模拟跑一遍比对接受性再拿最小化前后的 DFA 跑同一批串确认接受性完全一致、状态数不增加。这个习惯我从第一次做这类实验就养成了——那会儿我图省事直接拿一个样例串肉眼比对输出结果交上去才发现带 ε 边的用例全错连夜重写。从那以后我每次改完转移表都强制走一遍随机对拍加可达性检查宁可多花十分钟也不吃回头改的后悔药。如果你手上正缺一份能对着源码逐行看的实现这份带实验报告的 NFA 转 DFA 并最小化的 C 代码把上面这些结构、闭包、划分细化的细节都落成了可编译的代码拿来对照着重写一遍比自己从零试错快得多。希望帮到你。本文还有配套的精品资源点击获取