NFA转DFA的Python实现：子集构造法完整代码与避坑指南

简介面向编译原理学习者与开发者的完整实验资料包围绕非确定有限自动机到确定有限自动机的转换展开基于Python实现了子集构造法帮助理解正则表达式到自动机的编译过程。压缩包共3个文件包含Python转换脚本、状态描述文本和实验报告文档整体约607KB轻量易携带。脚本实现中定义了状态集合、起始状态、接受状态与转移函数并使用子集构造法处理多个可选转移和空转移最终生成等价的确定有限自动机。状态描述文本给出便于解析的输入格式文档则从基本概念到算法细节逐步讲解还包含转换结果状态图、输入字符串识别验证以及常见问题排查。已有1085人学习下载既适合正在学习编译原理的学生巩固课程实验也适合需要快速上手自动机转换的开发者参考整套资料实用性强。1. 编译原理NFA转DFA这份Python实现能让你少熬两个通宵编译原理课一讲到词法分析NFA转DFA就是绕不过去的坎。教材上的子集构造法看起来就几页纸真到自己写代码的时候epsilon闭包算不对、终态集合判错、转移表越查越乱实验课上一坐就是一下午。这份资源就是针对这个痛点来的用Python把NFA的存储结构、epsilon闭包、move操作、子集构造法主循环、DFA最小化整条链路写成可运行的代码你只需要把自己手算过的NFA五元组喂进去马上就能得到对应的DFA转移表和终态集合连1(0|1)*101这类教材经典例题都能直接验证。期末要交实验报告的同学、考研复习想验算答案的同学、刚开始写词法分析器但被状态转换搞晕的新手都适合拿这份实现当脚手架。与其对着草稿纸一遍遍推子集不如让代码帮你把结果算出来你只负责看懂每一步为什么这么做。2. NFA的数据结构用字典嵌套集合模拟状态转移表2.1 为什么不用二维数组存NFA转移NFA和DFA最大的区别就是转移关系不是函数而是关系一个状态读一个字符可能到达多个状态再加上epsilon空转移整个图的结构是稀疏且多对多的。很多第一次写转换程序的人习惯用二维数组transition[state][symbol]来存结果发现两个问题一是数组里大量格子是空的浪费空间二是NFA的转移目标不止一个二维数组根本塞不下集合。就算硬塞transition[state][symbol] [s1, s2]状态编号一旦多了查表和增删都别扭。我一般直接用字典嵌套集合结构直观写起来也顺手class NFA: def __init__(self, states, alphabet, transitions, epsilon, start, accepts): self.states set(states) # 状态编号集合比如 {0,1,2,...} self.alphabet set(alphabet) # 输入符号表比如 {0,1} # transitions: {状态: {符号: 目标状态集合}} # 例如 {0: {1: {1}}} 表示状态0读字符1到达状态1 self.transitions { s: {a: set(targets) for a, targets in row.items()} for s, row in transitions.items() } # epsilon: {状态: 可经epsilon到达的状态集合} self.epsilon {s: set(targets) for s, targets in epsilon.items()} self.start start # 起始状态 self.accepts set(accepts) # 接受状态集合这套NFA五元组对应的是编译原理教材里的标准定义状态集合、字母表、转移函数、起始状态、接受状态集合只是把数学符号写成了Python的数据结构。这里有几个细节值得说明状态编号用整数而不是字符串是因为后面子集构造法要用集合运算整数在frozenset和dict里做key效率高转移表的值必须是集合哪怕只有一个目标也要写成{3}而不是3不然后面做并集运算会类型报错epsilon转移单独用一个字典存不要和普通转移混在一块否则闭包计算的时候还要挨个区分哪些边是epsilon边。2.2 epsilon闭包和move子集构造法的两个地基算子子集构造法反复用到两个操作一个算epsilon闭包一个算move。epsilon闭包是从某个状态集合出发沿着epsilon边走能到达的全部状态move是从某个状态集合出发读一个指定字符能一步到达的状态集合。这两个操作单独拆出来写比在子集构造主循环里揉成一团清晰得多。def epsilon_closure(self, states): closure set(states) stack list(states) while stack: s stack.pop() for t in self.epsilon.get(s, set()): if t not in closure: closure.add(t) stack.append(t) return closure def move(self, states, symbol): result set() for s in states: targets self.transitions.get(s, {}).get(symbol, set()) result | targets return resultepsilon闭包用栈迭代而不是递归这是吃过亏之后养成的习惯。递归写法看起来简洁但NFA状态图里epsilon边经常成环比如闭包运算(0|1)*的NFA里状态通过epsilon边绕回起点递归不写visited集合就会无限循环写了visited又会有一层层栈帧开销。用stack closure的迭代写法closure本身就充当了visited的角色不会重复入栈也不存在递归深度风险。move操作更简单对states里每个状态查转移表取目标集合并集。注意用的是self.transitions.get(s, {}).get(symbol, set())而不是直接下标访问这样遇到没有定义转移的状态或字符时返回空集合不会抛KeyError——这个习惯在后面子集构造的循环里能省很多事。3. 子集构造法NFA转DFA的主循环怎么实现3.1 用课本例题1(0|1)*101完整走一遍转换子集构造法的思想一句话概括把NFA的状态子集当作DFA的状态用epsilon闭包和move两个算子构造转移关系。教材里写的是标记未处理的子集落到代码里就是一个未处理队列加一个已发现子集列表。以正则表达式1(0|1)*101为例按Thompson构造法生成的NFA状态图可以直接写成五元组喂给程序这个表达式在不少编译原理教材的课后习题里都出现过构造出的DFA恰好能检验你对闭包运算的理解。nfa NFA( statesrange(10), alphabet{0, 1}, transitions{ 0: {1: {1}}, 2: {1: {3}}, 4: {0: {3}}, 6: {1: {7}}, 7: {0: {8}}, 8: {1: {9}}, }, epsilon{ 1: {2, 4, 5}, 3: {2, 5}, 5: {6}, }, start0, accepts{9}, )这10个状态对应的是1(0|1)*101用Thompson构造法搭出来的中间状态0是开头那个1的起点1是它的终点同时也是(0|1)*的入口2和3是闭包内部1分支的一对状态4是闭包内部0分支的起点终点也是35是闭包出口6和7是中间1的起止7又兼作0的起点8兼作最后1的起点9是整体接受状态。epsilon边把闭包内部串起来1可以跳到2、4或53可以绕回2或跳到55再到6。你不需要手动理解这10个状态的全部含义写好输入交给转换函数就行。def subset_construction(nfa): start_set nfa.epsilon_closure({nfa.start}) dstates [start_set] # 已发现的所有NFA状态子集 unmarked [start_set] # 等待处理的状态子集队列 dtran {} # (DFA状态id, 符号) - 目标DFA状态id dfa_accepts set() # DFA接受状态id集合 while unmarked: T unmarked.pop() T_id dstates.index(T) if T nfa.accepts: dfa_accepts.add(T_id) for symbol in sorted(nfa.alphabet): U nfa.epsilon_closure(nfa.move(T, symbol)) if not U: continue if U not in dstates: dstates.append(U) unmarked.append(U) U_id dstates.index(U) dtran[(T_id, symbol)] U_id return dstates, dtran, dfa_accepts主循环里最核心的判断是T nfa.accepts子集T和原NFA接受状态集合的交集非空说明这个子集里包含了原NFA的接受状态那么对应的DFA状态就是接受状态。这里用位与运算而不是等值判断是因为子集构造法里一个DFA状态是若干个NFA状态的集合只要其中任何一个在NFA里是被接受的整个DFA状态都要标记为接受。sorted(nfa.alphabet)保证每次遍历字母表的顺序固定DFA状态编号的生成顺序稳定对后续输出转移表和调试都有帮助。3.2 转换结果如何组织成DFA转移表和终态集合跑完上面的函数拿到dstates、dtran、dfa_accepts三个返回值但直接看这些数据还是不直观——dstates里是frozenset的嵌套dtran的key是一对元组。为了让实验报告能直接贴上我习惯再写一个格式化的函数把每个DFA子集映射成字母A、B、C这样的短编号再逐行打印转移表。def format_dfa(nfa, dstates, dtran, dfa_accepts): name {i: chr(ord(A) i) for i in range(len(dstates))} lines [DFA状态\t \t.join(sorted(nfa.alphabet)) \t是否接受] for i, sset in enumerate(dstates): row [name[i]] for symbol in sorted(nfa.alphabet): target dtran.get((i, symbol), -) row.append(name[target] if target ! - else -) row.append(是 if i in dfa_accepts else 否) lines.append(\t.join(row)) return \n.join(lines)打印出来的结果应该是这样DFA状态01是否接受A-B否BCD否CCD否DED否ECF否FED是对照手算过程验证一下A是初态读1进入BB读0或1分别到C和D最后读到串1101即1 空串 101时路径是A→B→D→E→FF是接受态。你随便拿几个串去试比如1010110101对应A→B→C→D→E→F也接受而100走到C就断在非接受态。转移表里那个-表示未定义转移严格说应该补一个死状态这在第4章的最小化里会处理这里先在打印输出层面用-占位。4. 把DFA再压缩最小化分组算法实现4.1 为什么需要最小化存储开销和实验评分点子集构造法生成的DFA状态数量直接取决于NFA的结构例题还好你要是拿一个带多个闭包嵌套的正则表达式去跑生成的DFA状态动辄十几个而且里头往往有大量行为完全一致的状态——它们在每个输入符号下都去往同样的状态组接受性也相同。这样的冗余状态在词法分析器里意味着多余的分支判断在实验评分里也是明显的扣分项。教材给的算法叫表格填充分组法思想很朴素先把DFA状态按是否接受分成两类然后反复检查每一组里的状态在读取每个符号后是否都落到同一组如果某个状态落到了别的组就把它们拆开直到收敛。收敛的分组里同组状态彼此等价可以合并成一个。第3章生成的6个DFA状态里B和C就是一对等价状态B读0到C读1到DC读0到C读1到D行为完全一致合并之后DFA从6个状态压到5个整体结构也清爽很多。4.2 用分组细化实现DFA最小化实现最小化的代码里有个绕不开的细节转移表是稀疏的有些状态对某个符号没有定义转移。正经做最小化必须把这些缺口补全成死状态否则分组细化时两个状态可能因为一个缺转移一个不缺被错误地判成不等价。我的做法是给转移表补一个编号为len(dstates)的隐式死状态它所有符号的转移都指向自己永远不进接受组。def dfa_minimize(dstates, dtran, accepts, alphabet): n len(dstates) dead n full_dtran dict(dtran) full_accepts set(accepts) for s in list(range(n)) [dead]: for a in alphabet: if (s, a) not in full_dtran: full_dtran[(s, a)] dead groups [] accept_group {s for s in range(n) if s in full_accepts} non_accept_group {s for s in range(n) if s not in full_accepts} if accept_group: groups.append(accept_group) if non_accept_group: groups.append(non_accept_group) while True: new_groups [] changed False for group in groups: sig_map {} for s in group: signature tuple( next(gi for gi, g in enumerate(groups) if full_dtran[(s, a)] in g) for a in alphabet ) sig_map.setdefault(signature, set()).add(s) if len(sig_map) 1: changed True new_groups.extend(sig_map.values()) groups new_groups if not changed: break rep {} for gi, group in enumerate(groups): rep[min(group)] gi min_dtran {} min_accepts set() for gi, group in enumerate(groups): s min(group) for a in alphabet: target full_dtran[(s, a)] target_gi next(i for i, g in enumerate(groups) if target in g) min_dtran[(gi, a)] target_gi if s in full_accepts: min_accepts.add(gi) return groups, min_dtran, min_accepts这个实现里最关键的是signature的计算对组内每个状态拿出它在每个输入符号下转入的状态所在组的编号组成一个元组。元组相同的状态说明它们在当前分组划分下行为一致留在同一组元组不同的就会被拆到不同组。next(gi for gi, g in enumerate(groups) if target in g)这段是在找目标状态属于当前哪一组用生成器表达式少写一个for循环。收敛条件是整轮循环没有任何一组发生分裂这时每个分组内部的状态就完全等价了。把第3章的DFA跑完最小化分组过程是这样的初始分{F}和{A,B,C,D,E}第一轮E因为读1进了F而被单独拆出第二轮D因为读0进了E被拆出第三轮B、C因为读1进了D被拆出同时A和死状态因为读1的去向不同也被拆开最后剩下{B,C}可以合并。最终最小DFA的转移表最小DFA状态01是否接受A(含死态)-BC否BCBCD否DED否EBCF否FED是注意这里死状态被我合并进了A严格做法是死状态单独保留。实际写词法分析器时死状态通常直接省略转移函数里查不到就拒绝代码里这5个状态加死状态的组合按自己实验要求取舍。5. NFA转DFA避坑四个常见的翻车现场5.1 epsilon闭包漏算导致的状态集合错乱现象转换出来的DFA对明显应该接受的串报拒绝比如1(0|1)*101的最短串1101在某个中间状态就断了。原因epsilon_closure只处理了一层epsilon边没有沿着epsilon路径继续传播。有些NFA里epsilon边是链式的比如状态1经epsilon到55又经epsilon到6只算一层就会漏掉6。解决闭包计算必须用栈或队列迭代到收敛每弹出一个新状态就检查它的epsilon目标有没有进过closure。上面2.2节的实现里if t not in closure这行判断就是关键漏了这行遇到epsilon环就会死循环。5.2 子集编号与状态重命名冲突现象程序不报错但打印转移表时出现状态错位A状态的行为一会儿对一会儿不对。原因有人图省事直接用frozenset作为DFA状态的key打印的时候又按插入顺序编号dstates列表里子集被追加的顺序和子集实际被发现的顺序不一致一旦中间有状态被重复发现编号就乱了。解决数据结构上可以放心用list存dstates、用index找编号但打印和调试时一定维护一个子集 - 字母编号的映射表所有输出统一走映射。我在3.2节的format_dfa里就是先建name字典再逐行查表避免手写状态编号。5.3 终态判定条件写错导致DFA空接受现象生成的DFA一个接受状态都没有无论什么串都拒绝。原因子集构造法判断一个DFA状态是否为终态要看子集 nfa.accepts是否非空。有人写成子集 nfa.accepts要求子集和接受状态集合完全相等这在绝大多数情况下都成立不了——一个子集包含了接受状态同时还带着一堆非接受状态按等值判断就被漏掉了。解决统一用交集判断if subset nfa.accepts不要用等值。写完转换函数后拿1101这种一步到位的短串先验证一遍能接受就说明终态判断没问题。5.4 未定义转移导致KeyError死机现象程序在跑子集构造时突然抛出KeyError错误指向dtran[(T_id, symbol)]那一行。原因move返回空集合时epsilon闭包也是空集合你把它当成一个正常状态加进dstates在后面查转移表时自然找不到。或者反过来DFA对某个符号根本没有定义转移模拟读取时直接崩溃。解决move和闭包返回空集时直接跳过不要加入dstates读取DFA时用dtran.get((cur, a), None)代替直接索引查不到就返回拒绝。这两个习惯能挡住绝大多数因为转移表稀疏导致的问题。6. 不靠肉眼验证随机串对拍与状态图可视化6.1 穷举短串对拍NFA和DFA转换完了怎么说你写的DFA和原NFA是等价的光靠几个手推串不够。我习惯写一个穷举对拍器把长度不超过5的二进制串全部枚举出来分别喂给NFA模拟器和DFA模拟器对比接受/拒绝结果只要有一个不一致几乎可以断定某个环节出错了。def nfa_accepts(nfa, s): current nfa.epsilon_closure({nfa.start}) for ch in s: current nfa.epsilon_closure(nfa.move(current, ch)) if not current: return False return bool(current nfa.accepts) def dfa_accepts(dtran, start, accepts, s): cur start for ch in s: cur dtran.get((cur, ch)) if cur is None: return False return cur in accepts import itertools alphabet [0, 1] for length in range(6): for chars in itertools.product(alphabet, repeatlength): s .join(chars) if nfa_accepts(nfa, s) ! dfa_accepts(min_dtran, 0, min_accepts, s): print(不一致:, s)NFA模拟器的逻辑就是反复做闭包和moveDFA模拟器直接查表。注意对拍时用的DFA状态编号要和你验证的是同一个版本最小化前后的状态编号不一致别拿最小化后的表和原NFA对拍那会误报。对拍输出为空就说明转换正确。6.2 把DFA画出来当实验配图实验报告里光有转移表还不够很多老师要求画状态图。装好graphviz后把min_dtran的每个键值对转成一条A - B [label0]的dot语句输出一个dot文件命令行用dot -Tpng dfa.dot -o dfa.png就能出图。不想装环境的话就用上面的格式化函数把转移表打印出来手工画在纸上也不复杂。这段对拍脚本我从那以后每次跑转换实验都会先跑一遍不通过就不往下做最小化省下的排查时间远比写脚本花的时间多。希望帮到你。本文还有配套的精品资源点击获取