企业官网建设流程全解析

简介：面向高校编译原理课程实验的「NFA转DFA并最小化」配套材料，适合正在学习自动机理论、需要完成子集构造法与DFA最小化实验的本科生参考，尤其对ZZU相关课程的学生有较强针对性。压缩包共2个文件，由1份doc实验报告和1份cpp源码组成，整体约722KB，体量轻便，便于对照阅读与本地编译调试；源码侧重算法实现，实验报告侧重过程记录与结果分析。代码用C++实现NFA到DFA的转换及最小化流程，实验报告围绕实验目的、步骤、遇到的问题与解决方案展开，可帮助读者理解状态子集构造、冗余与不可达状态识别合并等关键环节。已有416人学习，说明其在课程实验场景中具有一定参考价值；读者可据此梳理词法分析相关的自动机思路、核对实验报告结构，并借助源码排查实现细节与调试难点。

1. 从一道手算题说起：这套 NFA→DFA→最小化方案覆盖到什么程度

编译原理实验里，NFA 转 DFA 并最小化这道题有个很有意思的现象：老师布置的三状态手算题，几乎所有人都能做对；一旦换成十来个状态、带 ε 边的自动机，就有人开始在草稿纸上画圈，画到子集构造第三轮时对不上号，最小化的划分表填到一半直接推倒重来。这套方案要解决的正是这件事——把 NFA→DFA 子集构造→DFA 最小化整条链路的 C++ 实现和配套实验报告一起交付：输入是一张转移表文本，输出是可以逐行核对的 DFA 转移表、最小化后的状态对照关系，以及一组测试串的接受/拒绝记录。

它适合两类人：正在做编译原理课程设计、需要交代码和报告的本科生，以及想找一份能直接跑起来、后面还能改造成词法分析器状态机的参考实现的人。整篇文章按「需求怎么定 → 数据结构怎么选 → 两个核心算法怎么落地 → 哪里容易翻车 → 怎么验收」的顺序展开，代码可以直接编译运行，报告部分的结构也能照着填。

2. 总体设计：状态机数据结构与四个模块的职责划分

动手写代码之前，先要决定状态集合用什么表示。这个决定看起来不起眼，实际上会一路影响到最小化那一步能不能写得干净。我见过不少实现用set<int>存状态集合，逻辑完全正确，但子集构造主循环里每做一次move就要建几十个临时 set、再比较、再插入 map，跑一个二十状态的自动机就开始卡；调试时打印一个集合还要手写循环。所以这套方案的第一个设计决定是：状态集合一律用位集。

2.1 为什么用位集存状态集合：把集合运算压成一次按位操作

编译原理实验涉及的自动机规模通常不大，状态数几十个顶天了。这个量级下，std::bitset<128>是最划算的选择：求并集是|，判断包含是&后比较，判断相等直接==，判空是.none()，塞进map当键还能直接用operator<（C++11 起bitset提供了字典序比较）。整套算法里最频繁的两个操作是「两个集合求并」和「集合去重」，位集把这两个操作的常数压到了几乎可以忽略的程度。

#include <bitset> #include <map> #include <queue> #include <vector> #include <string> const int MAXN = 128; // 状态数上限，超了要改这个常量 using SSet = std::bitset<MAXN>; // 一个位集就是一个状态集合 struct NFA { int n; // 状态总数，编号 0..n-1 std::string alphabet; // 字母表，例如 "ab" int start; // 初态编号 std::vector<bool> accept; // accept[i] 为真表示 i 是终态 std::vector<std::map<char, std::vector<int>>> move; // 字符转移 std::vector<std::vector<int>> eps; // ε 直接后继 }; struct DFA { int n; int start; std::vector<bool> accept; std::vector<std::map<char, int>> trans; // trans[s][c] = 后继状态编号 };

NFA里为什么用map<char, vector<int>>而不是二维数组？因为字母表是运行时读进来的，用数组就得写死[MAXN][26]，遇到数字字母混合的 token 还要重新改。map的查找是 O(log 26)，在这个规模下完全无感，换来的是「来什么字符集都能跑」。eps单独拆出来是因为 ε 边不做符号匹配，它只在求闭包的时候用，混在move里会让后续每个循环都要多一次if (c == '#')判断，反而是噪音。

提示：MAXN设成 128 是基于课程实验的常见规模。如果你要做一个小型词法分析器，关键字加运算符的状态数可能逼近这个值，建议直接改成 512 或改用std::vector<bool>动态位集，代价是map键需要自定义比较器。

2.2 四个模块的输入输出契约

整套程序拆成四个函数，每个函数的输入输出都在下面这张表里定死，主函数只负责把数据在它们之间传递，不掺任何算法逻辑。这样拆的好处是：调试时能单独把某一个阶段的输出打到文件里，跟手算结果逐行对，不用在整个流程里下断点。

注意epsilonClosure的第二个参数是「集合」而不是「单个状态」。这个签名是有意为之的：子集构造里每次求闭包的对象都是一个move之后得到的集合，如果只能传单个状态，调用方就得自己写循环再求并集，闭包的逻辑就会散到两个地方，后面排查「为什么少了一条边」的时候根本找不到源头。

runDFA单独抽出来是为了验收。最小化前后各跑一遍同一批测试串，结果全一致才算通过——这比肉眼比对两张转移表可靠得多，具体做法放在最后一章讲。

2.3 输入文件格式：把正则表达式落到一张转移表上

自动机的来源通常是 Thompson 构造，但实验报告里一般会直接给一张表。这套方案读的是一份纯文本，格式如下：

# 第一行：状态数 字母表 初态 终态个数 终态列表... 5 ab 0 2 3 4 # 之后每行三个字段：源状态 符号 目标状态，符号写 # 表示 ε 0 # 1 1 # 2 2 a 3 0 b 4

这份文件描述的语言很简单：从 0 出发，先走 ε 链到 2 再读一个a到终态 3，或者直接读一个b到终态 4，能接受的串就是a和b两个。选这么个小例子是有意的——状态少，你可以在纸上把子集构造的每一步都算出来，跟程序输出对照；同时它又同时包含了 ε 链和两个终态，最小化那一步能把两个终态合并成一个，正好把整条链路都验证一遍。

解析函数不到二十行：

NFA parseNFA(const std::string& path) { std::ifstream fin(path); NFA nfa; int k = 0; fin >> nfa.n >> nfa.alphabet >> nfa.start >> k; nfa.move.resize(nfa.n); nfa.eps.resize(nfa.n); nfa.accept.assign(nfa.n, false); for (int i = 0; i < k; ++i) { int f; fin >> f; nfa.accept[f] = true; } int from = 0, to = 0; std::string sym; while (fin >> from >> sym >> to) { // >> 自动跳过换行和空格 if (sym == "#") nfa.eps[from].push_back(to); else nfa.move[from][sym[0]].push_back(to); } return nfa; }

用>>读而不是按行getline再切分，是因为这个格式里换行没有语义，纯粹是给人看的排版。>>天然跳过所有空白字符，#那一行注释也不会被误读——解析器里根本没处理#开头的整行，所以第一行注释行会被fin >> nfa.n直接跳过吗？不会。>>读整数时遇到#会失败并置位 failbit。

所以实际交付的版本里，我在main开头加了一句跳过注释的逻辑：

// 跳过文件开头的 # 注释行 std::string line; while (std::getline(fin, line) && !line.empty() && line[0] == '#') { /* 丢弃 */ }

这里踩过一次坑：早期版本注释行写在中间，while (fin >> ...)读到#就停，后面的转移全部丢失，程序不报错，只是静默地少读了半张表，输出结果看着像模像样，其实是错的。后来干脆约定注释只能写在文件头，中间不允许出现，解析器里也只处理头部那一小段。

3. 子集构造的实现：ε-闭包、move 与状态编号管理

子集构造法的教科书描述只有三行：从初态的 ε 闭包开始，对每个已生成的子集和每个输入字符求 move 再求闭包，新出现的子集入队，直到队列空。但真写起来，三行变三十行，问题主要集中在两处：闭包怎么写才不会重复入栈，以及新子集怎么编号才不会跟已有状态撞车。

3.1 ε-闭包：一个带栈的图遍历

ε 闭包的本质是从给定集合出发，沿 ε 边做一次可达性搜索，把所有能到的状态并进来。因为 ε 边可能成环（Thompson 构造里(a|b)*那一段就是环），不能简单递归，得用显式的栈配合「已访问」标记。

SSet epsilonClosure(const NFA& nfa, const SSet& s) { SSet res = s; // 集合自身一定在闭包里 std::vector<int> stk; for (int i = 0; i < nfa.n; ++i) if (s[i]) stk.push_back(i); // 初始集合的元素全部入栈 while (!stk.empty()) { int u = stk.back(); stk.pop_back(); for (int v : nfa.eps[u]) { if (!res[v]) { // 只有第一次到达才入栈 res[v] = 1; stk.push_back(v); } } } return res; }

关键在if (!res[v])这个判断：标记和入栈是同一时刻完成的。如果写成「先全部入栈，出栈时再判断是否访问过」，那么一个状态可能在标记之前被多个前驱重复压栈，栈深度会膨胀到边数的平方级，环上更会直接爆掉。这个写法保证每个状态最多入栈一次，整体复杂度是 O(状态数 + ε 边数)。

还有一个容易忽略的点：res的初始值是s本身，不是空集。求闭包的意思是「从这些状态出发能到达的所有状态，包括它们自己」。我见过把初始值设成空集、然后只把 ε 后继加进去的写法，结果初态自己不在自己的闭包里，子集构造的起始状态就错了，后面全盘皆输。

3.2 子集构造主循环：为什么空集不建状态

主循环用一个map<SSet, int>维护「子集 → DFA 状态编号」的映射，同时用一个vector<SSet>维护反向映射，队列里存的是 DFA 状态编号。每次取出一个状态，对它代表的子集在字母表上逐个字符求 move，再求闭包，查表决定是复用已有编号还是新建。

DFA subsetConstruct(const NFA& nfa) { DFA dfa; dfa.n = 0; std::map<SSet, int> id; // 子集 -> DFA 状态编号 std::vector<SSet> sets; // DFA 状态编号 -> 子集 std::queue<int> q; SSet init; init[nfa.start] = 1; SSet startSet = epsilonClosure(nfa, init); id[startSet] = dfa.n++; sets.push_back(startSet); dfa.trans.push_back({}); q.push(0); while (!q.empty()) { int u = q.front(); q.pop_front(); SSet cur = sets[u]; for (char c : nfa.alphabet) { SSet nxt; // move(cur, c) for (int i = 0; i < nfa.n; ++i) { if (!cur[i]) continue; auto it = nfa.move[i].find(c); if (it == nfa.move[i].end()) continue; for (int v : it->second) nxt[v] = 1; } if (nxt.none()) continue; // 空集不产生新状态 SSet closure = epsilonClosure(nfa, nxt); if (!id.count(closure)) { id[closure] = dfa.n++; sets.push_back(closure); dfa.trans.push_back({}); q.push(id[closure]); } dfa.trans[u][c] = id[closure]; } } dfa.start = 0; dfa.accept.assign(dfa.n, false); for (int i = 0; i < dfa.n; ++i) for (int j = 0; j < nfa.n; ++j) if (sets[i][j] && nfa.accept[j]) { dfa.accept[i] = true; break; } return dfa; }

if (nxt.none()) continue;这行是整个函数里最值得说明的一处。课本上的子集构造法确实会为「死状态」∅ 建一个状态，它的所有转移都指向自己。但工程实现里通常不建：一个转移缺失就代表「读到这个字符后进入死状态」，runDFA里查trans[cur].find(c)找不到就直接返回 false，效果完全等价，而状态表少一行、最小化少一个等价类。两种做法都对，选哪种取决于输出格式——如果实验报告要求画出完整转移表、包括死状态那一行，就得老老实实建出来；如果只是要一份能跑的 DFA，不建更省事。

dfa.trans.push_back({})出现的时机也要注意：它必须和dfa.n++、sets.push_back()在同一时刻发生，三者的下标才能保持对齐。我在第一版里把dfa.trans的扩容写在循环外面，用trans.resize(MAXN)预分配，结果后面输出转移表时按dfa.n去遍历，是对的；但一拍脑袋改成trans.resize(32)，状态数一多就越界了。现在这个「哪里加状态就在哪里扩容」的写法，虽然多两行，但不会出现下标对不齐的问题。

3.3 状态重命名与转移表输出

子集构造产出的状态编号是按发现顺序分配的，跟原 NFA 的编号没有任何关系，直接打出来是一堆数字，没法跟手算结果对照。通常的做法是额外输出一张对照表，把每个 DFA 状态编号映射回它代表的状态集合。

void printDFA(const DFA& dfa, const std::string& alphabet, const std::vector<SSet>& sets, const std::string& title) { std::cout << "=== " << title << " ===\n"; std::cout << "状态数: " << dfa.n << " 初态: " << dfa.start << "\n"; std::cout << "状态\t集合\t\t"; for (char c : alphabet) std::cout << c << "\t"; std::cout << "\n"; for (int i = 0; i < dfa.n; ++i) { std::cout << (dfa.accept[i] ? "*" : " ") << i << "\t"; if (sets.empty()) { std::cout << "-\t\t"; // 最小化后集合已合并不再显示 } else { std::string s = "{"; for (int j = 0; j < MAXN; ++j) if (sets[i][j]) s += std::to_string(j) + ","; if (s.size() > 1) s.pop_back(); s += "}"; std::cout << s << "\t"; } for (char c : alphabet) { auto it = dfa.trans[i].find(c); std::cout << (it == dfa.trans[i].end() ? "-" : std::to_string(it->second)) << "\t"; } std::cout << "\n"; } }

拿 2.3 节那份输入跑一遍，子集构造的输出是三个状态：{0,1,2}、{3}、{4}，前者的a和b分别指向后两者，后两者都没有出边。这个结果跟自己纸上算的完全对得上，说明子集构造这一层通了。接下来最小化会把{3}和{4}合并——它们都接受、都没有出边，对任何后续输入的反应完全一样。

注意：对照表里打印状态集合时会遍历到MAXN，如果状态数不大但MAXN设得很高，每行会有一大截空白。调试阶段无所谓，正式输出时把上界改成nfa.n即可。

4. DFA 最小化实现：初始划分与签名迭代

最小化的经典算法有 Hopcroft 的 O(n log n) 版本，但那个版本要维护「等待集合」和「被拆分块」的逆向索引，代码量是划分法的三倍以上，调试难度也高一个量级。课程实验的 DFA 规模小，通常的做法是用朴素的等价类划分：先按终态/非终态分两组，然后反复用「每个状态在各字符上的后继落在哪个组」作为签名去细化分组，直到分组数不再变化。思路直白，代码不到四十行，出错也好定位。

4.1 初始划分：只分终态和非终态

等价类划分的起点只有一个约束：终态和非终态一定不等价。因为终态接受空串、非终态不接受，这就是一个可区分的证据。所以初始分组只有两类，用一个vector<int>存每个状态所属的组号：

int n = dfa.n; std::vector<int> group(n, 0); for (int i = 0; i < n; ++i) group[i] = dfa.accept[i] ? 1 : 0; // 0 = 非终态组，1 = 终态组

组号本身没有意义，它只是个标签，用来在下一步判断「两个状态的后继是不是落在同一个组」。这一点很关键：很多实现到这里会额外维护一个vector<vector<int>>存每组包含哪些状态，然后每次细化都要重建，代码量翻倍还容易漏。其实完全可以不维护——签名里只用到「组号」这一个整数，状态到组号的映射一个数组就够了。

4.2 用签名细化：一次遍历完成一次拆分

细化的核心是给每个状态算一个签名，签名由「自己当前所属的组号」加上「在每个输入字符上的后继所属的组号」组成，签名相同的状态归为一组。这里有个细节：签名里必须带上当前组号，否则一个原本在非终态组的状态，可能因为后继组号组合恰好相同而被合并进终态组。这是我曾经翻过车的地方，后面第 5 章会展开讲。

bool changed = true; while (changed) { changed = false; std::map<std::vector<int>, int> sig2id; std::vector<int> newGroup(n, 0); int cnt = 0; for (int i = 0; i < n; ++i) { std::vector<int> sig; sig.push_back(group[i]); // 当前组号参与签名 for (char c : alphabet) { auto it = dfa.trans[i].find(c); sig.push_back(it == dfa.trans[i].end() ? -1 : group[it->second]); } auto it = sig2id.find(sig); if (it == sig2id.end()) { sig2id[sig] = cnt; newGroup[i] = cnt++; } else { newGroup[i] = it->second; } } int oldCnt = 0; for (int g : group) oldCnt = std::max(oldCnt, g + 1); if (cnt != oldCnt) changed = true; // 组数变了说明还在拆分 group = newGroup; }

-1这个哨兵值代表「该字符上没有转移」。为什么要单独用一个值而不是用某个特赦组号？因为缺失转移和「转移到某个具体组」是两种不同的行为，前者在任何输入下都拒绝，后者可能接受也可能拒绝，混在一起会让两个本该分开的状态被误合并。用一个不可能出现的负数做哨兵，签名比较时自然就区分开了。

终止条件是cnt != oldCnt。划分只会拆分不会合并，所以组数单调不减；组数不变就意味着这一轮没有任何拆分，已经到达最细划分。反过来，如果用「新旧group数组是否完全相同」做判据，就会陷入死循环——每次重新分配组号后，即使划分没变，组号的数值也可能整体变换（比如原来的[0,1,0,2]变成[0,1,0,2]但下一轮变成[0,2,0,1]），数组比较永远不相等。组数判据没有这个问题。

4.3 重建最小 DFA 与不可达状态清理

划分定下来之后，每个组就是一状态，组号就是新状态编号。重建的时候遍历原 DFA 的每条转移，把源和目标的组号取出来作为新转移：

DFA minimizeDFA(const DFA& dfa, const std::string& alphabet) { // ... 上一节的划分代码，得到 group 和组数 k ... int k = 0; for (int g : group) k = std::max(k, g + 1); DFA out; out.n = k; out.trans.resize(k); out.accept.assign(k, false); for (int i = 0; i < dfa.n; ++i) { if (dfa.accept[i]) out.accept[group[i]] = true; for (const auto& kv : dfa.trans[i]) { out.trans[group[i]][kv.first] = group[kv.second]; } } out.start = group[dfa.start]; return out; }

out.accept[group[i]] = true这一句要在遍历过程中逐状态执行，不能只在某个代表状态上设一次。因为一个组里只要有一个原状态是终态，整个组就是终态——这是划分算法保证的，同一组内不可能既有终态又有非终态。写成逐状态赋值，即使前面划分哪里出了偏差，至少终态标记不会丢。

out.start = group[dfa.start]也要用组号，不能直接用dfa.start。原 DFA 的初态编号在最小化后基本都会变，直接赋值会让程序从一个不相干的状态开始跑，测试串全部拒绝，而转移表看上去又是对的，非常难查。

关于不可达状态：子集构造产出的 DFA 天然是从初态可达的（每个状态都是通过某条转移首次发现的），所以最小化这一步不需要额外做可达性剪枝。但如果你的输入是一张手写的 DFA 转移表，里面可能包含从初态永远走不到的状态，这时候要在最小化之前先跑一次 BFS 标记可达状态，把不可达的清掉再划分——否则这些孤岛状态会参与划分、影响组号，虽然不影响语言等价性，但输出会跟标准答案对不上。

5. 避坑与常见问题：五个最容易翻车的地方

这一章列的五个问题，都是我在写这套代码和帮别人看代码时反复遇到的，现象、原因、解决办法逐条写清楚。有些问题不会让程序崩溃，只会让结果悄悄错掉，这类最难查。

5.1 省略了 ε-闭包，转换结果少了好几条边

现象：子集构造跑完了，状态数比手算少，转移表里若干格子是空的，用测试串一跑，本该接受的串被拒绝。

原因：move之后直接拿结果当新状态，忘了再求一次 ε 闭包。ε 边在 NFA 里不消耗输入，求完 move 之后必须把能通过 ε 到达的状态全部补进来，否则新状态集合不完整，后续所有转移都建立在错误的集合上。

解决：把SSet closure = epsilonClosure(nfa, nxt);写成固定的两步，并且在move函数和epsilonClosure函数之间加一条断言——如果 NFA 里根本没有 ε 边（eps全空），闭包结果应该等于输入，这个断言能快速排除「闭包函数本身写错了」的可能。另外，起始状态也要走一遍闭包，不能直接用{start}。

5.2 空集被当成合法状态，最小化后凭空多出终态

现象：最小化之后状态数不降反升，或者多出一个「什么字符都不接受但标着星号」的终态。

原因：move的结果是空集时，仍然为它分配了一个 DFA 状态编号。这个空集状态在后续最小化里会跟其他「没有出边」的状态混在一起参与划分，而它本身连终态都不是，划到最后可能跟某个终态组合并，导致终态标记被污染。

解决：严格按 3.2 节的写法，if (nxt.none()) continue;，空集不建状态，转移缺失即死状态。如果实验要求输出完整的转移表（包括死状态那一行），那就单独在输出阶段补一行，把缺失的格子填成一个专门的死状态编号，但不要让它参与子集构造的编号分配。

5.3 最小化死循环：签名里漏掉了「当前所在组」

现象：程序跑最小化时卡住不动，CPU 占满，加打印发现组数在两组之间来回跳。

原因：签名只包含了「各字符后继所属的组号」，没包含「自己当前所属的组号」。这样一来，一个非终态和一个终态只要后继组号组合相同，就会被判为同签名而合并；合并之后组号重排，下一轮又因为其他原因拆开，来回震荡。

解决：签名第一个元素固定放group[i]。这个字段相当于给每个状态打上「我已经属于哪个组」的烙印，保证细化只会让组变多不会变少。加上之后，while循环的终止判据用组数变化（4.2 节）就非常稳，我这边跑过的所有测试用例都没再出现过震荡。

5.4 终态标记漏判：子集里有一个原终态就算终态

现象：子集构造输出里，某个状态明明包含原 NFA 的终态，却没有被标成接受状态，导致最小化把两个本该分开的组误合并。

原因：终态判定写成了「子集里所有状态都是终态才算终态」，或者只检查了子集的第一个元素。正确的语义是存在量词：子集里只要有一个原终态，这个 DFA 状态就是终态，因为 NFA 的接受定义是「存在一条到达终态的路径」。

解决：按 3.2 节的写法，双层循环里一旦命中就break，语义是「存在即真」。另外建议在输出阶段加一行统计：打印出所有终态编号，跟手算结果逐个对，这一步不到十秒钟，能省掉后面半小时的排查。

5.5 状态编号没有做压缩，转换表打印出一堆空洞

现象：最小化后的转移表能跑对，但状态编号是 0、3、7、11 这种跳跃的，实验报告里画图时对不上，老师一眼就看出中间删过东西。

原因：重建时直接用原group数组里的组号当新编号，而组号是划分过程中分配的，中间可能有空号。

解决：重建之前先做一次编号压缩，把出现过的组号按升序重新映射到 0..k-1。这段代码只有五行，但能让输出干净一大截，画状态转换图时也方便。

// 组号压缩：把 {0,3,7} 映射成 {0,1,2} std::map<int, int> remap; for (int i = 0; i < n; ++i) if (!remap.count(group[i])) { int nid = remap.size(); remap[group[i]] = nid; } for (int i = 0; i < n; ++i) group[i] = remap[group[i]];

6. 验收与答辩：用测试集证明语言等价

代码能跑通不代表结果对，这一点在自动机这类题目上尤其明显——错误的实现往往也能输出一张漂亮的转移表，看着像那么回事。我的做法是准备一组测试串，在子集构造后的 DFA 和最小化后的 DFA 上分别跑一遍，逐条比对结果。

测试集的构造有讲究：不能只放能接受的串，也不能随便凑。通常分三类——边界串（空串、单个字符）、能接受的典型串、以及一堆看着像能接受其实不能的串。拿 2.3 节那份输入来说，语言就是a和b两个串，测试集可以这样设计：

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