简介这套「NFA转DFA并最小化」实验资料由代码与实验报告组成面向开设编译原理课程的高校学生尤其适合ZZU学弟学妹对照课程设计完成自动机部分实验。资源帮助理解子集构造法、DFA状态简化与词法分析原理并提供了可直接运行学习的C实现。压缩包共2个文件其中cpp为实验源码doc为实验报告整体仅722KB轻量且便于快速下载与本地运行。已有415人学习下载说明其实验场景具有一定参考价值。报告涵盖实验目的、步骤、遇到的问题与解决方案源码则可用于验证NFA转DFA及最小化过程便于学生边读边跑、查漏补缺也可作为课程报告撰写的结构参考。1. 这个实验为什么值得跑NFA转DFA不是背算法是手搓状态表「NFA转DFA并最小化」是编译原理实验里出勤率最高的一个也是最容易让人翻车的。说它反直觉是因为你明明背下了子集构造法的三行伪代码合上书开始写C时才发现epsilon闭包、move集合、未访问状态、接受态判定每一步都有暗坑稍不留神就产出一张带着重复行的DFA状态表。这套资源是某高校编译原理课程的完整实验C实现NFA转DFA并做最小化附带一份能直接交的实验报告。它解决的问题很实际你需要一份能跑通、能交报告、还能自己改来应付变体的完整参考实现而不是网上东拼西凑的片段。适合正在做课设的本科生也适合想复习自动机理论的开发者。2. 整体设计与数据表示把NFA先装进C的内存2.1 NFA的存储结构邻接表加epsilon边NFA在课本上是一个五元组(Q, Σ, δ, q0, F)其中δ是个多值映射一个状态读一个符号可能跳转到多个状态。代码里最自然的存法是邻接表每个状态是一个节点每条边记录「符号目标状态」。epsilon转移也塞进这张表里用一个特殊字符占位。const char EPSILON #; struct NFANode { bool is_accept false; std::vectorstd::pairchar, int transitions; // (符号, 目标状态) }; class NFA { public: std::vectorNFANode states; int start 0; std::vectorchar alphabet; // 字母表不含epsilon };符号用char就够因为课程实验里的正则通常只涉及ASCII字符。epsilson占位符选了#而不是空串是因为空串没法放在pair里跟普通字符区分。alphabet单独存一份后面子集构造法要按字母表逐符号遍历这个遍历顺序如果不固定生成的DFA状态编号会不稳定排查起来很头疼。2.2 输入格式一行一条转移规则实验配套的NFA不是程序里硬编码的而是从文本文件读入。常见格式约定如下第一行写状态数和字母表符号个数中间若干行每条写一条转移格式是源状态 符号 目标状态最后一行写起始状态和接受态列表。用#表示epsilon字母表里不包含#。bool loadNFA(const std::string filename, NFA nfa) { std::ifstream in(filename); if (!in.is_open()) return false; int stateCount, alphaCount; in stateCount alphaCount; nfa.states.resize(stateCount); nfa.alphabet.clear(); for (int i 0; i alphaCount; i) { char c; in c; nfa.alphabet.push_back(c); } int from, to; char sym; while (in from sym to) { if (sym EPSILON) { nfa.states[from].transitions.push_back({EPSILON, to}); } else { nfa.states[from].transitions.push_back({sym, to}); } } in nfa.start; int acceptCount; in acceptCount; for (int i 0; i acceptCount; i) { int s; in s; nfa.states[s].is_accept true; } return true; }这段读取逻辑有个隐含约定最后两行不是转移规则所以while循环读到底之后再用读起始状态和接受态。我第一次写的时候把接受态也当作转移规则来读结果起始状态被吞掉DFA的初态全乱。如果你拿到的实验模板格式不同改loadNFA的解析顺序就行后面所有算法都不受影响这算是这套代码设计得比较干净的地方。2.3 工程结构与实验报告里有什么整套资源的目录结构大致是NFA2DFA/ ├── src/ │ ├── nfa.h / nfa.cpp // NFA数据结构和文件读取 │ ├── subset.h / subset.cpp // 子集构造法 │ ├── minimize.h / minimize.cpp // DFA最小化 │ └── main.cpp // 主流程 ├── tests/ │ ├── test1.nfa │ ├── test2.nfa │ └── expected_dfa.txt └── 实验报告.docx实验报告里包含的内容通常有三块算法原理说明、中间状态表的手算过程、最终DFA迁移表。报告里会画NFA的状态图标注每个集合是epsilon-closure的结果。我拿到报告第一件事是看它的状态表命名方式因为程序输出的命名必须跟报告一致否则老师比对时一眼就发现对不上。3. 子集构造法核心从NFA到DFA的完整状态集推导3.1 epsilon闭包与move两个基础函数子集构造法的两个基础操作是epsilonClosure和move。前者是「从一组状态出发沿着epsilon边走能到达的所有状态集合」后者是「从一组状态出发读一个符号能直达的所有状态集合」。两者组合起来就是DFA每个状态的定义。std::setint epsilonClosure(const NFA nfa, const std::setint states) { std::setint closure states; std::vectorint stack(states.begin(), states.end()); while (!stack.empty()) { int cur stack.back(); stack.pop_back(); for (const auto e : nfa.states[cur].transitions) { if (e.first EPSILON !closure.count(e.second)) { closure.insert(e.second); stack.push_back(e.second); } } } return closure; } std::setint move(const NFA nfa, const std::setint states, char sym) { std::setint result; for (int s : states) { for (const auto e : nfa.states[s].transitions) { if (e.first sym) { result.insert(e.second); } } } return result; }epsilonClosure用的是显式栈而不是递归。原因很实际epsilon边可能形成环比如0 - 1 - 0这种循环递归写法一旦忘记标记已访问就是死循环而显式栈配合closure.count判重天然免疫epsilon环。move只找非epsilon的边不做闭包所以代码短得多。注意这两个函数的参数和返回值都是std::setint集合的序是稳定的这保证了同一个NFA每次运行生成的DFA一致。3.2 主循环把状态集合映射成DFA节点子集构造法的主循环本质上是个BFS初始状态epsilonClosure({start})是第一个DFA状态然后对每个DFA状态、每个符号计算epsilonClosure(move(...))得到的新集合要么是已有DFA状态要么新建一个。struct DFAState { std::setint nfa_states; // 对应的NFA状态集合 std::mapchar, int transitions; // 符号 - 目标DFA状态编号 bool is_accept false; }; std::vectorDFAState buildDFA(const NFA nfa) { std::mapstd::setint, int stateIndex; // NFA集合 - DFA状态编号 std::vectorDFAState dfa; auto startSet epsilonClosure(nfa, {nfa.start}); stateIndex[startSet] 0; dfa.push_back({startSet, {}, false}); for (int i 0; i (int)dfa.size(); i) { for (char sym : nfa.alphabet) { auto next epsilonClosure(nfa, move(nfa, dfa[i].nfa_states, sym)); if (next.empty()) continue; if (!stateIndex.count(next)) { stateIndex[next] (int)dfa.size(); dfa.push_back({next, {}, false}); } dfa[i].transitions[sym] stateIndex[next]; } } for (auto s : dfa) { for (int ns : s.nfa_states) { if (nfa.states[ns].is_accept) { s.is_accept true; break; } } } return dfa; }这段代码的关键细节是for (int i 0; i (int)dfa.size(); i)。dfa.size()在循环中不断增长新状态会被继续处理直到没有新状态产生这比用while加queue的写法更直观。另一个细节是接受态判定只要DFA状态的NFA集合里包含任何一个接受态这个DFA状态就是接受态。因为NFA的语义是「存在一条路径到达接受态」不是所有路径。3.3 字母表排序与确定性构建DFA前alphabet最好排个序。原因有两个一是输出状态表时列的顺序稳定二是mapchar, int的key遍历顺序本身就按字符升序如果alphabet不排序某些读入顺序会让输出列和报告排版不一致。排序不会影响DFA的语义只影响展示。std::sort(nfa.alphabet.begin(), nfa.alphabet.end()); nfa.alphabet.erase(std::unique(nfa.alphabet.begin(), nfa.alphabet.end()), nfa.alphabet.end());后面这句unique是去重输入文件里如果重复声明了同一个字母表符号会导致同一个符号被处理两遍move结果一样但生成两条相同的边DFA的确定性被破坏。这种错误用肉眼极难发现因为状态表看起来是满的细看才发现同一列有两个相同的值。我在调试一个测试用例时DFA迁移表里出现了并列的两列a排查半天发现是字母表定义重复从那以后读文件必做去重。4. 最小化实现等价类划分的完整推导4.1 最小化的本质与初始划分DFA最小化的目标是找到等价状态并合并。两个状态等价指的是从它们出发接受完全相同的语言也就是对任意输入串二者要么都接受、要么都拒绝。算法上先按接受态/非接受态分成两个初始块然后反复细分同一块内的状态如果读某个符号后跳到的块不同就拆开。std::vectorstd::setint initializePartition(const std::vectorDFAState dfa) { std::setint accepting, nonAccepting; for (int i 0; i (int)dfa.size(); i) { if (dfa[i].is_accept) accepting.insert(i); else nonAccepting.insert(i); } std::vectorstd::setint partition; if (!nonAccepting.empty()) partition.push_back(nonAccepting); if (!accepting.empty()) partition.push_back(accepting); return partition; }注意不能把空块塞进partition里。如果一个DFA全部状态都是接受态非接受态集合为空push_back空集合会导致后面细分时多出一个永远不变化的空块合并状态时会把编号搞乱。我见过有同学的代码跑出来状态数比理论值多一个就是这个原因。4.2 迭代细分按符号签名拆分块核心循环是不断扫描每个块按「块内每个状态读各符号后落入哪个块」来分组。这个信息可以编码成一个字符串签名每个符号对应一个块编号的字符连成一个串签名相同就留在同一组签名不同就拆开。bool refinePartition(std::vectorstd::setint partition, const std::vectorDFAState dfa, const std::vectorchar alphabet) { bool changed false; std::vectorstd::setint newPartition; for (const auto block : partition) { std::mapstd::string, std::setint groups; for (int state : block) { std::string signature; for (char sym : alphabet) { auto it dfa[state].transitions.find(sym); int target (it dfa[state].transitions.end()) ? -1 : it-second; signature blockIdOf(partition, target); } groups[signature].insert(state); } if (groups.size() 1) changed true; for (const auto kv : groups) { newPartition.push_back(kv.second); } } partition newPartition; return changed; }blockIdOf的作用是查一个DFA状态属于partition里的哪个块返回块编号转成的字符。这里有个关键点-1表示目标状态不存在即转移未定义。未定义转移也要参与签名否则两个状态一个没有转移、一个转移到某个块会被误判为等价。签名用字符串拼接而不是比较两个setint相等是因为分组时需要一个可排序的keymap按字典序排字符串比自定义set比较函数省事得多。主循环只要refinePartition返回changed就继续直到没有块被拆分。这是一个不动点迭代最多DFA状态数轮收敛实际一般两三轮就结束了。4.3 合并等价类从划分回到DFA划分完成后把每个块当作新DFA的一个状态块编号就是新状态编号。迁移关系按块内任意原状态的迁移来确定因为同一块的状态已经验证过迁移到同一块取哪个的结果都一样。std::vectorDFAState minimizeDFA(const std::vectorDFAState dfa, const std::vectorchar alphabet, int startState) { auto partition initializePartition(dfa); while (refinePartition(partition, dfa, alphabet)) {} std::vectorint newId(dfa.size(), -1); for (int i 0; i (int)partition.size(); i) { for (int s : partition[i]) newId[s] i; } std::vectorDFAState minimized(partition.size()); for (int i 0; i (int)partition.size(); i) { int rep *partition[i].begin(); // 取块内任一状态作为代表 minimized[i].is_accept dfa[rep].is_accept; for (char sym : alphabet) { auto it dfa[rep].transitions.find(sym); if (it ! dfa[rep].transitions.end()) { minimized[i].transitions[sym] newId[it-second]; } } } return minimized; }newId数组做了一次编号映射把原DFA状态编号映射到块编号。合并后可能出现新的未定义转移原来指向的状态不可达或已被合并transitions里自然就没有这一项。判断最小化结果是否合理一个简单办法是看状态数是否小于等于原DFA以及从新起始状态出发遍历一遍确认没有状态被孤立。5. 运行与避坑能跑通实验和报了奇怪错误是两回事5.1 坑一epsilon闭包漏掉了初始状态现象生成的DFA状态数比手算的少而且起始状态的NFA集合里只有一个元素明显不对。原因buildDFA主循环里对每个符号都做了epsilonClosure(move(...))但初始状态{start}本身没有先求一次闭包。如果起始状态有epsilon边指向别的状态这些状态就丢了。更隐蔽的情况是起始状态没有epsilon边手算结果恰好正确掩盖了问题。解决第一次计算必须写成epsilonClosure(nfa, {nfa.start})。我习惯把所有闭包计算统一封装不让任何状态直接从NFA裸进DFA集合。5.2 坑二字母表顺序不稳定导致DFA编号随机现象同一份NFA输入跑两次生成的DFA迁移表不同但语义看起来一样。原因alphabet如果用std::setchar去重存储key的遍历顺序是字典序问题不大但如果你用unordered_set遍历顺序每次运行可能不同。DFA状态编号取决于处理符号的顺序顺序一变BFS入队顺序就变状态编号全变。解决强制把字母表放进std::vectorchar并排序。推送固定顺序还能让输出表格与实验报告的状态表对齐手算验证时不用来回数哪列是哪个符号。5.3 坑三最小化前没删不可达状态现象最小化后的状态数比预期多划分结果和理论值对不上。原因DFA从起始状态出发可能有些状态根本到不了比如NFA里定义了但子集构造时没生成的孤立状态。不可达状态通常是非接受态会被归入非接受态那个大块。但它们没有迁移或迁移到未知状态签名和真正可达的非接受态不同导致划分把它们单独拆成一个块。解决最小化之前先做一次BFS遍历从起始状态出发把所有可达状态标记出来然后重排状态编号、丢掉不可达状态。这步必须在initializePartition之前做。我一般会写一个collectReachableStates函数顺便检查有没有状态无法从起始状态到达。5.4 坑四程序输出的状态表跟实验报告对不上现象状态数对了、接受态对了但老师要求的状态表格式跟程序输出格式不一致手工誊写又抄错。原因实验报告的表格通常是「状态 | 符号a | 符号b | 是否接受」四列而程序默认只打印转移关系省略接受态列或者列序不同。解决写一个dump函数按报告格式输出CSV或TSV直接把输出粘贴进报告。void dumpDFA(const std::vectorDFAState dfa, const std::vectorchar alphabet) { std::cout state; for (char sym : alphabet) std::cout \t sym; std::cout \taccept std::endl; for (int i 0; i (int)dfa.size(); i) { std::cout i; for (char sym : alphabet) { auto it dfa[i].transitions.find(sym); std::cout \t (it dfa[i].transitions.end() ? - : std::to_string(it-second)); } std::cout \t (dfa[i].is_accept ? Y : N) std::endl; } }用-表示未定义转移比留空更直观也避免表格列数对不齐。输出后跟报告里手算的表逐行比一遍几乎能立刻定位是算法错误还是格式问题。6. 二次开发把最小化DFA改造成词法分析器实验做到最小化DFA出表其实已经完成了一个词法分析器的核心。下一步改造是把这张状态表变成可执行的匹配器。常见做法是直接用二维数组存迁移表行是DFA状态列是字符值是目标状态。读取方式用一个vectorvectorint transitionTable长度是状态数乘字母表大小查表复杂度O(1)。int matchLongest(const std::vectorstd::vectorint table, const std::vectorchar alphabet, const std::string input, int endPos) { int currentState 0, lastAccept -1, lastPos -1; for (int i 0; i (int)input.size(); i) { auto pos std::find(alphabet.begin(), alphabet.end(), input[i]); if (pos alphabet.end()) break; currentState table[currentState][pos - alphabet.begin()]; if (currentState -1) break; if (isAcceptState(currentState)) { lastAccept currentState; lastPos i 1; } } endPos lastPos; return lastAccept; }这个函数是经典的「最长匹配」逻辑每次转移后记录最近一次进入接受态的位置最终返回最后一个接受位置。词法分析器用它识别标识符、关键字、数字字面量时能正确处理像intx这种应该拆成int和x而不是匹配成intx失败的场景。endPos回传给调用方就能不断切割输入流。如果想把实验做得更完整可以在子集构造后增加一个符号表模块把每个DFA状态关联一个token类型最小化DFA后把等价状态合并带来的token类型冲突检查一遍。有一个教训做改造时别直接改minimizeDFA的返回结构先给原DFA和最小化DFA各写一个匹配器用随机生成的字符串分别跑一遍确认两个匹配器接受的语言完全一致再合并代码。从那以后我每次改完自动机相关代码都强制跑一遍「原DFA vs 最小化DFA」的双轨对拍再交给老师看结果。这个习惯帮你省下大量查报告对不上的时间。希望帮到你。本文还有配套的精品资源点击获取