简介基于Python实现的编译原理课程设计资源包围绕正则表达式转NFA、NFA确定化及DFA最小化三个核心环节提供完整可运行的Python源码与配套说明文档适合计算机专业学生学习编译原理或完成形式语言作业时参考。压缩包共9个文件主要包括3个Python脚本、3张演示图片、2个Markdown文档及1个License文件整体大小仅243KB结构清晰。其中三个Python脚本分别对应自动机构建、确定化与最小化算法配合README和作业说明可快速理解实现思路代码注释清晰自带演示图片便于对照文档调试运行。资源已有355人学习下载内容覆盖幂集构造法、Hopcroft算法等关键知识点并配有图示与实验报告能帮助读者结合代码深入理解自动机理论提升编译原理实践能力。从正则表达式到最小化DFA的完整链路均有可执行程序支撑既能用于编译原理课程设计也为后续词法分析器开发打下基础。1. 正则表达式到自动机把编译原理作业做成状态转移表看着像数学题的NFA确定化和DFA最小化落到Python里其实只需要处理三个数据结构状态编号、转移字典、状态集合。这个课程设计把编译原理第一次作业中的正则式转NFA、NFA确定化和DFA最小化拆成三个独立脚本正好对应一个可运行的编译器前端玩具。对想深入理解re模块背后机制的开发者来说手动实现一遍要比直接背诵定义有用得多。我们不讨论如何调用re.match而是研究模式本身如何变成一张可查询的转移表。整个流程可以拆成三张表NFA的转移表、DFA的子集编号表、最小化后的等价类划分表搞清楚它们之间怎么互相转换比记住术语更重要。2. 正则式转 NFAThompson 构造法与状态图数据结构2.1 用转移字典表达“同字符多走向”省掉图类NFA最直观的落地方式是给每个状态分配一个整数用元组(from_state, symbol)作为键值是一个由目标状态组成的集合。这样一个字典就同时表达了“在状态1读入a可以到2或3”和“从状态1不读任何字符就跳到5”两种语义。与自定义Graph类相比字典元组键的查询复杂度是O(1)后续幂集构造需要反复查找某个状态集对某个字符的后继这个选择能省掉不少循环。class NFA: def __init__(self): self.start -1 # 起始状态编号 self.accept -1 # 唯一接受状态编号 self.transitions {} # {(src, symbol): set(dst)} self._next_id 0 def new_state(self): sid self._next_id self._next_id 1 return sid def add_transition(self, src, dst, symbol): self.transitions.setdefault((src, symbol), set()).add(dst)这段代码定义了自动机的最小骨架。new_state每次返回一个不重复的状态号避免在拼接子NFA时手工维护计数器add_transition用setdefault给同一个(src, symbol)追加目标正好对应NFA在同输入字符下可以有多个后续转移的特性。symbol允许传None例如 add_transition(1, 5, None) 表示从状态1无需消耗任何输入就能到达状态5这就是ε边。实际项目里我会在这套类上再加一个用于调试的name字段否则画图时只能看到数字。2.2 后缀式与三规则连接、并、闭包正则表达式转NFA的常见做法是先做词法预处理把中缀表达式换成后缀式再用栈组装片段。预处理时要插入显式连接符.因为ab在自动机构造里应当被理解成“a随后接b”而不是一个字符。def insert_concat(regex: str) - str: out [] for i, ch in enumerate(regex): out.append(ch) if i 1 len(regex): nxt regex[i 1] # 当前不是左括号或并运算符且下一个不是右括号、并或闭包时补连接符 if ch not in |( and nxt not in |)*: out.append(.) return .join(out) def regex_to_postfix(regex: str) - str: expr insert_concat(regex) pre {*: 3, .: 2, |: 1, (: 0} stack, out [], [] for ch in expr: if ch (: stack.append(ch) elif ch ): while stack and stack[-1] ! (: out.append(stack.pop()) stack.pop() elif ch in pre: while stack and pre[stack[-1]] pre[ch]: out.append(stack.pop()) stack.append(ch) else: out.append(ch) # 普通元素字符 while stack: out.append(stack.pop()) return .join(out)insert_concat会在相邻两个元素之间插入.使优先级处理像四则运算一样明确。regex_to_postfix维护一个运算符栈左括号直接入栈右括号弹出到左括号为止运算符在弹出所有优先级不低于自己的运算符后进站。预定义pre[(] 0是为了防止左括号被运算符比较弹出。注意返回的后缀串中普通字符和.、|、*混在一起下一步构建NFA需要区分它们。有了后缀式就可以用Thompson构造法边扫描边组装片段。class Fragment: def __init__(self, start, accept): self.start start self.accept accept def build_nfa(postfix: str) - NFA: nfa NFA() stack [] for ch in postfix: if ch .: right stack.pop(); left stack.pop() nfa.add_transition(left.accept, right.start, None) stack.append(Fragment(left.start, right.accept)) elif ch |: right stack.pop(); left stack.pop() s nfa.new_state(); a nfa.new_state() nfa.add_transition(s, left.start, None) nfa.add_transition(s, right.start, None) nfa.add_transition(left.accept, a, None) nfa.add_transition(right.accept, a, None) stack.append(Fragment(s, a)) elif ch *: f stack.pop() s nfa.new_state(); a nfa.new_state() nfa.add_transition(s, f.start, None) nfa.add_transition(s, a, None) nfa.add_transition(f.accept, f.start, None) nfa.add_transition(f.accept, a, None) stack.append(Fragment(s, a)) else: s nfa.new_state(); a nfa.new_state() nfa.add_transition(s, a, ch) stack.append(Fragment(s, a)) frag stack.pop() nfa.start frag.start nfa.accept frag.accept return nfa连接运算符直接把前一个片段的接受状态与后一个片段的起始状态用ε边相连新的接受状态改为后段的accept。并运算符新建一个起始状态分别指向两个分支的start再新建一个接受状态承接两个分支的accept。闭包运算符在片段的首尾之间加环从新建start可以跳过整个片段也可以进入片段片段结束后既可以回到片段开头重复也可以直接跳到新建接受状态。整个构造过程始终保证每个片段只有一个入口和一个出口这个性质让后面的NFA确定化只需要处理单一接受状态。需要注意这里没有处理转义符如果输入里有\这类转义需要在insert_concat之前把转义后的字符替换成不冲突的占位符。下表归纳了三种基本构造的图形含义正则式构造新增状态数添加的边说明连接r1 r20r1.accept - r2.start (ε)首尾相接并r1|r22start - r1/r2.startr1/r2.accept - accept (ε)两条分支汇聚闭包r*2start - r.startstart - acceptr.accept - r.startr.accept - accept (ε)可循环可跳过2.3 ε边是免费移动不是可有可无ε边让状态能在不消耗输入字符的情况下跳转是Thompson构造的粘合剂。没有ε边a|b无法在不引入复杂返回逻辑的情况下共用接受状态a*也无法同时表达“跳过”和“重复”两条路径。正是因为所有复杂结构都有ε边后续NFA确定化才必须引入epsilon闭包把不读字符就能到达的所有状态先收拢在一起。很多课程设计卡在第六步就是因为第一步构造NFA时忽略了ε边的存在导致闭包总是空集。3. NFA 确定化幂集构造法与子集编码3.1 epsilon_closure 的迭代写法幂集构造的第一步是计算ε闭包。给定一个NFA状态集闭包包含这些状态本身以及沿着ε边能到达的所有状态。递归写法代码短但遇到长ε链容易触发Python递归上限所以我一般用栈迭代。def epsilon_closure(nfa: NFA, states) - frozenset: stack list(states) closure set(states) while stack: s stack.pop() for nxt in nfa.transitions.get((s, None), set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return frozenset(closure)这里把结果返回成frozenset目的是让闭包结果可以直接作为字典键。Python的set不可哈希不能放进dict当作keyfrozenset则可以。闭包计算时只查(s, None)这个键其他字符的转移不受影响。需要注意传入的states本身可能已经包含若干状态闭包不会漏掉它们自己。3.2 子集构造主循环从闭包到DFA有了闭包move和确定化主循环就顺理成章。move返回从当前状态集读入一个字符后能到达的原始NFA状态集合但不处理这些状态后续的ε边因此每次move之后都要立刻再算一次闭包才能得到一个完整的新DFA子集。def move(nfa: NFA, states, symbol): result set() for s in states: for nxt in nfa.transitions.get((s, symbol), set()): result.add(nxt) return result def nfa_to_dfa(nfa: NFA, alphabet: set[str]): start_closure epsilon_closure(nfa, {nfa.start}) dfa_states {start_closure: 0} queue [start_closure] dfa_trans {} dfa_accepts set() while queue: subset queue.pop() cur_id dfa_states[subset] if nfa.accept in subset: dfa_accepts.add(cur_id) for sym in alphabet: reached epsilon_closure(nfa, move(nfa, subset, sym)) if not reached: continue if reached not in dfa_states: dfa_states[reached] len(dfa_states) queue.append(reached) dfa_trans[(cur_id, sym)] dfa_states[reached] return { num_states: len(dfa_states), start: dfa_states[start_closure], accept: dfa_accepts, transitions: dfa_trans }主循环用queue作为未标记DFA状态列表每次弹出一个子集先判断它是否包含原NFA的接受状态再对字母表中每个字符执行“move closure”。新出现的子集立刻登记到dfa_states并分配编号同时压入队列等待处理。dfa_trans记录的是整数源状态、输入字符、目标编号这个结构比保存frozenset更紧凑后续最小化和可视化都可以直接消费。参数alphabet需要人工从原始正则式中提取不能从转移表里偷懒推断因为某些在表达式里出现过的字符可能没有出现在最终NFA边上虽然实际很少见保持一致才不会丢转移。下表把子集构造的过程拆成五步方便对照代码调试阶段做了什么对应变量初始化计算初始闭包作为DFA起点start_closure, dfa_states取未标记状态从队列弹出一个子集queue, subset标记接受检查子集是否含原NFA接受状态dfa_accepts生成转移对每个sym执行move和closuredfa_trans去重与分配编号新子集登记编号并加入队列dfa_states, len3.3 子集爆炸最坏情况不是作业重点理论上n个状态的NFA可以对应到2的n次方个DFA状态(a|b)*a(a|b)^n这种经典模式会让DFA状态数随n指数增长。课程设计通常不会压到这种规模但如果你在测试时看到状态数疯涨先怀疑是不是字母表里混入了None或者退出了多余字符。实用优化是把字符按类别聚合例如把0到9合并成digit类再参与构造这能在不改变语言的前提下把很多等价的分支合并掉。正常作业里几十个状态已经算多接下来的最小化才是省状态的主要手段。4. DFA 最小化Hopcroft 划分与不可区分状态合并4.1 先剔除不可达状态再做划分最小化前必须先生成可达状态集合。不可达状态比如那些从起始状态永远走不到的死编号会让初始划分多出无意义的块也会让最终画图时状态数量虚高。用BFS收集可达集合最简单def reachable_states(dfa): seen set() stack [dfa[start]] while stack: s stack.pop() if s in seen: continue seen.add(s) for (src, ch), dst in dfa[transitions].items(): if src s: stack.append(dst) return seen这个函数依赖dfa[transitions]里键的格式也就是上一章nfa_to_dfa返回的(src, symbol) - dst。如果自己定义了别的转移表结构只要保证 src 能从元组里正确取出来就行。遍历所有边找srcs的方式在大状态集上偏慢但几万个状态内都能接受而且只跑一次不值得为此把结构改成邻接表。4.2 划分细化签名决定是否拆块最小化的核心是把所有状态划分成若干等价类。两个状态等价意味着从它们出发、对任意输入串要么都接受要么都拒绝。算法从接受状态和非接受状态两个大块开始反复计算每个状态读入各字符后落入哪个块如果同一块里的状态得到的签名不同就把它们拆开。def minimize_dfa(dfa): reach reachable_states(dfa) old_to_new {s: i for i, s in enumerate(sorted(reach))} start old_to_new[dfa[start]] accept {old_to_new[s] for s in dfa[accept] if s in reach} alphabet sorted({ch for _, ch in dfa[transitions]}) transitions {} for (s, ch), dst in dfa[transitions].items(): if s in reach and dst in reach: transitions[(old_to_new[s], ch)] old_to_new[dst] state_count len(old_to_new) acc frozenset(accept) non frozenset(set(range(state_count)) - acc) groups [acc] ([non] if non else []) while True: block_of {} for gid, group in enumerate(groups): for s in group: block_of[s] gid new_groups [] for group in groups: parts {} for s in group: sig tuple( block_of.get(transitions.get((s, ch), -1), -1) for ch in alphabet ) parts.setdefault(sig, []).append(s) for states in parts.values(): new_groups.append(frozenset(states)) if len(new_groups) len(groups): groups new_groups break groups new_groups state_of_rep {} for s in range(state_count): for gid, group in enumerate(groups): if s in group: state_of_rep[s] gid break min_start state_of_rep[start] min_accept {state_of_rep[s] for s in accept} min_trans {} for (s, ch), dst in transitions.items(): min_trans[(state_of_rep[s], ch)] state_of_rep[dst] return { num_states: len(groups), start: min_start, accept: min_accept, transitions: min_trans }这段代码先对可达状态重新编号保证状态号是连续整数alphabet从转移键里提取保证所有字符都被纳入签名计算。初始划分如果只有接受状态而没有非接受状态需要跳过空的non块。循环里每个状态的签名是“读入每个字符后所属块编号”字符缺失转移统一为-1这样不会因为某个状态少一条边而报错。当块数不再变化时每个块就是一个等价类。最后用每个块作为最小DFA的一个状态块中任意一个原始状态都能代表整块。因为最终转移表中可能出现同一个边重复写入后写覆盖先写但同一(src,ch)到同一dst覆盖不会改变语义。参数上dfa的accept必须是一个set而不是单个整数如果之前nfa_to_dfa返回的是集合这里就可以直接传入。缺失转移用-1模拟这在作业里够用但严谨做法是补一个非接受死状态避免出现“对某字符没有定义转移”这种不完全DFA。补法是在minimize之前遍历全部状态和字符把没有边的位置指向新状态。下面把三类常用最小化算法放在一起对比算法时间复杂度核心思路实现难度表填涂法O(n^2)标记所有可区分状态对简单划分细化O(n^2)按转移目标所属块拆分中等HopcroftO(n log n)用待细化块队列优化较复杂上面代码属于划分细化结果与Hopcroft相同只是常数大一些。课程设计的DFA状态数一般不超过百个直接跑划分细化足够。如果后续要处理上千状态的词法器再考虑用队列版的Hopcroft。4.3 为什么会停在不动点有些同学在第一次迭代后看到块数没变就以为算法结束其实可能只是这轮没拆下一轮还会拆。例如状态A和B都落在接受块读入a后也都到接受块但再读入b时一个到接受、一个到拒绝这只有在第二轮签名里才会暴露。所以必须循环到块数完全不增长才能保证稳定。调试时可以在每次循环结束打印每个块里包含的状态编号对照“两个状态是否能区分”的手写推导很快就能发现问题。5. 作业检查和实际技巧Graphviz 可视化与死状态补全5.1 用 DOT 导出状态图手写转移表只能看到数字不如把最小化前后的DFA各自导出一张图。Graphviz的DOT格式很简单def dfa_to_dot(dfa, pathdfa.dot): lines [digraph DFA {, rankdirLR;] for s in range(dfa[num_states]): shape doublecircle if s in dfa[accept] else circle lines.append(f {s} [shape{shape}];) for (s, ch), dst in dfa[transitions].items(): lines.append(f {s} - {dst} [label{ch}];) lines.append(}) with open(path, w, encodingutf-8) as f: f.write(\n.join(lines))生成文件后在命令行跑dot -Tpng dfa.dot -o dfa.png就能看到接受状态是双圈其他状态是单圈的图。对比最小化前后的状态数如果最小化后仍然有等于最大状态数的节点说明划分细化没有生效优先检查alphabet是否包含全部字符以及转移表里是否忘了清理不可达状态。5.2 随机字符串验证最小化前后等价最小化合不合法光看状态数减少不够要证明任何输入串在老DFA和新DFA上的接受结果一致。写一个simulate函数对同一串输入分别跑两个DFA。def simulate(dfa, s: str) - bool: state dfa[start] for ch in s: if (state, ch) not in dfa[transitions]: return False state dfa[transitions][(state, ch)] return state in dfa[accept]验证脚本可以随机生成几千个只包含字母表字符的字符串逐个比较simulate(old, test)和simulate(new, test)。如果脚本里既跑nfa_to_dfa原始结果也跑minimize_dfa结果还能顺带验证确定化是否漏字符。自动化测试比肉眼盯着状态图可靠得多作业报告里贴一段断言通过的控制台输出也更有说服力。5.3 补死状态让DFA“完全定义”最后补一个常见扣分点如果某个状态对某个输入字符没有转移标准DFA会隐式进死状态且永远不会被接受。幂集构造时我直接跳过了空子集导致最小化阶段用-1占位。作业里为了严谨可以在minimize_dfa之前给DFA补全缺失转移指向一个新增的非接受状态。补法是在转移表里对所有状态和alphabet做一次双重循环遇到缺失边就填到死状态。这个死状态也要参与可达性判断吗不需要它不可达正常流程会在reachable_states阶段被剔除。但如果你把死状态当作可达状态加进初始划分最小化结果会多出一个钝块反而把图弄乱。所以建议顺序是先补全死状态再跑reachable最后划分。本文还有配套的精品资源点击获取 
长河君 · 2026/9/12 19:07:36 · 阅读 1.2k 正则表达式到自动机：Python实现NFA确定化与DFA最小化
简介基于Python实现的编译原理课程设计资源包围绕正则表达式转NFA、NFA确定化及DFA最小化三个核心环节提供完整可运行的Python源码与配套说明文档适合计算机专业学生学习编译原理或完成形式语言作业时参考。压缩包共9个文件主要包括3个Python脚本、3张演示图片、2个Markdown文档及1个License文件整体大小仅243KB结构清晰。其中三个Python脚本分别对应自动机构建、确定化与最小化算法配合README和作业说明可快速理解实现思路代码注释清晰自带演示图片便于对照文档调试运行。资源已有355人学习下载内容覆盖幂集构造法、Hopcroft算法等关键知识点并配有图示与实验报告能帮助读者结合代码深入理解自动机理论提升编译原理实践能力。从正则表达式到最小化DFA的完整链路均有可执行程序支撑既能用于编译原理课程设计也为后续词法分析器开发打下基础。1. 正则表达式到自动机把编译原理作业做成状态转移表看着像数学题的NFA确定化和DFA最小化落到Python里其实只需要处理三个数据结构状态编号、转移字典、状态集合。这个课程设计把编译原理第一次作业中的正则式转NFA、NFA确定化和DFA最小化拆成三个独立脚本正好对应一个可运行的编译器前端玩具。对想深入理解re模块背后机制的开发者来说手动实现一遍要比直接背诵定义有用得多。我们不讨论如何调用re.match而是研究模式本身如何变成一张可查询的转移表。整个流程可以拆成三张表NFA的转移表、DFA的子集编号表、最小化后的等价类划分表搞清楚它们之间怎么互相转换比记住术语更重要。2. 正则式转 NFAThompson 构造法与状态图数据结构2.1 用转移字典表达“同字符多走向”省掉图类NFA最直观的落地方式是给每个状态分配一个整数用元组(from_state, symbol)作为键值是一个由目标状态组成的集合。这样一个字典就同时表达了“在状态1读入a可以到2或3”和“从状态1不读任何字符就跳到5”两种语义。与自定义Graph类相比字典元组键的查询复杂度是O(1)后续幂集构造需要反复查找某个状态集对某个字符的后继这个选择能省掉不少循环。class NFA: def __init__(self): self.start -1 # 起始状态编号 self.accept -1 # 唯一接受状态编号 self.transitions {} # {(src, symbol): set(dst)} self._next_id 0 def new_state(self): sid self._next_id self._next_id 1 return sid def add_transition(self, src, dst, symbol): self.transitions.setdefault((src, symbol), set()).add(dst)这段代码定义了自动机的最小骨架。new_state每次返回一个不重复的状态号避免在拼接子NFA时手工维护计数器add_transition用setdefault给同一个(src, symbol)追加目标正好对应NFA在同输入字符下可以有多个后续转移的特性。symbol允许传None例如 add_transition(1, 5, None) 表示从状态1无需消耗任何输入就能到达状态5这就是ε边。实际项目里我会在这套类上再加一个用于调试的name字段否则画图时只能看到数字。2.2 后缀式与三规则连接、并、闭包正则表达式转NFA的常见做法是先做词法预处理把中缀表达式换成后缀式再用栈组装片段。预处理时要插入显式连接符.因为ab在自动机构造里应当被理解成“a随后接b”而不是一个字符。def insert_concat(regex: str) - str: out [] for i, ch in enumerate(regex): out.append(ch) if i 1 len(regex): nxt regex[i 1] # 当前不是左括号或并运算符且下一个不是右括号、并或闭包时补连接符 if ch not in |( and nxt not in |)*: out.append(.) return .join(out) def regex_to_postfix(regex: str) - str: expr insert_concat(regex) pre {*: 3, .: 2, |: 1, (: 0} stack, out [], [] for ch in expr: if ch (: stack.append(ch) elif ch ): while stack and stack[-1] ! (: out.append(stack.pop()) stack.pop() elif ch in pre: while stack and pre[stack[-1]] pre[ch]: out.append(stack.pop()) stack.append(ch) else: out.append(ch) # 普通元素字符 while stack: out.append(stack.pop()) return .join(out)insert_concat会在相邻两个元素之间插入.使优先级处理像四则运算一样明确。regex_to_postfix维护一个运算符栈左括号直接入栈右括号弹出到左括号为止运算符在弹出所有优先级不低于自己的运算符后进站。预定义pre[(] 0是为了防止左括号被运算符比较弹出。注意返回的后缀串中普通字符和.、|、*混在一起下一步构建NFA需要区分它们。有了后缀式就可以用Thompson构造法边扫描边组装片段。class Fragment: def __init__(self, start, accept): self.start start self.accept accept def build_nfa(postfix: str) - NFA: nfa NFA() stack [] for ch in postfix: if ch .: right stack.pop(); left stack.pop() nfa.add_transition(left.accept, right.start, None) stack.append(Fragment(left.start, right.accept)) elif ch |: right stack.pop(); left stack.pop() s nfa.new_state(); a nfa.new_state() nfa.add_transition(s, left.start, None) nfa.add_transition(s, right.start, None) nfa.add_transition(left.accept, a, None) nfa.add_transition(right.accept, a, None) stack.append(Fragment(s, a)) elif ch *: f stack.pop() s nfa.new_state(); a nfa.new_state() nfa.add_transition(s, f.start, None) nfa.add_transition(s, a, None) nfa.add_transition(f.accept, f.start, None) nfa.add_transition(f.accept, a, None) stack.append(Fragment(s, a)) else: s nfa.new_state(); a nfa.new_state() nfa.add_transition(s, a, ch) stack.append(Fragment(s, a)) frag stack.pop() nfa.start frag.start nfa.accept frag.accept return nfa连接运算符直接把前一个片段的接受状态与后一个片段的起始状态用ε边相连新的接受状态改为后段的accept。并运算符新建一个起始状态分别指向两个分支的start再新建一个接受状态承接两个分支的accept。闭包运算符在片段的首尾之间加环从新建start可以跳过整个片段也可以进入片段片段结束后既可以回到片段开头重复也可以直接跳到新建接受状态。整个构造过程始终保证每个片段只有一个入口和一个出口这个性质让后面的NFA确定化只需要处理单一接受状态。需要注意这里没有处理转义符如果输入里有\这类转义需要在insert_concat之前把转义后的字符替换成不冲突的占位符。下表归纳了三种基本构造的图形含义正则式构造新增状态数添加的边说明连接r1 r20r1.accept - r2.start (ε)首尾相接并r1|r22start - r1/r2.startr1/r2.accept - accept (ε)两条分支汇聚闭包r*2start - r.startstart - acceptr.accept - r.startr.accept - accept (ε)可循环可跳过2.3 ε边是免费移动不是可有可无ε边让状态能在不消耗输入字符的情况下跳转是Thompson构造的粘合剂。没有ε边a|b无法在不引入复杂返回逻辑的情况下共用接受状态a*也无法同时表达“跳过”和“重复”两条路径。正是因为所有复杂结构都有ε边后续NFA确定化才必须引入epsilon闭包把不读字符就能到达的所有状态先收拢在一起。很多课程设计卡在第六步就是因为第一步构造NFA时忽略了ε边的存在导致闭包总是空集。3. NFA 确定化幂集构造法与子集编码3.1 epsilon_closure 的迭代写法幂集构造的第一步是计算ε闭包。给定一个NFA状态集闭包包含这些状态本身以及沿着ε边能到达的所有状态。递归写法代码短但遇到长ε链容易触发Python递归上限所以我一般用栈迭代。def epsilon_closure(nfa: NFA, states) - frozenset: stack list(states) closure set(states) while stack: s stack.pop() for nxt in nfa.transitions.get((s, None), set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return frozenset(closure)这里把结果返回成frozenset目的是让闭包结果可以直接作为字典键。Python的set不可哈希不能放进dict当作keyfrozenset则可以。闭包计算时只查(s, None)这个键其他字符的转移不受影响。需要注意传入的states本身可能已经包含若干状态闭包不会漏掉它们自己。3.2 子集构造主循环从闭包到DFA有了闭包move和确定化主循环就顺理成章。move返回从当前状态集读入一个字符后能到达的原始NFA状态集合但不处理这些状态后续的ε边因此每次move之后都要立刻再算一次闭包才能得到一个完整的新DFA子集。def move(nfa: NFA, states, symbol): result set() for s in states: for nxt in nfa.transitions.get((s, symbol), set()): result.add(nxt) return result def nfa_to_dfa(nfa: NFA, alphabet: set[str]): start_closure epsilon_closure(nfa, {nfa.start}) dfa_states {start_closure: 0} queue [start_closure] dfa_trans {} dfa_accepts set() while queue: subset queue.pop() cur_id dfa_states[subset] if nfa.accept in subset: dfa_accepts.add(cur_id) for sym in alphabet: reached epsilon_closure(nfa, move(nfa, subset, sym)) if not reached: continue if reached not in dfa_states: dfa_states[reached] len(dfa_states) queue.append(reached) dfa_trans[(cur_id, sym)] dfa_states[reached] return { num_states: len(dfa_states), start: dfa_states[start_closure], accept: dfa_accepts, transitions: dfa_trans }主循环用queue作为未标记DFA状态列表每次弹出一个子集先判断它是否包含原NFA的接受状态再对字母表中每个字符执行“move closure”。新出现的子集立刻登记到dfa_states并分配编号同时压入队列等待处理。dfa_trans记录的是整数源状态、输入字符、目标编号这个结构比保存frozenset更紧凑后续最小化和可视化都可以直接消费。参数alphabet需要人工从原始正则式中提取不能从转移表里偷懒推断因为某些在表达式里出现过的字符可能没有出现在最终NFA边上虽然实际很少见保持一致才不会丢转移。下表把子集构造的过程拆成五步方便对照代码调试阶段做了什么对应变量初始化计算初始闭包作为DFA起点start_closure, dfa_states取未标记状态从队列弹出一个子集queue, subset标记接受检查子集是否含原NFA接受状态dfa_accepts生成转移对每个sym执行move和closuredfa_trans去重与分配编号新子集登记编号并加入队列dfa_states, len3.3 子集爆炸最坏情况不是作业重点理论上n个状态的NFA可以对应到2的n次方个DFA状态(a|b)*a(a|b)^n这种经典模式会让DFA状态数随n指数增长。课程设计通常不会压到这种规模但如果你在测试时看到状态数疯涨先怀疑是不是字母表里混入了None或者退出了多余字符。实用优化是把字符按类别聚合例如把0到9合并成digit类再参与构造这能在不改变语言的前提下把很多等价的分支合并掉。正常作业里几十个状态已经算多接下来的最小化才是省状态的主要手段。4. DFA 最小化Hopcroft 划分与不可区分状态合并4.1 先剔除不可达状态再做划分最小化前必须先生成可达状态集合。不可达状态比如那些从起始状态永远走不到的死编号会让初始划分多出无意义的块也会让最终画图时状态数量虚高。用BFS收集可达集合最简单def reachable_states(dfa): seen set() stack [dfa[start]] while stack: s stack.pop() if s in seen: continue seen.add(s) for (src, ch), dst in dfa[transitions].items(): if src s: stack.append(dst) return seen这个函数依赖dfa[transitions]里键的格式也就是上一章nfa_to_dfa返回的(src, symbol) - dst。如果自己定义了别的转移表结构只要保证 src 能从元组里正确取出来就行。遍历所有边找srcs的方式在大状态集上偏慢但几万个状态内都能接受而且只跑一次不值得为此把结构改成邻接表。4.2 划分细化签名决定是否拆块最小化的核心是把所有状态划分成若干等价类。两个状态等价意味着从它们出发、对任意输入串要么都接受要么都拒绝。算法从接受状态和非接受状态两个大块开始反复计算每个状态读入各字符后落入哪个块如果同一块里的状态得到的签名不同就把它们拆开。def minimize_dfa(dfa): reach reachable_states(dfa) old_to_new {s: i for i, s in enumerate(sorted(reach))} start old_to_new[dfa[start]] accept {old_to_new[s] for s in dfa[accept] if s in reach} alphabet sorted({ch for _, ch in dfa[transitions]}) transitions {} for (s, ch), dst in dfa[transitions].items(): if s in reach and dst in reach: transitions[(old_to_new[s], ch)] old_to_new[dst] state_count len(old_to_new) acc frozenset(accept) non frozenset(set(range(state_count)) - acc) groups [acc] ([non] if non else []) while True: block_of {} for gid, group in enumerate(groups): for s in group: block_of[s] gid new_groups [] for group in groups: parts {} for s in group: sig tuple( block_of.get(transitions.get((s, ch), -1), -1) for ch in alphabet ) parts.setdefault(sig, []).append(s) for states in parts.values(): new_groups.append(frozenset(states)) if len(new_groups) len(groups): groups new_groups break groups new_groups state_of_rep {} for s in range(state_count): for gid, group in enumerate(groups): if s in group: state_of_rep[s] gid break min_start state_of_rep[start] min_accept {state_of_rep[s] for s in accept} min_trans {} for (s, ch), dst in transitions.items(): min_trans[(state_of_rep[s], ch)] state_of_rep[dst] return { num_states: len(groups), start: min_start, accept: min_accept, transitions: min_trans }这段代码先对可达状态重新编号保证状态号是连续整数alphabet从转移键里提取保证所有字符都被纳入签名计算。初始划分如果只有接受状态而没有非接受状态需要跳过空的non块。循环里每个状态的签名是“读入每个字符后所属块编号”字符缺失转移统一为-1这样不会因为某个状态少一条边而报错。当块数不再变化时每个块就是一个等价类。最后用每个块作为最小DFA的一个状态块中任意一个原始状态都能代表整块。因为最终转移表中可能出现同一个边重复写入后写覆盖先写但同一(src,ch)到同一dst覆盖不会改变语义。参数上dfa的accept必须是一个set而不是单个整数如果之前nfa_to_dfa返回的是集合这里就可以直接传入。缺失转移用-1模拟这在作业里够用但严谨做法是补一个非接受死状态避免出现“对某字符没有定义转移”这种不完全DFA。补法是在minimize之前遍历全部状态和字符把没有边的位置指向新状态。下面把三类常用最小化算法放在一起对比算法时间复杂度核心思路实现难度表填涂法O(n^2)标记所有可区分状态对简单划分细化O(n^2)按转移目标所属块拆分中等HopcroftO(n log n)用待细化块队列优化较复杂上面代码属于划分细化结果与Hopcroft相同只是常数大一些。课程设计的DFA状态数一般不超过百个直接跑划分细化足够。如果后续要处理上千状态的词法器再考虑用队列版的Hopcroft。4.3 为什么会停在不动点有些同学在第一次迭代后看到块数没变就以为算法结束其实可能只是这轮没拆下一轮还会拆。例如状态A和B都落在接受块读入a后也都到接受块但再读入b时一个到接受、一个到拒绝这只有在第二轮签名里才会暴露。所以必须循环到块数完全不增长才能保证稳定。调试时可以在每次循环结束打印每个块里包含的状态编号对照“两个状态是否能区分”的手写推导很快就能发现问题。5. 作业检查和实际技巧Graphviz 可视化与死状态补全5.1 用 DOT 导出状态图手写转移表只能看到数字不如把最小化前后的DFA各自导出一张图。Graphviz的DOT格式很简单def dfa_to_dot(dfa, pathdfa.dot): lines [digraph DFA {, rankdirLR;] for s in range(dfa[num_states]): shape doublecircle if s in dfa[accept] else circle lines.append(f {s} [shape{shape}];) for (s, ch), dst in dfa[transitions].items(): lines.append(f {s} - {dst} [label{ch}];) lines.append(}) with open(path, w, encodingutf-8) as f: f.write(\n.join(lines))生成文件后在命令行跑dot -Tpng dfa.dot -o dfa.png就能看到接受状态是双圈其他状态是单圈的图。对比最小化前后的状态数如果最小化后仍然有等于最大状态数的节点说明划分细化没有生效优先检查alphabet是否包含全部字符以及转移表里是否忘了清理不可达状态。5.2 随机字符串验证最小化前后等价最小化合不合法光看状态数减少不够要证明任何输入串在老DFA和新DFA上的接受结果一致。写一个simulate函数对同一串输入分别跑两个DFA。def simulate(dfa, s: str) - bool: state dfa[start] for ch in s: if (state, ch) not in dfa[transitions]: return False state dfa[transitions][(state, ch)] return state in dfa[accept]验证脚本可以随机生成几千个只包含字母表字符的字符串逐个比较simulate(old, test)和simulate(new, test)。如果脚本里既跑nfa_to_dfa原始结果也跑minimize_dfa结果还能顺带验证确定化是否漏字符。自动化测试比肉眼盯着状态图可靠得多作业报告里贴一段断言通过的控制台输出也更有说服力。5.3 补死状态让DFA“完全定义”最后补一个常见扣分点如果某个状态对某个输入字符没有转移标准DFA会隐式进死状态且永远不会被接受。幂集构造时我直接跳过了空子集导致最小化阶段用-1占位。作业里为了严谨可以在minimize_dfa之前给DFA补全缺失转移指向一个新增的非接受状态。补法是在转移表里对所有状态和alphabet做一次双重循环遇到缺失边就填到死状态。这个死状态也要参与可达性判断吗不需要它不可达正常流程会在reachable_states阶段被剔除。但如果你把死状态当作可达状态加进初始划分最小化结果会多出一个钝块反而把图弄乱。所以建议顺序是先补全死状态再跑reachable最后划分。本文还有配套的精品资源点击获取