简介针对高校《编译原理》课程的「NFA转DFA并最小化」实验这份资源提供了C源代码与完整实验报告适用于本科阶段正在学习自动机理论、需要动手完成编译器词法分析环节的读者。代码采用子集构造法完成NFA到等价DFA的转换并通过合并等价状态逐步消除冗余状态最终得到最小化DFA实验报告则围绕实验目的、操作步骤、测试用例和异常问题展开附有必要的算法思路与结果分析能够帮助读者真正理解子集构造和最小化的运作过程。压缩包共2个文件doc格式报告与cpp源码整体仅722KB轻量便于下载取用。目前已有414人学习下载。通过这份资料既可以直接阅读或运行C实现验证算法又能参照一份结构完整的实验报告来梳理自己的设计思路对课堂作业、期末复习以及后续词法分析器设计均有借鉴价值。1. 编译原理实验里的NFA转DFA为什么值得花一个晚上编译原理实验排到 NFA转DFA并最小化基本上就是词法分析之前的分水岭正则写起来容易一到子集构造法和DFA最小化很多同学开始怀疑状态表是玄学。ZZU把这个实验放在词法分析前面验收标准很朴素——给一个正则比如(a|b)*abb要能给出最终最小化的DFA并且打开你的代码解释清楚每一步在做什么。这个实验值不值得花时间值得。它直接决定你后面词法分析实验是照抄糊弄还是真正理解状态机也是面试官针对自动机问题最喜欢追问的一段。下面按实际动手顺序来写先定数据结构再跑子集构造法做最小化最后是排错和实验报告。新手能跟着代码跑通已经写过一遍的人可以重点看坑和验证方法。2. NFA的表示与输入把状态转移表设计好算法先省一半力2.1 为什么说数据结构决定整个实验的难度NFA 的五元组是(Q, Σ, δ, q0, F)难点全在δ一个状态在同一个符号下可以转移到多个状态还允许 ε 转移。用 C 写常见的做法是vectormapchar, setint看着不复杂但后面子集构造法得到的 DFA 状态是一个 NFA 状态集合你得维护mapsetint, int这种“集合到编号”的映射C 的set做 map key 没有任何问题但输出调试、打印状态集合的时候非常痛苦。我一般直接用 Python 标准库实现原因有三个一是子集构造法里 DFA 状态天然就是集合Python 的frozenset可以直接做字典 key省掉一层手工编号二是实验报告里贴 Python 代码可读性比 C 的模板容器高一大截老师一眼能看懂你在干什么三是不需要第三方库机房没有网也能跑。如果你学校要求必须交 C算法逻辑完全一样只是把dict换成mapset换成setint即可。推荐的数据结构是这样NFA 的转移表用dict[int, dict[str, set[int]]]外层 key 是状态编号内层 key 是转移符号value 是所有能到达的状态集合。ε 转移用一个特殊符号E表示避免和普通字符混淆。这个结构对读取、闭包计算和 move 操作都很顺手后面三个核心函数都会基于它写。2.2 约定一个简单可读的输入文件格式实验报告里需要贴 NFA 数据我习惯用一个纯文本文件作为输入格式固定成这样行内容说明第 1 行状态数 字母表 起始状态 接受状态字母表和接受状态用逗号分隔无 ε第 2 行起状态 符号 目标状态每行一条转移符号为E时表示 ε读取函数如下逻辑很直接但要记得跳过空行和注释def read_nfa(path): with open(path, encodingutf-8) as f: lines [] for line in f: line line.strip() if not line or line.startswith(#): continue lines.append(line) header lines[0].split() n_states int(header[0]) alphabet header[1].split(,) start int(header[2]) accepts {int(x) for x in header[3].split(,)} transitions {} for s in range(n_states): transitions[s] {} for line in lines[1:]: s, sym, t line.split() s, t int(s), int(t) if sym not in transitions[s]: transitions[s][sym] set() transitions[s][sym].add(t) return list(range(n_states)), alphabet, start, accepts, transitions这个函数的返回是一个五元组和 NFA 的定义一一对应。参数path是输入文件路径encodingutf-8是为了防止 Windows 机房默认编码读中文注释报错。读取完成后建议先打印一下每个状态的转移确认数据没读歪再继续写算法。比如打印transitions[0]应该能看到{E: {1}}这样的字典。2.3 准备两个测试样例一个练 ε 闭包一个练最小化不要一上来就拿大正则测试。我一般准备两个 NFA 文件分别针对实验的两个核心步骤。第一个文件nfa_eps.txt语言是(a|b)*专门用来验证 ε 闭包和子集构造法3 a,b 0 2 0 E 1 1 a 1 1 b 1 1 E 2状态 0 到状态 1 是 ε 转移状态 1 到状态 2 也是 ε 转移所以epsilon_closure({0})应该得到{0, 1, 2}直接从初态就能跳到终态。第二个文件nfa_abb.txt语言是(a|b)*abb这是选用书里最常见的例子用来验证最小化4 a,b 0 3 0 a 0 0 a 1 0 b 0 1 b 2 2 b 3这个 NFA 没有 ε 转移但状态 0 在a下同时转到 0 和 1是一个标准的非确定型转移。子集构造后应该得到 4 个 DFA 状态最小化后合并成 3 个如果结果不是 3 个算法里一定有 bug。提示输入文件的字母表里不要写EE只作为转移符号出现在后面的行里这样alphabet可以安全用于遍历 DFA 的每个输入符号。3. 子集构造法从NFA到DFA核心是ε闭包和move3.1 先实现ε闭包一个栈加一个visited集合就够了ε 闭包的定义从某组 NFA 状态出发只沿着 ε 边能到达的所有状态集合包括自己。写递归也能做但 NFA 的 Thompson 构造里经常出现环比如a*的构造会生成0 - ε - 1和1 - ε - 0这种结构递归一旦没做 visited 标记直接爆栈。用栈加集合去重最稳。def epsilon_closure(sources, transitions): result set(sources) stack list(sources) while stack: s stack.pop() for nxt in transitions.get(s, {}).get(E, ()): if nxt not in result: result.add(nxt) stack.append(nxt) return frozenset(result)这里sources可以是一个状态也可以是一组状态调用方只需要保证它可迭代。逻辑上result既是返回值也是 visited 集合每个状态只会入栈一次所以即使 NFA 里有 ε 环也能正常结束。返回frozenset而不是set是为下一步子集构造法里拿它当字典 key 做准备。参数transitions就是读入函数返回的转移表不需要额外复制。3.2 再写 move一个状态集合在某个符号下能走到哪move 和 ε 闭包的区别在于move 只走一条普通符号边不继续走 ε 边。标准的子集构造法步骤是先对当前 DFA 状态一个 NFA 状态集合做 move得到一组中间状态再对这组中间状态求 ε 闭包结果才是下一个 DFA 状态。def move(sources, symbol, transitions): result set() for s in sources: for nxt in transitions.get(s, {}).get(symbol, ()): result.add(nxt) return result这段代码看起来简单但有一个容易忽略的点transitions.get(s, {})返回空字典时说明状态s没有这个符号的转移这时.get(symbol, ())返回空元组循环体不会执行。返回值是set而不是frozenset因为下一步还要把它传给epsilon_closure闭包函数内部会自己转成frozenset。3.3 子集构造主循环frozenset做状态deque做队列核心循环的思路是初始 DFA 状态是epsilon_closure({q0})然后不断从未处理的 DFA 状态出发对字母表里每个符号算epsilon_closure(move(...))如果得到的新集合还没出现过就给它分配一个新的编号。这就是子集构造法也叫幂集构造因为最坏情况下 DFA 状态数是 NFA 状态数的指数级。from collections import deque def nfa_to_dfa(states, alphabet, start, accepts, transitions): start_set epsilon_closure({start}, transitions) dfa_states [start_set] # 下标就是 DFA 状态编号 state_id {start_set: 0} # frozenset - 编号 queue deque([0]) # 待处理的 DFA 状态编号 dfa_trans {} # DFA 转移表 dfa_accepts set() # DFA 终态集合 while queue: cur queue.popleft() cur_set dfa_states[cur] # 只要 DFA 状态对应的 NFA 集合里包含原始终态它就是终态 if cur_set accepts: dfa_accepts.add(cur) dfa_trans[cur] {} for sym in alphabet: nxt_set epsilon_closure(move(cur_set, sym, transitions), transitions) if not nxt_set: continue # 死状态先不写进转移表 if nxt_set not in state_id: state_id[nxt_set] len(dfa_states) dfa_states.append(nxt_set) queue.append(state_id[nxt_set]) dfa_trans[cur][sym] state_id[nxt_set] return dfa_states, dfa_trans, dfa_accepts这里有两个关键参数states和alphabet其实只在数据类型层面约束了输入真正干活的是transitions和accepts。state_id用frozenset做 key是因为 Python 的set不可哈希直接拿去查字典会报unhashable type: set。用deque而不是list.pop()是为了按广度优先的顺序给 DFA 状态编号这样打印出来的状态表层次清晰和手推结果容易对应。3.4 跑一下 (a|b)*abb四状态DFA到手把两个测试文件都跑一遍。用小样本验证闭包states, alphabet, start, accepts, trans read_nfa(nfa_eps.txt) dfa_states, dfa_trans, dfa_acc nfa_to_dfa(states, alphabet, start, accepts, trans) for i, s in enumerate(dfa_states): print(i, sorted(s), dfa_trans[i], F if i in dfa_acc else )nfa_eps.txt的输出应该是状态 0 对应的集合是{0, 1, 2}字母a和b都回到自己而且是终态。这说明(a|b)*整个语言只需要一个 DFA 状态非常符合直觉。nfa_abb.txt的输出整理成转换表是DFA状态对应的NFA状态集合ab是否终态0{0}10否1{0,1}12否2{0,2}13否3{0,3}10是手动检查一下状态 1它读a时move({0,1}, a)得到{0,1}状态 0 的 a 边到 0 和 1状态 1 没有 a 边闭包后还是{0,1}于是回到状态 1读b时得到{0,2}进入状态 2。这个表就是后续最小化的输入建议实验报告里原样贴出来。4. DFA最小化划分法三步走先把快照拍好4.1 最小化到底在消除什么观察上面的四状态 DFA状态 0 和状态 1 看起来不一样一个{0}一个{0,1}但它们在所有输入下的行为完全一致读a都进状态 1读b都进状态 0而且都不是终态。对任何输入串从状态 0 出发和从状态 1 出发最终是否接受的结果都一样。这样的两个状态叫不可区分状态可以合并成一个。最小化算法的本质就是找出所有不可区分状态把 DFA 的状态集合划分成若干等价类。每个等价类合并成一个新状态得到的 DFA 是原语言的最小 DFA。这里不要求你理解 Hopcroft 算法的高深数学证明只要掌握迭代划分法就能应付实验初始把所有终态放在一组、所有非终态放在另一组然后反复检查同一组里的状态在每个符号下都必须转到同一组否则拆开直到不能再拆。4.2 迭代划分法实现minimize_dfa 的 3 个必写细节第一个细节是初始划分必须同时考虑终态组和非终态组少了非终态组所有非终态会因为找不到分组而全部混在一起。第二个细节是每一轮迭代必须基于上一轮的划分结果做判断也就是先拍快照再更新。第三个细节是每个状态的“签名”要把字母表里所有符号都算上只比较一个符号就分组结果会不稳定。def find_group(partitions, state): for idx, group in enumerate(partitions): if state in group: return idx return -1 def minimize_dfa(dfa_states, dfa_trans, dfa_accepts, alphabet): n len(dfa_states) accept_set set(dfa_accepts) non_accept_set set(range(n)) - accept_set partitions [] if accept_set: partitions.append(accept_set) if non_accept_set: partitions.append(non_accept_set) changed True while changed: changed False snap partitions[:] # 旧划分快照必须用这份做判断 new_partitions [] for group in snap: bucket {} for s in group: sig [] for sym in alphabet: nxt dfa_trans.get(s, {}).get(sym, -1) sig.append(find_group(snap, nxt)) bucket.setdefault(tuple(sig), set()).add(s) if len(bucket) 1: new_partitions.extend(bucket.values()) changed True else: new_partitions.append(group) partitions new_partitions return partitionsfind_group的作用是查一个状态属于哪个组查不到就返回-1对应的是“死状态”或者“没有转移”的情况。snap partitions[:]是浅拷贝因为partitions里的元素是set浅拷贝已经够用——我们只需要保证这一轮迭代里查的组顺序不被新划分干扰。sig是一个元组长度等于字母表长度表示这个状态在当前划分下的“行为指纹”。如果组里所有状态指纹相同说明它们暂时不可区分如果出现不同指纹就按指纹分桶拆开。changed只在真正发生拆分时置为True所以最坏情况下每轮至少拆出一个单状态组最多n-1轮结束。这个实现不是 Hopcroft 最优版本但实验规模下性能完全够用而且比教科书伪代码更容易理解。4.3 重命名把划分变成一张干净的新转换表划分得到的是若干组每组里塞了好几个旧状态。要输出新 DFA得给每个组分配一个新编号。方法很简单把每个组取最小的那个状态编号作为组的代表按代表的顺序编号。然后遍历旧转移表把每个旧状态映射到新编号。def rebuild_dfa(partitions, dfa_trans, dfa_accepts, alphabet): mapping {} for new_id, group in enumerate(partitions): for s in group: mapping[s] new_id new_trans {} new_accepts set() for old, trans in dfa_trans.items(): cur mapping[old] if cur not in new_trans: new_trans[cur] {} for sym, target in trans.items(): new_trans[cur][sym] mapping[target] for acc in dfa_accepts: new_accepts.add(mapping[acc]) return len(partitions), new_trans, new_acceptsmapping是从旧 DFA 状态到新 DFA 状态的字典partitions的顺序直接决定新状态编号。这里有个小坑如果旧转移表里出现了没有映射的状态一定是你最小化前的dfa_states和dfa_trans不一致建议在调用前断言len(dfa_states) len(dfa_trans)。终态集合的重映射也要做否则合并后终态会丢。4.4 验证最小化前后用同一批字符串跑一遍对nfa_abb.txt跑最小化划分结果应该是{0, 1}原状态 0 和 1 合并、{2}、{3}。按重命名顺序新状态 0 对应旧 {0,1}新状态 1 对应旧 {2}新状态 2 对应旧 {3}。重建后的转换表新状态ab是否终态001否102否200是从原来的 4 个状态减到 3 个而且这个 3 状态 DFA 是(a|b)*abb的标准最小 DFA。为了验证最小化没有改变语言建议写一个简单的模拟器def accepts(word, trans, accept_set, start0): s start for c in word: if c not in trans.get(s, {}): return False s trans[s][c] return s in accept_set然后随机生成一批由a和b组成的字符串分别用最小化前后的dfa_trans和new_trans跑结果必须完全一致。这一步一定要做因为最小化算法一旦写错状态数可能对但语言已经变了。我在自己的实现里用这个方法抓出过一次 bug当时是快照没拍导致合并后的状态接受行为完全乱了。5. 常见问题排查NFA转DFA实验里我掉进去的5个坑这一章全是血泪经验。每个坑我都按“现象—原因—解决”写你如果正好卡在某一步直接对照排查。5.1 ε闭包死循环NFA里藏着ε环现象epsilon_closure函数一跑就报RecursionError或者程序卡住不结束。原因Thompson 构造出的 NFA 里a*这类结构会出现0 - ε - 1、1 - ε - 0的环递归写法没有记录哪些状态访问过永远递归不完。解决用栈加result集合状态只有在第一次被加入result时才入栈每个状态最多处理一次。这个就是上面代码里的写法不需要再用单独的 visited 变量。5.2 set 当 dict key报 unhashable type现象TypeError: unhashable type: set。原因子集构造法里自然想到用set表示 DFA 状态但 Python 的set是可变的不能做字典 key。解决所有放进state_id和dfa_states的状态一律用frozenset。注意epsilon_closure的返回值必须是frozenset不能只在state_id里转一次——如果闭包函数返回set每次查字典前都得手工转漏一处就崩一次。5.3 最小化时原地改划分结果全乱现象最小化后的状态数量碰巧对但随机抽几个字符串验证接受结果和原来不一样。原因迭代划分法里同一轮迭代中一个组被拆开后新组立刻被放进partitions后续状态在find_group时查到了新组导致同一个状态在不同的判断里归属不一致整个划分就乱了。解决每轮迭代开始前拍快照snap partitions[:]这一轮所有find_group都查snap新划分统一收集到new_partitions轮末一次性替换。这是最小化算法里最容易隐蔽的 bug没有之一。5.4 初始划分漏了非终态组现象最小化后 DFA 只剩 1 个状态而且这个状态是终态。原因partitions里只加了accept_set非终态组没有加进去。这样所有非终态状态在find_group里都返回-1签名相同被当成一组合并了。解决初始划分必须同时考虑终态组和非终态组。写的时候要注意如果某个 DFA 所有状态都是终态或者都不是终态对应的组要跳过否则partition会多出一个空集合导致后面的映射出错。上面代码里两个if判断就是干这个的。5.5 终态判定时忘了 ε 闭包现象(a|b)*这个 NFA 转出的 DFA 居然不是终态。原因只判断了move的结果是否包含 NFA 终态但 NFA 的终态可能通过 ε 边从当前集合里的其他状态到达。也就是说终态判断必须在epsilon_closure(move(...))之后的集合上做而不是在 move 的中间集合上做。解决在nfa_to_dfa的主循环里先算了cur_set dfa_states[cur]这个cur_set已经是闭包之后的结果直接判断cur_set accepts即可。如果你手写子集构造法每一步都要记得先 move再闭包最后判断终态。5.6 状态编号顺序和手算对不上现象自己手推的 DFA 状态表是{0,1}、{0,2}这种顺序代码打印出来却是乱序比如{2,0}。原因set是无序的直接str(s)打印出来当然乱另外 BFS 和 DFS 的遍历顺序不同状态编号也会不同。解决打印时用sorted(s)把集合转成有序列表便于和手推表对照。如果你希望编号顺序和手推一致把deque换成栈list用 DFS 顺序生成编号或者反过来以你手推的方式为准来选队列类型。调整个实验的时候我的习惯是每跑一步就打印一次阶段结果读入后打印 NFA 转移表子集构造后打印 DFA 转换表最小化后打印分组和重建表。不要等到最后统一输出那样很难定位是第几步出的问题。6. 实验报告怎么编排才叫“完整可复现”代码跑通只是前半场ZZU 这个实验的评分标准是代码加报告一起交报告里如果只有两段截图老师很难相信是你自己写的。我一般会把报告结构固定成下面这样既不冗长又能覆盖所有扣分点。报告部分具体写什么容易踩的坑实验目的写“理解 NFA 与 DFA 的等价性掌握子集构造法和 DFA 最小化算法”抄教材原文和实验内容脱节实验环境Python 3.8标准库操作系统不写版本号老师没法复现实验原理ε 闭包、move、子集构造法、不可区分状态的定义只贴定义不写为什么需要核心代码read_nfa、epsilon_closure、nfa_to_dfa、minimize_dfa贴整段 main没有函数逻辑说明测试与结果输入文件内容、中间子集、最小化前后的转换表只有截图没有可复制的表格复杂度分析子集构造最坏 O(2^n)划分法每轮 O(Q实验心得写你实际改过的 bug比如快照问题、ε 环问题写“学会了团队合作”这类空话报告里的转换表一定要用表格形式状态编号和输入符号对齐。老师检查时会先看最小化前后状态数有没有变化然后再随机找一个状态对着表走两步表格清晰能省掉大量不必要的解释。另外有一个小技巧提交前在代码里加一段调试输出把每个 DFA 状态对应的 NFA 状态集合打出来。老师看到{0,1}、{0,2}这种中间结果就能确信你是真跑了算法而不是背答案。我自己的习惯是先把预期状态表手写出来再倒着跑代码验证。这个习惯看着笨但换语言、换学校、换项目都通用帮我少翻了好几次车。希望帮到你。本文还有配套的精品资源点击获取