尧图网页设计 
简介基于Python实现正则式转NFA、NFA确定化、DFA最小化的编译原理课程设计资料包面向正在学习形式语言与自动机理论的学生也适合需要动手实践的开发者可用于课程作业、实验报告或相关毕设参考。代码与文档完整覆盖三个核心环节从正则表达式的语法结构构建对应的NFA再利用幂集构造法消除不确定转移得到DFA最后通过状态等价类合并完成DFA最小化实现脉络清晰。压缩包共9个文件以3个Python脚本分别对应上述三个模块辅以3张图片文件、2份Markdown说明和1份许可证文件整体仅243KB便于快速下载与对照阅读。已有355人浏览学习。通过源码对照报告与图示读者可掌握自动机数据结构的类设计、状态转移表的存储方式、每一步转换的输入输出关系还能了解NFA中同一输入存在多条转移路径时的处理思路借此巩固编译原理知识为文本匹配、词法分析等应用打下基础。1. 这门课设看着简单却总在确定化这一步翻车正则式转 NFA、NFA 确定化、DFA 最小化这串名词第一次出现通常是在编译原理的课程项目里。我见过不少同学把正则式转 NFA 当成“按字符画状态图”结果一跑测试就翻车a(b|c)*这种分支加循环的表达式手工画都会漏掉一条回边更别说让程序稳定生成。这个题目的本质是把字符串匹配问题变成图上的可达性问题输入一串正则式输出一张行为完全等价、状态数尽可能少的确定性转移表。它直接服务于词法分析器的骨架也常出现在考研复试和手写正则引擎的面试里。适合正在做编译原理课设的学生以及想用 Python 把《编译原理》第三章真正跑通一遍的从业者。下面我从解析、构造、确定化、最小化到验证按一条可复现的路径展开。2. 先把正则式读进来中缀转后缀与 Thompson 片段构造2.1 为什么我用后缀式而不是 AST教材做法是先建 AST 再递归遍历因为人看表达式是从最外层结构看。但课程项目代码里我更喜欢先把中缀正则式改成后缀式逆波兰式原因只有一个Python 里中缀转后缀只要十几行而直接建 AST 的递归下降要处理括号深度、运算符优先级写起来容易在|和连接符的优先级上翻车。后缀表达式ab*表示a与b*连接运算符跟在操作数后面。求值时只需要一个栈完全不用管括号嵌套。所以我的第一步是先补连接符再转后缀。补连接符是个容易漏的细节正则式ab里两个字符相邻中间隐含一个“连接”运算但肉眼看不出来。我一般用这样一个函数显式插入.。PREC {|: 1, .: 2, *: 3} def insert_concat(regex: str) - str: out [] prev for ch in regex: # 前一个字符不是 ( 或 |当前字符不是 | ) *说明两个操作数相邻 if prev and prev not in (| and ch not in |)*: out.append(.) # 插入连接运算符 out.append(ch) prev ch return .join(out) def to_postfix(regex: str) - str: regex insert_concat(regex) output, stack [], [] for ch in regex: if ch.isalnum(): output.append(ch) elif ch (: stack.append(ch) elif ch ): while stack and stack[-1] ! (: output.append(stack.pop()) stack.pop() # 丢掉左括号 else: if ch not in PREC: raise ValueError(f不支持的运算符: {ch}) while stack and stack[-1] ! ( and PREC[stack[-1]] PREC[ch]: output.append(stack.pop()) stack.append(ch) while stack: output.append(stack.pop()) return .join(output)代码逻辑分三块字符直接输出括号负责改变优先级运算符弹出栈顶优先级不低于自己的元素。insert_concat的规则要记牢prev是(或|时不补因为左边是运算符ch是|、)、*时不补因为右边是运算符。这个规则不处理?、、\d这类扩展语法本文只聚焦在字母数字 | * ( )这个子集上。2.2 从后缀式到 NFA 片段状态怎么编号、边怎么存接下来是 Thompson 构造法。我习惯把 NFA 设计成三个部分起始状态、接受状态、转移关系。这里的关键取舍是状态用一个全局递增整数转移用字典存“某个状态在某个字符下能到达的状态集合”。next_id 0 def new_state() - int: global next_id next_id 1 return next_id - 1 class NFA: def __init__(self, startNone, acceptNone): self.start start if start is not None else new_state() self.accept accept if accept is not None else new_state() self.transitions {} # (from_state, char) - set(to_state) self.epsilon {} # from_state - set(to_state) def add_char(self, ch, frm, to): self.transitions.setdefault((frm, ch), set()).add(to) def add_eps(self, frm, to): self.epsilon.setdefault(frm, set()).add(to)transitions和epsilon分开存是因为确定化时运算不同字符转移直接取ε 转移要递归闭包。状态编号从 0 开始递增保证每个状态在调试输出时是干净的数字。2.3 三种拼接连接、分支、闭包的实现后缀式求值时栈里始终是“已经构造好的 NFA 片段”。遇到字符就构造单字符片段遇到.、|、*就从栈里弹出一到两个片段拼成一个新片段。def postfix_to_nfa(postfix: str) - NFA: stack [] for ch in postfix: if ch.isalnum(): nfa NFA() nfa.add_char(ch, nfa.start, nfa.accept) stack.append(nfa) elif ch *: inner stack.pop() nfa NFA() # 新起一个片段包住 inner nfa.add_eps(nfa.start, inner.start) nfa.add_eps(nfa.start, nfa.accept) nfa.add_eps(inner.accept, inner.start) nfa.add_eps(inner.accept, nfa.accept) nfa.transitions.update(inner.transitions) nfa.epsilon.update(inner.epsilon) stack.append(nfa) elif ch |: right, left stack.pop(), stack.pop() nfa NFA() nfa.add_eps(nfa.start, left.start) nfa.add_eps(nfa.start, right.start) nfa.add_eps(left.accept, nfa.accept) nfa.add_eps(right.accept, nfa.accept) nfa.transitions.update(left.transitions) nfa.transitions.update(right.transitions) nfa.epsilon.update(left.epsilon) nfa.epsilon.update(right.epsilon) stack.append(nfa) elif ch .: right, left stack.pop(), stack.pop() nfa NFA(startleft.start, acceptright.accept) nfa.add_eps(left.accept, right.start) nfa.transitions.update(left.transitions) nfa.transitions.update(right.transitions) nfa.epsilon.update(left.epsilon) nfa.epsilon.update(right.epsilon) stack.append(nfa) return stack.pop()连接操作里NFA(startleft.start, acceptright.accept)不需要新分配状态直接把左片段起始状态和右片段接受状态当作新片段的接口。闭包操作必须新建两个状态作为新片段的起止因为要引入四条 ε 边绕过内部、进入内部、从内部回归内部、从内部跳出。这四边缺一条a*的空串接受或循环接受就会少一半。2.4 字母表从哪里来确定化需要知道所有输入字符。最简单的方法是从后缀式里直接筛出可打印字符* . | ( )都不算字母。def get_alphabet(postfix: str) - set: return {ch for ch in postfix if ch.isalnum()}这一步在真正实现时要放在to_postfix之后因为后缀式里的字符就是最终 NFA 会用到的字符。常见坑是有人把中缀式里的括号也算进字符集导致确定化时多跑很多不存在的输入。另外注意这里不支持\d、[a-z]。如果评审要求支持常见做法是先做一层预处理把字符类展开成(0|1|2|...|9)这种「或」结构再进入这套流程我只在边界上说明不展开实现。3. 子集构造法确定化 NFA两个函数、一个队列、一张转移表3.1 ε-闭包与 move确定化依赖的两个基础操作NFA 和 DFA 的本质区别是NFA 在一个状态下读入一个字符可能跳到多个状态也可能不读字符就自己跳ε 转移。确定化要做的是把“当前可能在的所有状态”打包成一个 DFA 状态。这里两个函数是全部基础epsilon_closure算一个状态集合经 ε 边能到达的全体状态move算一个状态集合读入某个字符后直接能到达的全体状态。def epsilon_closure(nfa: NFA, states) - set: result set(states) # 自己必须包含在内不能从空集开始 stack list(states) while stack: s stack.pop() for t in nfa.epsilon.get(s, ()): if t not in result: result.add(t) stack.append(t) return result def move(nfa: NFA, states, ch: str) - set: result set() for s in states: for t in nfa.transitions.get((s, ch), ()): result.add(t) return resultepsilon_closure初始化直接用set(states)这是防止漏掉状态自身的关键。很多人写成result set()导致a*的空串路径第一次闭包就没把自己算进去后面全错。move只走字符边不走 ε 边返回的集合还没闭包需要在下一轮闭包时补上。3.2 子集构造法实现队列 seen 集合跑完所有状态确定化的经典算法是从初始闭包出发不断用每个字符算出新状态集合如果这个集合没出现过就入队。最终每个去重后的状态集合就是一个 DFA 状态。def subset_construct(nfa: NFA, alphabet: set): start frozenset(epsilon_closure(nfa, {nfa.start})) dfa {} finals set() states {start} queue [start] while queue: cur queue.pop(0) if nfa.accept in cur: finals.add(cur) for ch in alphabet: target frozenset(epsilon_closure(nfa, move(nfa, cur, ch))) if target: dfa[(cur, ch)] target if target not in states: states.add(target) queue.append(target) return dfa, start, finals, statesfinals是 DFA 接受状态集合判定条件是“这个状态集合里包含原 NFA 的接受状态”。判断顺序放在循环开头而不是转移内部是为了连空串这种“一开始就在终态集合里”的情况也能被标记。这里我用queue.pop(0)是图省事如果状态规模变大换成collections.deque的popleft()会更稳。3.3 用 frozenset 当 DFA 状态名不变量与坑DFA 状态是 NFA 状态集合Python 的set不能做 dict 的 key因为它是可变的。我统一用frozenset这样状态集合既能做 dict key也能放进states集合做去重。这个选择贯穿确定化和最小化全流程后面finals里的元素也全是frozenset。有个隐藏约束dfa的 key 是(frozenset, ch)打印时会很啰嗦这是正常的。调试验证时可以用编号重映射但在确定化阶段保持 frozenset 可以随时回溯“这个 DFA 状态对应哪些 NFA 状态”对排查问题极有价值。3.4 怎么求 NFA 等价的 DFA对拍自检方法确定化完后先别急着最小化我一般会立刻做一轮小型对拍随便写一个nfa_accepts和一个dfa_accepts枚举长度不超过 4 的字符串在两台“机器”上分别跑。这样可以先证明确定化这一步没有把语言搞丢再做最小化后面排错范围会小很多。def nfa_accepts(nfa: NFA, s: str) - bool: current epsilon_closure(nfa, {nfa.start}) for ch in s: current epsilon_closure(nfa, move(nfa, current, ch)) return nfa.accept in current def dfa_accepts(dfa, start, finals, s: str) - bool: cur start for ch in s: if (cur, ch) not in dfa: return False cur dfa[(cur, ch)] return cur in finalsnfa_accepts每一步都是“先 move 再关包”和确定化里的逻辑完全一致所以它是验证确定化的天然参照。把这几个函数拼起来用a(b|c)*跑一遍应该能得到 4 个 DFA 状态其中一个终态最小化后是 2 个状态。如果你确定化后不是 4 个先回去检查insert_concat是否把连接符补对。4. Hopcroft 划分做 DFA 最小化补死状态、分裂直到稳定4.1 合并等价状态的依据未来转移行为一致最小化的目标是合并“未来行为完全一致”的状态。两个状态如果都是接受态或者都是非接受态对每个字符跳过去的目标状态也都落在同一个等价类那它们在语言上不可区分可以合并。实现上不直接找等价对而是从“接受态 / 非接受态”这个粗划分开始不断用字符转移把分区细化直到所有分区都不需要再分裂。这个算法学术界叫 Moore 划分细化工程上也常被泛称为 Hopcroft 风格划分。区别只在细化策略和复杂度Hopcroft 用 worklist 只处理被改动的分区这里用“扫到没有变化为止”的版本代码更短状态规模几百以内性能完全够用更适合课程项目。4.2 补全死状态最小化前必须做的一步确定化时我跳过了空目标集合这意味着很多状态对某些字符没有转移行为是“直接拒绝”。最小化算法里失去出边的状态如果把“没有转移”当成一个特殊 bucket容易把两个行为不同的状态误分到一组。常见做法是先补一个显式死状态把所有缺失的转移都指向它再进入划分阶段。def complete_dfa(dfa, states, alphabet): sink -1 # 显式死状态编号与正常状态不冲突 cdfa dict(dfa) for s in states: for ch in alphabet: if (s, ch) not in cdfa: cdfa[(s, ch)] sink for ch in alphabet: cdfa[(sink, ch)] sink return cdfa, states | {sink}补全后所有状态对每个字符都有去路最小化划分只依赖“落到哪个分区”不再依赖“有没有转移”。输出状态数会多一个死状态这是显式表示的代价。严格定义里 DFA 自动机允许缺失转移视为拒绝但显式死状态能让最小化算法更干净代价是状态数比手工画的通常多 1后面第五部分会专门讲这个坑。4.3 划分实现partition 不断细化直到稳定划分的核心思路对每个分区、每个字符看分区内各状态转移目标落在哪个旧分区按目标旧分区把当前分区拆成若干组。只要任何一组被拆开就继续下一轮直到所有分区不再变化。def partition_minimize(dfa, states, finals, alphabet): partitions [set(states) - finals, set(finals)] partitions [p for p in partitions if p] # 去掉空集 changed True while changed: changed False new_partitions [] for part in partitions: groups [set(part)] for ch in alphabet: next_groups [] for group in groups: bucket {} for s in group: target dfa.get((s, ch)) idx None if target is not None: for pi, p in enumerate(partitions): if target in p: idx pi break bucket.setdefault(idx, set()).add(s) next_groups.extend(bucket.values()) groups next_groups if len(groups) 1: changed True new_partitions.extend(groups) partitions new_partitions return [frozenset(p) for p in partitions]这里有两个参数值得解释。alphabet是循环维度字符越多每轮分裂的检查次数越多所以确定化时不要混入无关字符。partitions在每轮开始时保持不变即使本轮已经分裂出一个新分区判断目标时仍按旧分区表算下一轮再按新分区表调整。这样实现简单代价是可能需要多扫几轮。4.4 重新编号并输出转移表从一个分区取代表划分完成后每个分区对应一个最小化状态。重新编号就是把原 DFA 状态映射到分区编号再把转移表整体改写。def renumber(dfa, partitions, start, finals): state_map {} for new_id, part in enumerate(partitions): for s in part: state_map[s] new_id new_dfa {} for (s, ch), t in dfa.items(): new_dfa[(state_map[s], ch)] state_map[t] new_start state_map[start] new_finals {state_map[s] for s in finals} return new_dfa, new_start, new_finalsstate_map相当于一个稠密重编码表原状态编号 0、5、7 可能都映射到新状态 0。转移表改写后同一分区的状态从映射上看只有一条代表转移不会产生冲突因为在划分算法里它们对每个字符都落在同一目标分区。输出时建议再打印一下len(partitions)和len([x for x in partitions if x finals])前者是总状态数后者是终态数一眼能看出最小化效果。5. 最容易翻车的 4 个坑现象、原因、解法5.1 ε-闭包漏掉了起点自身a*不认空串现象a*生成的正则式用nfa_accepts测试空串返回 False但理论上应该接受。进一步看epsilon_closure返回的初始集合里没有起始状态。原因闭包函数写成result set()而不是result set(states)。ε 闭包定义是“从这些状态出发经零条或多条 ε 边可达的状态”零条 ε 边意味着自己必须包含在内。漏掉起点会连锁影响所有确定化状态不只是空串问题。解决初始化改成result set(states)并且把epsilon_closure设计成“自己先入栈再扩展”这样即使状态自身没有任何 ε 出边也不会丢。这个坑最容易在写完代码兴奋测试别的样例时被忽略所以我把自检清单里第一项就设为空串。5.2 连接符补错位置解析结果南辕北辙现象a*b解析成后缀式后变成a*b甚至抛异常生成的 NFA 完全无法匹配aaab。原因insert_concat的补位规则没有覆盖*后面的字符。*是单目运算符但它应用完之后后面的字符与整个闭包片段是“连接”关系必须补.。同样)后面紧跟字母时也必须补因为括号表达式是一个完整操作数。解决把边界写全。prev是(或|时不补ch是|、)、*时不补其余相邻操作数全部补.。我一般在写完这个函数后会直接打印insert_concat((a|b)*c)的结果肉眼确认是(a|b)*.c而不是(a|b)*c。这种错用单元测试最划算两个断言就能锁住。5.3 全局状态没重置多次转换串台现象循环里跑 10 个正则式前 3 个正常第 4 个开始新生成的 NFA 状态编号从几百开始而且每次运行结果都不一样。原因new_state依赖全局变量next_id在测试脚本多次调用时没有重置状态编号一路涨上去。编号大本身不影响正确性但某些同学会把状态编号二维数组当矩阵用比如transitions [[-1]*n for _ in range(n)]编号不连续就直接越界。解决在每个用例开始前执行next_id 0。更稳妥的做法是写一个new_automaton_context()包装函数把编号计数、NFA 构造、确定化、最小化整个流程包在一个函数里顶层测试代码只调用这个函数。这样既避免了全局污染也方便并发跑用例。5.4 最小化后状态数反而变多死状态参与了分区现象a这个单字符正则式手工最小化应该是 2 个状态起始非接受态读a到接受态然后接受态无出边。但补全死状态并最小化后输出是 3 个状态多了一个死状态。原因complete_dfa把死状态显式加入状态集划分算法会把死状态单独分成一个非终态分区。这不是算法错而是“显式死状态”这个实现选择的结果。有些教材的 DFA 允许转移缺失不画死状态所以教科书答案总是少一个状态。解决输出状态数时明确分开统计总状态数和去死状态后的有效状态数。如果你希望交付物和教科书一致可以在重编号后删掉死状态分区找出所有既不是终态、又只转移到自己的分区然后从转移表里去掉对应条目。这样得到的 DFA 在“缺失转移即拒绝”的语义下与最小化结果完全等价。但要记住删掉死状态的 DFA 在交给别的工具进一步处理前必须先补回缺失转移。6. 随机对拍十分钟验证最小化前后不丢语言写几个手写样例永远不够我提交前跑的是随机对拍。先生成随机正则式再走完整条流水线然后枚举长度不超过 4 的字符串对比 NFA 语义解释器和最小化 DFA 的接受结果。这一步能一次性抓住「划分合并过头」「闭包漏状态」「连接符边界错」三类问题。import random from itertools import product def gen_regex(depth2): if depth 0 or random.random() 0.4: return random.choice(abc01) op random.choice([|, , *]) if op |: return ( gen_regex(depth - 1) | gen_regex(depth - 1) ) if op *: return ( gen_regex(depth - 1) )* return gen_regex(depth - 1) gen_regex(depth - 1) def all_strings(alphabet, max_len4): for length in range(max_len 1): for chars in product(sorted(alphabet), repeatlength): yield .join(chars) for _ in range(200): next_id 0 regex gen_regex(2) postfix to_postfix(regex) alphabet get_alphabet(postfix) nfa postfix_to_nfa(postfix) dfa, start, finals, states subset_construct(nfa, alphabet) cdfa, cstates complete_dfa(dfa, states, alphabet) partitions partition_minimize(cdfa, cstates, finals, alphabet) mdfa, mstart, mfinals renumber(cdfa, partitions, start, finals) for s in all_strings(alphabet, 4): if nfa_accepts(nfa, s) ! dfa_accepts(mdfa, mstart, mfinals, s): print(不匹配:, regex, 字符串:, repr(s)) break else: continue break这里深度设成 2生成的表达式已经能覆盖|、连接、*的三层组合。all_strings枚举空串到长度 4 的字符串空串必须测a*这类表达式的空串接受是最容易错的地方。200 个正则式每个枚举最多 341 个字符串跑完通常几秒到十几秒。我现在提交这类课设前都会先跑一遍这段对拍再把确定性 DFA 的转移表打印出来人工扫一眼。最怕的不是算法不熟而是自己在某个小函数里埋了一个“看起来没问题”的边界错误却不知道。对拍能把这些黑匣子问题全部晒出来。希望这套流程能帮你少踩几个坑尤其是那个epsilon_closure的起点问题。本文还有配套的精品资源点击获取 编译原理实战：用Python实现正则式转NFA与DFA最小化
简介基于Python实现正则式转NFA、NFA确定化、DFA最小化的编译原理课程设计资料包面向正在学习形式语言与自动机理论的学生也适合需要动手实践的开发者可用于课程作业、实验报告或相关毕设参考。代码与文档完整覆盖三个核心环节从正则表达式的语法结构构建对应的NFA再利用幂集构造法消除不确定转移得到DFA最后通过状态等价类合并完成DFA最小化实现脉络清晰。压缩包共9个文件以3个Python脚本分别对应上述三个模块辅以3张图片文件、2份Markdown说明和1份许可证文件整体仅243KB便于快速下载与对照阅读。已有355人浏览学习。通过源码对照报告与图示读者可掌握自动机数据结构的类设计、状态转移表的存储方式、每一步转换的输入输出关系还能了解NFA中同一输入存在多条转移路径时的处理思路借此巩固编译原理知识为文本匹配、词法分析等应用打下基础。1. 这门课设看着简单却总在确定化这一步翻车正则式转 NFA、NFA 确定化、DFA 最小化这串名词第一次出现通常是在编译原理的课程项目里。我见过不少同学把正则式转 NFA 当成“按字符画状态图”结果一跑测试就翻车a(b|c)*这种分支加循环的表达式手工画都会漏掉一条回边更别说让程序稳定生成。这个题目的本质是把字符串匹配问题变成图上的可达性问题输入一串正则式输出一张行为完全等价、状态数尽可能少的确定性转移表。它直接服务于词法分析器的骨架也常出现在考研复试和手写正则引擎的面试里。适合正在做编译原理课设的学生以及想用 Python 把《编译原理》第三章真正跑通一遍的从业者。下面我从解析、构造、确定化、最小化到验证按一条可复现的路径展开。2. 先把正则式读进来中缀转后缀与 Thompson 片段构造2.1 为什么我用后缀式而不是 AST教材做法是先建 AST 再递归遍历因为人看表达式是从最外层结构看。但课程项目代码里我更喜欢先把中缀正则式改成后缀式逆波兰式原因只有一个Python 里中缀转后缀只要十几行而直接建 AST 的递归下降要处理括号深度、运算符优先级写起来容易在|和连接符的优先级上翻车。后缀表达式ab*表示a与b*连接运算符跟在操作数后面。求值时只需要一个栈完全不用管括号嵌套。所以我的第一步是先补连接符再转后缀。补连接符是个容易漏的细节正则式ab里两个字符相邻中间隐含一个“连接”运算但肉眼看不出来。我一般用这样一个函数显式插入.。PREC {|: 1, .: 2, *: 3} def insert_concat(regex: str) - str: out [] prev for ch in regex: # 前一个字符不是 ( 或 |当前字符不是 | ) *说明两个操作数相邻 if prev and prev not in (| and ch not in |)*: out.append(.) # 插入连接运算符 out.append(ch) prev ch return .join(out) def to_postfix(regex: str) - str: regex insert_concat(regex) output, stack [], [] for ch in regex: if ch.isalnum(): output.append(ch) elif ch (: stack.append(ch) elif ch ): while stack and stack[-1] ! (: output.append(stack.pop()) stack.pop() # 丢掉左括号 else: if ch not in PREC: raise ValueError(f不支持的运算符: {ch}) while stack and stack[-1] ! ( and PREC[stack[-1]] PREC[ch]: output.append(stack.pop()) stack.append(ch) while stack: output.append(stack.pop()) return .join(output)代码逻辑分三块字符直接输出括号负责改变优先级运算符弹出栈顶优先级不低于自己的元素。insert_concat的规则要记牢prev是(或|时不补因为左边是运算符ch是|、)、*时不补因为右边是运算符。这个规则不处理?、、\d这类扩展语法本文只聚焦在字母数字 | * ( )这个子集上。2.2 从后缀式到 NFA 片段状态怎么编号、边怎么存接下来是 Thompson 构造法。我习惯把 NFA 设计成三个部分起始状态、接受状态、转移关系。这里的关键取舍是状态用一个全局递增整数转移用字典存“某个状态在某个字符下能到达的状态集合”。next_id 0 def new_state() - int: global next_id next_id 1 return next_id - 1 class NFA: def __init__(self, startNone, acceptNone): self.start start if start is not None else new_state() self.accept accept if accept is not None else new_state() self.transitions {} # (from_state, char) - set(to_state) self.epsilon {} # from_state - set(to_state) def add_char(self, ch, frm, to): self.transitions.setdefault((frm, ch), set()).add(to) def add_eps(self, frm, to): self.epsilon.setdefault(frm, set()).add(to)transitions和epsilon分开存是因为确定化时运算不同字符转移直接取ε 转移要递归闭包。状态编号从 0 开始递增保证每个状态在调试输出时是干净的数字。2.3 三种拼接连接、分支、闭包的实现后缀式求值时栈里始终是“已经构造好的 NFA 片段”。遇到字符就构造单字符片段遇到.、|、*就从栈里弹出一到两个片段拼成一个新片段。def postfix_to_nfa(postfix: str) - NFA: stack [] for ch in postfix: if ch.isalnum(): nfa NFA() nfa.add_char(ch, nfa.start, nfa.accept) stack.append(nfa) elif ch *: inner stack.pop() nfa NFA() # 新起一个片段包住 inner nfa.add_eps(nfa.start, inner.start) nfa.add_eps(nfa.start, nfa.accept) nfa.add_eps(inner.accept, inner.start) nfa.add_eps(inner.accept, nfa.accept) nfa.transitions.update(inner.transitions) nfa.epsilon.update(inner.epsilon) stack.append(nfa) elif ch |: right, left stack.pop(), stack.pop() nfa NFA() nfa.add_eps(nfa.start, left.start) nfa.add_eps(nfa.start, right.start) nfa.add_eps(left.accept, nfa.accept) nfa.add_eps(right.accept, nfa.accept) nfa.transitions.update(left.transitions) nfa.transitions.update(right.transitions) nfa.epsilon.update(left.epsilon) nfa.epsilon.update(right.epsilon) stack.append(nfa) elif ch .: right, left stack.pop(), stack.pop() nfa NFA(startleft.start, acceptright.accept) nfa.add_eps(left.accept, right.start) nfa.transitions.update(left.transitions) nfa.transitions.update(right.transitions) nfa.epsilon.update(left.epsilon) nfa.epsilon.update(right.epsilon) stack.append(nfa) return stack.pop()连接操作里NFA(startleft.start, acceptright.accept)不需要新分配状态直接把左片段起始状态和右片段接受状态当作新片段的接口。闭包操作必须新建两个状态作为新片段的起止因为要引入四条 ε 边绕过内部、进入内部、从内部回归内部、从内部跳出。这四边缺一条a*的空串接受或循环接受就会少一半。2.4 字母表从哪里来确定化需要知道所有输入字符。最简单的方法是从后缀式里直接筛出可打印字符* . | ( )都不算字母。def get_alphabet(postfix: str) - set: return {ch for ch in postfix if ch.isalnum()}这一步在真正实现时要放在to_postfix之后因为后缀式里的字符就是最终 NFA 会用到的字符。常见坑是有人把中缀式里的括号也算进字符集导致确定化时多跑很多不存在的输入。另外注意这里不支持\d、[a-z]。如果评审要求支持常见做法是先做一层预处理把字符类展开成(0|1|2|...|9)这种「或」结构再进入这套流程我只在边界上说明不展开实现。3. 子集构造法确定化 NFA两个函数、一个队列、一张转移表3.1 ε-闭包与 move确定化依赖的两个基础操作NFA 和 DFA 的本质区别是NFA 在一个状态下读入一个字符可能跳到多个状态也可能不读字符就自己跳ε 转移。确定化要做的是把“当前可能在的所有状态”打包成一个 DFA 状态。这里两个函数是全部基础epsilon_closure算一个状态集合经 ε 边能到达的全体状态move算一个状态集合读入某个字符后直接能到达的全体状态。def epsilon_closure(nfa: NFA, states) - set: result set(states) # 自己必须包含在内不能从空集开始 stack list(states) while stack: s stack.pop() for t in nfa.epsilon.get(s, ()): if t not in result: result.add(t) stack.append(t) return result def move(nfa: NFA, states, ch: str) - set: result set() for s in states: for t in nfa.transitions.get((s, ch), ()): result.add(t) return resultepsilon_closure初始化直接用set(states)这是防止漏掉状态自身的关键。很多人写成result set()导致a*的空串路径第一次闭包就没把自己算进去后面全错。move只走字符边不走 ε 边返回的集合还没闭包需要在下一轮闭包时补上。3.2 子集构造法实现队列 seen 集合跑完所有状态确定化的经典算法是从初始闭包出发不断用每个字符算出新状态集合如果这个集合没出现过就入队。最终每个去重后的状态集合就是一个 DFA 状态。def subset_construct(nfa: NFA, alphabet: set): start frozenset(epsilon_closure(nfa, {nfa.start})) dfa {} finals set() states {start} queue [start] while queue: cur queue.pop(0) if nfa.accept in cur: finals.add(cur) for ch in alphabet: target frozenset(epsilon_closure(nfa, move(nfa, cur, ch))) if target: dfa[(cur, ch)] target if target not in states: states.add(target) queue.append(target) return dfa, start, finals, statesfinals是 DFA 接受状态集合判定条件是“这个状态集合里包含原 NFA 的接受状态”。判断顺序放在循环开头而不是转移内部是为了连空串这种“一开始就在终态集合里”的情况也能被标记。这里我用queue.pop(0)是图省事如果状态规模变大换成collections.deque的popleft()会更稳。3.3 用 frozenset 当 DFA 状态名不变量与坑DFA 状态是 NFA 状态集合Python 的set不能做 dict 的 key因为它是可变的。我统一用frozenset这样状态集合既能做 dict key也能放进states集合做去重。这个选择贯穿确定化和最小化全流程后面finals里的元素也全是frozenset。有个隐藏约束dfa的 key 是(frozenset, ch)打印时会很啰嗦这是正常的。调试验证时可以用编号重映射但在确定化阶段保持 frozenset 可以随时回溯“这个 DFA 状态对应哪些 NFA 状态”对排查问题极有价值。3.4 怎么求 NFA 等价的 DFA对拍自检方法确定化完后先别急着最小化我一般会立刻做一轮小型对拍随便写一个nfa_accepts和一个dfa_accepts枚举长度不超过 4 的字符串在两台“机器”上分别跑。这样可以先证明确定化这一步没有把语言搞丢再做最小化后面排错范围会小很多。def nfa_accepts(nfa: NFA, s: str) - bool: current epsilon_closure(nfa, {nfa.start}) for ch in s: current epsilon_closure(nfa, move(nfa, current, ch)) return nfa.accept in current def dfa_accepts(dfa, start, finals, s: str) - bool: cur start for ch in s: if (cur, ch) not in dfa: return False cur dfa[(cur, ch)] return cur in finalsnfa_accepts每一步都是“先 move 再关包”和确定化里的逻辑完全一致所以它是验证确定化的天然参照。把这几个函数拼起来用a(b|c)*跑一遍应该能得到 4 个 DFA 状态其中一个终态最小化后是 2 个状态。如果你确定化后不是 4 个先回去检查insert_concat是否把连接符补对。4. Hopcroft 划分做 DFA 最小化补死状态、分裂直到稳定4.1 合并等价状态的依据未来转移行为一致最小化的目标是合并“未来行为完全一致”的状态。两个状态如果都是接受态或者都是非接受态对每个字符跳过去的目标状态也都落在同一个等价类那它们在语言上不可区分可以合并。实现上不直接找等价对而是从“接受态 / 非接受态”这个粗划分开始不断用字符转移把分区细化直到所有分区都不需要再分裂。这个算法学术界叫 Moore 划分细化工程上也常被泛称为 Hopcroft 风格划分。区别只在细化策略和复杂度Hopcroft 用 worklist 只处理被改动的分区这里用“扫到没有变化为止”的版本代码更短状态规模几百以内性能完全够用更适合课程项目。4.2 补全死状态最小化前必须做的一步确定化时我跳过了空目标集合这意味着很多状态对某些字符没有转移行为是“直接拒绝”。最小化算法里失去出边的状态如果把“没有转移”当成一个特殊 bucket容易把两个行为不同的状态误分到一组。常见做法是先补一个显式死状态把所有缺失的转移都指向它再进入划分阶段。def complete_dfa(dfa, states, alphabet): sink -1 # 显式死状态编号与正常状态不冲突 cdfa dict(dfa) for s in states: for ch in alphabet: if (s, ch) not in cdfa: cdfa[(s, ch)] sink for ch in alphabet: cdfa[(sink, ch)] sink return cdfa, states | {sink}补全后所有状态对每个字符都有去路最小化划分只依赖“落到哪个分区”不再依赖“有没有转移”。输出状态数会多一个死状态这是显式表示的代价。严格定义里 DFA 自动机允许缺失转移视为拒绝但显式死状态能让最小化算法更干净代价是状态数比手工画的通常多 1后面第五部分会专门讲这个坑。4.3 划分实现partition 不断细化直到稳定划分的核心思路对每个分区、每个字符看分区内各状态转移目标落在哪个旧分区按目标旧分区把当前分区拆成若干组。只要任何一组被拆开就继续下一轮直到所有分区不再变化。def partition_minimize(dfa, states, finals, alphabet): partitions [set(states) - finals, set(finals)] partitions [p for p in partitions if p] # 去掉空集 changed True while changed: changed False new_partitions [] for part in partitions: groups [set(part)] for ch in alphabet: next_groups [] for group in groups: bucket {} for s in group: target dfa.get((s, ch)) idx None if target is not None: for pi, p in enumerate(partitions): if target in p: idx pi break bucket.setdefault(idx, set()).add(s) next_groups.extend(bucket.values()) groups next_groups if len(groups) 1: changed True new_partitions.extend(groups) partitions new_partitions return [frozenset(p) for p in partitions]这里有两个参数值得解释。alphabet是循环维度字符越多每轮分裂的检查次数越多所以确定化时不要混入无关字符。partitions在每轮开始时保持不变即使本轮已经分裂出一个新分区判断目标时仍按旧分区表算下一轮再按新分区表调整。这样实现简单代价是可能需要多扫几轮。4.4 重新编号并输出转移表从一个分区取代表划分完成后每个分区对应一个最小化状态。重新编号就是把原 DFA 状态映射到分区编号再把转移表整体改写。def renumber(dfa, partitions, start, finals): state_map {} for new_id, part in enumerate(partitions): for s in part: state_map[s] new_id new_dfa {} for (s, ch), t in dfa.items(): new_dfa[(state_map[s], ch)] state_map[t] new_start state_map[start] new_finals {state_map[s] for s in finals} return new_dfa, new_start, new_finalsstate_map相当于一个稠密重编码表原状态编号 0、5、7 可能都映射到新状态 0。转移表改写后同一分区的状态从映射上看只有一条代表转移不会产生冲突因为在划分算法里它们对每个字符都落在同一目标分区。输出时建议再打印一下len(partitions)和len([x for x in partitions if x finals])前者是总状态数后者是终态数一眼能看出最小化效果。5. 最容易翻车的 4 个坑现象、原因、解法5.1 ε-闭包漏掉了起点自身a*不认空串现象a*生成的正则式用nfa_accepts测试空串返回 False但理论上应该接受。进一步看epsilon_closure返回的初始集合里没有起始状态。原因闭包函数写成result set()而不是result set(states)。ε 闭包定义是“从这些状态出发经零条或多条 ε 边可达的状态”零条 ε 边意味着自己必须包含在内。漏掉起点会连锁影响所有确定化状态不只是空串问题。解决初始化改成result set(states)并且把epsilon_closure设计成“自己先入栈再扩展”这样即使状态自身没有任何 ε 出边也不会丢。这个坑最容易在写完代码兴奋测试别的样例时被忽略所以我把自检清单里第一项就设为空串。5.2 连接符补错位置解析结果南辕北辙现象a*b解析成后缀式后变成a*b甚至抛异常生成的 NFA 完全无法匹配aaab。原因insert_concat的补位规则没有覆盖*后面的字符。*是单目运算符但它应用完之后后面的字符与整个闭包片段是“连接”关系必须补.。同样)后面紧跟字母时也必须补因为括号表达式是一个完整操作数。解决把边界写全。prev是(或|时不补ch是|、)、*时不补其余相邻操作数全部补.。我一般在写完这个函数后会直接打印insert_concat((a|b)*c)的结果肉眼确认是(a|b)*.c而不是(a|b)*c。这种错用单元测试最划算两个断言就能锁住。5.3 全局状态没重置多次转换串台现象循环里跑 10 个正则式前 3 个正常第 4 个开始新生成的 NFA 状态编号从几百开始而且每次运行结果都不一样。原因new_state依赖全局变量next_id在测试脚本多次调用时没有重置状态编号一路涨上去。编号大本身不影响正确性但某些同学会把状态编号二维数组当矩阵用比如transitions [[-1]*n for _ in range(n)]编号不连续就直接越界。解决在每个用例开始前执行next_id 0。更稳妥的做法是写一个new_automaton_context()包装函数把编号计数、NFA 构造、确定化、最小化整个流程包在一个函数里顶层测试代码只调用这个函数。这样既避免了全局污染也方便并发跑用例。5.4 最小化后状态数反而变多死状态参与了分区现象a这个单字符正则式手工最小化应该是 2 个状态起始非接受态读a到接受态然后接受态无出边。但补全死状态并最小化后输出是 3 个状态多了一个死状态。原因complete_dfa把死状态显式加入状态集划分算法会把死状态单独分成一个非终态分区。这不是算法错而是“显式死状态”这个实现选择的结果。有些教材的 DFA 允许转移缺失不画死状态所以教科书答案总是少一个状态。解决输出状态数时明确分开统计总状态数和去死状态后的有效状态数。如果你希望交付物和教科书一致可以在重编号后删掉死状态分区找出所有既不是终态、又只转移到自己的分区然后从转移表里去掉对应条目。这样得到的 DFA 在“缺失转移即拒绝”的语义下与最小化结果完全等价。但要记住删掉死状态的 DFA 在交给别的工具进一步处理前必须先补回缺失转移。6. 随机对拍十分钟验证最小化前后不丢语言写几个手写样例永远不够我提交前跑的是随机对拍。先生成随机正则式再走完整条流水线然后枚举长度不超过 4 的字符串对比 NFA 语义解释器和最小化 DFA 的接受结果。这一步能一次性抓住「划分合并过头」「闭包漏状态」「连接符边界错」三类问题。import random from itertools import product def gen_regex(depth2): if depth 0 or random.random() 0.4: return random.choice(abc01) op random.choice([|, , *]) if op |: return ( gen_regex(depth - 1) | gen_regex(depth - 1) ) if op *: return ( gen_regex(depth - 1) )* return gen_regex(depth - 1) gen_regex(depth - 1) def all_strings(alphabet, max_len4): for length in range(max_len 1): for chars in product(sorted(alphabet), repeatlength): yield .join(chars) for _ in range(200): next_id 0 regex gen_regex(2) postfix to_postfix(regex) alphabet get_alphabet(postfix) nfa postfix_to_nfa(postfix) dfa, start, finals, states subset_construct(nfa, alphabet) cdfa, cstates complete_dfa(dfa, states, alphabet) partitions partition_minimize(cdfa, cstates, finals, alphabet) mdfa, mstart, mfinals renumber(cdfa, partitions, start, finals) for s in all_strings(alphabet, 4): if nfa_accepts(nfa, s) ! dfa_accepts(mdfa, mstart, mfinals, s): print(不匹配:, regex, 字符串:, repr(s)) break else: continue break这里深度设成 2生成的表达式已经能覆盖|、连接、*的三层组合。all_strings枚举空串到长度 4 的字符串空串必须测a*这类表达式的空串接受是最容易错的地方。200 个正则式每个枚举最多 341 个字符串跑完通常几秒到十几秒。我现在提交这类课设前都会先跑一遍这段对拍再把确定性 DFA 的转移表打印出来人工扫一眼。最怕的不是算法不熟而是自己在某个小函数里埋了一个“看起来没问题”的边界错误却不知道。对拍能把这些黑匣子问题全部晒出来。希望这套流程能帮你少踩几个坑尤其是那个epsilon_closure的起点问题。本文还有配套的精品资源点击获取