正则表达式到自动机：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. 正则式转 NFA：Thompson 构造法与状态图数据结构

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之前把转义后的字符替换成不冲突的占位符。

下表归纳了三种基本构造的图形含义：

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当作key，frozenset则可以。闭包计算时只查(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边上（虽然实际很少见），保持一致才不会丢转移。

下表把子集构造的过程拆成五步，方便对照代码调试：

3.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 能从元组里正确取出来就行。遍历所有边找src==s的方式在大状态集上偏慢，但几万个状态内都能接受，而且只跑一次，不值得为此把结构改成邻接表。

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之前遍历全部状态和字符，把没有边的位置指向新状态。

下面把三类常用最小化算法放在一起对比：

上面代码属于划分细化，结果与Hopcroft相同，只是常数大一些。课程设计的DFA状态数一般不超过百个，直接跑划分细化足够。如果后续要处理上千状态的词法器，再考虑用队列版的Hopcroft。

4.3 为什么会停在不动点

有些同学在第一次迭代后看到块数没变，就以为算法结束，其实可能只是这轮没拆，下一轮还会拆。例如状态A和B都落在接受块，读入'a'后也都到接受块，但再读入'b'时一个到接受、一个到拒绝，这只有在第二轮签名里才会暴露。所以必须循环到块数完全不增长，才能保证稳定。调试时可以在每次循环结束打印每个块里包含的状态编号，对照“两个状态是否能区分”的手写推导，很快就能发现问题。

5. 作业检查和实际技巧：Graphviz 可视化与死状态补全

5.1 用 DOT 导出状态图

手写转移表只能看到数字，不如把最小化前后的DFA各自导出一张图。Graphviz的DOT格式很简单：

def dfa_to_dot(dfa, path='dfa.dot'): lines = ['digraph DFA {', ' rankdir=LR;'] 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', encoding='utf-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，最后划分。

本文还有配套的精品资源，点击获取