简介：面向编译原理课程设计的完整Python实现工程，围绕正则表达式转NFA、NFA确定化及DFA最小化三大核心环节，覆盖状态转移、子集构造、等价类划分等关键算法，以编译原理第一次作业的形式组织代码、文档与演示截图，整体按构建NFA、执行确定化、完成最小化三个模块拆分，适合计算机专业学生作为课程设计参考、实验报告范本或自动机理论复习材料。压缩包共9个文件，含3个py算法源码、3张运行结果截图、2份Markdown说明文档和1个LICENSE，整包仅243KB，便于下载对照。目前已有355人学习，内容包含从正则式解析、幂集构造法确定化到Hopcroft等价类合并最小化的完整流程；代码结构清晰并配有说明文档，可帮助逐步对应算法原理、验证中间结果，适合用于作业验收、考前梳理或课程报告撰写，对希望通过实际编程加深编译原理与有限自动机理解的学习者相当实用。

1. 从正则式到最小化 DFA：这个题目到底在考什么

“基于Python实现正则式转NFA、NFA确定化、DFA最小化”，题目末尾那个【100012432】一般是题库入库编号，不影响技术内容。真正值得拆的是这条流水线：正则表达式先通过 Thompson 构造法变成带 ε 边的 NFA，再用子集构造法把它确定化为 DFA，最后用划分法把等价状态合并成最简 DFA。走完这三步，你就拥有一颗不依赖 re 模块的轻量正则引擎核心。适合谁？写编译原理课程设计的本科生、面试前想徒手推导自动机的工程师、要在自动化工具里内置匹配逻辑的开发者。环境只需要 Python 3.8+ 纯标准库，不需要第三方依赖。我当年踩得最狠的不是算法本身，而是解析器的优先级、ε-closure 的收敛写法、以及最小化前的不可达状态清理，这些都会在后面逐节展开。

2. 正则式转 NFA：Thompson 构造法与解析器的三个细节

2.1 插入显式连接符：把“ab”变成“a.b”的小函数

初学最容易忽略的是正则式里的“隐式连接”。ab表示 a 与 b 连接，但解析器读字符时并没有一个明确的连接运算符。常见做法是先做一次字符串预处理，把所有需要连接的位置插入一个显式的.符号，后续中缀转后缀就好处理了。

def insert_explicit_concat(expr: str) -> str: """把隐式连接改成显式 . 连接，方便转后缀表达式。""" res = [] for i, ch in enumerate(expr): res.append(ch) if i + 1 >= len(expr): break nxt = expr[i + 1] # 当前字符能结束一个子表达式，且下一个字符能开始一个新子表达式 if (ch in ')*+?]' or ch.isalnum()) and (nxt in '(*?+[' or nxt.isalnum()): res.append('.') return ''.join(res)

逻辑说明：ch.isalnum()覆盖普通字母数字，)*+?]表示一个子表达式刚刚结束，后面的(*?+[或字母数字表示下一个表达式开始，这两类字符相邻就说明中间缺了一个连接符。参数上我默认输入已经去掉了空白符；如果你要支持\d这类转义，得先做一层词法扫描把\d替换成单个内部符号（比如D），否则\和d之间会被错误地插入.。

2.2 中缀转后缀：Shunting-yard 算法的 20 行实现

正则式里的运算符优先级和普通四则运算很像：|优先级最低，连接次之，*、+、?最高。用调度场算法（Shunting-yard）转后缀时，把*这类后缀运算符当作一元运算符压栈，遇到更低或同优先级运算符时再弹出，就能保持正确的结合顺序。

def to_postfix(expr_with_dots: str) -> list: """中缀带点表达式转后缀 token 列表。""" precedence = {'|': 1, '.': 2, '*': 3, '+': 3, '?': 3} output = [] stack = [] for ch in expr_with_dots: if ch.isalnum(): output.append(ch) elif ch == '(': stack.append(ch) elif ch == ')': while stack and stack[-1] != '(': output.append(stack.pop()) if stack: stack.pop() else: # 操作符 while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence.get(ch, 0): output.append(stack.pop()) stack.append(ch) while stack: output.append(stack.pop()) return output

逻辑说明：遇到右括号时一直弹出到左括号为止，但左括号本身不输出。操作符入栈前，把所有栈顶优先级不低于当前操作符的符号弹出，因为|、.都是左结合，同优先级也要先弹旧的。参数上，precedence这个字典是核心，如果你以后要扩展新的运算符，第一件事是给它排优先级。举个例子，表达式1(0|1)*101插入显式连接符后变成1.(0|1)*.1.0.1，转后缀的结果是['1', '0', '1', '|', '*', '.', '1', '.', '0', '.', '1', '.']，这个序列在后面构造 NFA 时可以直接进栈。

2.3 Thompson 构造法：用 NFA 类把状态当作整数

Thompson 构造法的规则很固定：单字符是两状态一条边；连接是用 ε 边把前者的终态接到后者的初态；并集是新增初态和终态，用两条 ε 边接入两个子图；闭包是新增一条 ε 环。我建议不要把状态做成对象，直接用整数编号，后面做子集构造时要用frozenset当字典键，整数编号最省心。

class NFA: def __init__(self, n_states, start, accept, transitions): self.n_states = n_states # 状态总数，编号为 0..n_states-1 self.start = start # 唯一初态 self.accept = accept # 唯一终态（Thompson 构造保证唯一） self.transitions = transitions # list[dict[str, set[int]]] def symbol_nfa(ch: str) -> NFA: """单字符 NFA：状态 0 --ch--> 状态 1。""" trans = [dict(), dict()] trans[0][ch] = {1} return NFA(2, 0, 1, trans) def concat_nfa(a: NFA, b: NFA) -> NFA: """连接 a b：把 a 的终态与 b 的初态用 ε 边串起来。""" offset = a.n_states trans = [dict(row) for row in a.transitions] + [dict() for _ in range(b.n_states)] for s in range(b.n_states): for sym, targets in b.transitions[s].items(): trans[offset + s][sym] = {t + offset for t in targets} a_acc = a.accept b_start = offset + b.start trans[a_acc].setdefault('', set()).add(b_start) return NFA(offset + b.n_states, a.start, offset + b.accept, trans) def union_nfa(a: NFA, b: NFA) -> NFA: """并 a|b：新增初态和终态，分别用 ε 边接入 a、b。""" offset = a.n_states total = a.n_states + b.n_states + 2 new_start, new_accept = total - 2, total - 1 trans = [dict(row) for row in a.transitions] + [dict() for _ in range(b.n_states + 2)] for s in range(b.n_states): for sym, targets in b.transitions[s].items(): trans[offset + s][sym] = {t + offset for t in targets} trans[new_start][''] = {a.start, offset + b.start} trans[a.accept][''] = {new_accept} trans[offset + b.accept][''] = {new_accept} return NFA(total, new_start, new_accept, trans) def star_nfa(a: NFA) -> NFA: """闭包 a*：新增初态/终态，a 的终态能回 a 的初态。""" total = a.n_states + 2 new_start, new_accept = total - 2, total - 1 trans = [dict(row) for row in a.transitions] + [dict() for _ in range(2)] trans[new_start][''] = {a.start, new_accept} trans[a.accept][''] = {a.start, new_accept} return NFA(total, new_start, new_accept, trans) def plus_nfa(a: NFA) -> NFA: """正闭包 a+：a 的终态能回 a 的初态，也能到新终态。""" total = a.n_states + 1 new_accept = total - 1 trans = [dict(row) for row in a.transitions] + [dict()] trans[a.accept][''] = {a.start, new_accept} return NFA(total, a.start, new_accept, trans) def option_nfa(a: NFA) -> NFA: """可选 a?：新增初态/终态，直接走 ε 边跳过 a。""" total = a.n_states + 2 new_start, new_accept = total - 2, total - 1 trans = [dict(row) for row in a.transitions] + [dict() for _ in range(2)] trans[new_start][''] = {a.start, new_accept} trans[a.accept][''] = {new_accept} return NFA(total, new_start, new_accept, trans) def build_nfa(postfix: list) -> NFA: """从左到右扫后缀式，用栈组合 NFA。""" stack = [] for tok in postfix: if tok not in '|.*+?': stack.append(symbol_nfa(tok)) elif tok == '.': b, a = stack.pop(), stack.pop() stack.append(concat_nfa(a, b)) elif tok == '|': b, a = stack.pop(), stack.pop() stack.append(union_nfa(a, b)) elif tok == '*': stack.append(star_nfa(stack.pop())) elif tok == '+': stack.append(plus_nfa(stack.pop())) elif tok == '?': stack.append(option_nfa(stack.pop())) return stack[-1]

逻辑说明：concat_nfa和union_nfa都做了浅拷贝[dict(row) for row in a.transitions]，避免组合时修改原 NFA 的转移表——这是一个很容易忽略的副作用坑，如果你直接在原列表上操作，构造第二个子图时会把第一个的 ε 边污染掉。参数上，offset是状态编号偏移量，组合时把 b 的全部状态加了一个偏移量，这样两个子图的状态编号不会冲突。setdefault('', set())是每次加 ε 边的标准写法，因为一个状态可以同时有多条 ε 出边。

用1(0|1)*101跑一遍，生成的后缀式是前面贴过的那个序列，构造出的 NFA 大约 16 个状态，初态、终态唯一，转移表里能看到大量 ε 边。画成图之后你会直观感受到：NFA 的状态数几乎等于正则式的操作数规模，这也是后边确定化要有子集构造法的原因。

3. NFA 确定化：子集构造法与 ε-closure 的边界

3.1 ε-closure 要写收敛：自我包含和迭代缺一不可

确定化第一步是 ε-closure：从某个 NFA 状态集合出发，沿着 ε 边能到达的所有状态集合。有两个细节最容易翻车：一是初始状态集合本身必须包含在内（空串不需要任何移动也能留在原状态）；二是要一直扩张到没有新状态加入为止，不能只算一层。

def epsilon_closure(nfa: NFA, states: set) -> set: """从 states 出发，沿 ε 边能到达的全部状态集合。""" stack = list(states) closure = set(states) while stack: s = stack.pop() for nxt in nfa.transitions[s].get('', set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return closure

逻辑说明：closure = set(states)就是“自我包含”，然后配合栈做深度优先扩张，直到栈空。参数上，nfa.transitions[s].get('', set())用空字符串表示 ε 边，取不到就返回空集合，避免写一堆if分支。为什么不用递归？因为如果 NFA 里 ε 边成环，递归写法需要额外维护 visited 集合，而且深链容易栈溢出，栈迭代是这里的常规做法。

3.2 move 与子集构造：frozenset 当 DFA 状态键

子集构造法的标准套路是对每个未处理的 DFA 状态（本身就是 NFA 状态集合），对字母表每个符号算一遍epsilon_closure(move(T, a))，得到新的子集，再为子集分配编号。DFA 的每个状态对应一个 NFA 状态集合，因此 Python 里必须用frozenset当字典键，普通set不可哈希。

def move(nfa: NFA, states: set, symbol: str) -> set: """从 states 出发，沿 symbol 边能一步到达的状态集合（不含 ε 闭包）。""" result = set() for s in states: for targets in nfa.transitions[s].values(): # 这里只匹配当前符号；如果支持通配符 '.'，需要额外判断 pass # 上面的写法不完整，看下面这个版本 return result

上面那段是错误示范，我来写正确的完整版：

def move(nfa: NFA, states: set, symbol: str) -> set: result = set() for s in states: targets = nfa.transitions[s].get(symbol, set()) result |= targets return result def subset_construction(nfa: NFA, alphabet: set) -> "DFA": start_closure = epsilon_closure(nfa, {nfa.start}) unmarked = [start_closure] dfa_states = [frozenset(start_closure)] dfa_trans = [dict()] state_index = {frozenset(start_closure): 0} accepts = set() if nfa.accept in start_closure: accepts.add(0) while unmarked: current = unmarked.pop() cur_idx = state_index[frozenset(current)] for sym in alphabet: next_set = epsilon_closure(nfa, move(nfa, current, sym)) if not next_set: continue ns = frozenset(next_set) if ns not in state_index: state_index[ns] = len(dfa_states) dfa_states.append(ns) dfa_trans.append(dict()) unmarked.append(next_set) if nfa.accept in next_set: accepts.add(state_index[ns]) dfa_trans[cur_idx][sym] = state_index[ns] return DFA(len(dfa_states), 0, accepts, dfa_trans) class DFA: def __init__(self, n_states, start, accepts, transitions): self.n_states = n_states self.start = start self.accepts = accepts self.transitions = transitions # list[dict[str, int]]

逻辑说明：move只做“走一条符号边”这件事，不处理 ε；subset_construction里先epsilon_closure(move(...))才是完整的“经符号边到达的闭包”。state_index承担“子集到编号”的映射，用frozenset保证可哈希。参数上，alphabet是从正则式里收集的字符集合，对1(0|1)*101就是{'0', '1'}；如果正则式支持\d，要在外部把\d展开成'0'...'9'再加入alphabet，否则确定化时永远走不到数字边。

3.3 用 1(0|1)*101 验证确定化：手工子集表与代码对照

很多人在搜“怎么求 nfa 等价的 dfa”，其实核心就是这个子集构造法。跑完上面代码后，可以把 DFA 的转移表打出来，跟手工推的子集对照。我习惯写一个小函数看结果：

def print_dfa(dfa: DFA, alphabet: set): symbols = sorted(alphabet) print(f"start={dfa.start}, accepts={dfa.accepts}") print("state\t" + "\t".join(symbols)) for s in range(dfa.n_states): row = [str(s)] for sym in symbols: row.append(str(dfa.transitions[s].get(sym, '-'))) print("\t".join(row)) dfa = subset_construction(nfa, {'0', '1'}) print_dfa(dfa, {'0', '1'})

对1(0|1)*101，跑出来大概 7 到 8 个状态，具体编号会受 set 迭代顺序影响，但接受语言是唯一的。一个快速的自检验：101应该被接受，1001应该被拒绝，11101应该被接受。拿一个字符串挨个看转移表，你就能确认确定化没写歪。注意这里的 DFA 还没有补死状态，比如输入字符串里出现2，dfa_trans[cur][sym]取不到就直接返回 False，在单次匹配场景没问题，但后面最小化时要统一考虑符号表。

4. DFA 最小化：划分法的反向切分与 Hopcroft 取舍

4.1 前置清理：先删除不可达状态再做划分

最小化的第一个前置步骤是删除不可达状态，很多人上来就划分，结果老是发现输出里有一堆孤立状态。从 DFA 初态出发做 BFS，能走到的才是有效状态，其余全部丢掉。这个步骤不做，后面的划分会把不可达状态当成独立分组，最终生成的 DFA 带着永远到不了的转移，看着就头疼。

def reachable_states(dfa: DFA) -> set: seen = set() stack = [dfa.start] while stack: s = stack.pop() if s in seen: continue seen.add(s) for t in dfa.transitions[s].values(): if t not in seen: stack.append(t) return seen def strip_unreachable(dfa: DFA) -> DFA: live = reachable_states(dfa) mapping = {s: i for i, s in enumerate(sorted(live))} new_trans = [] for s in sorted(live): row = {} for sym, t in dfa.transitions[s].items(): if t in mapping: row[sym] = mapping[t] new_trans.append(row) return DFA(len(live), mapping[dfa.start], {mapping[a] for a in dfa.accepts if a in mapping}, new_trans)

逻辑说明：reachable_states用stack做显式 DFS，避免递归爆栈。strip_unreachable里对live排序后再建映射，目的是让状态编号输出稳定，不随set的哈希顺序漂移。参数上，如果 DFA 本身已经有死状态（比如补了全转移表的死状态），这个死状态是可达的，不会被删掉；但如果没有从初态到它的路径，就会消失。最小化的语义只关心可达状态，所以这一步是安全的。

4.2 划分法实现：从接受/非接受出发按符号切分

划分法（也叫 Moore 法）的核心是维护一个状态分组列表，每组代表一组互等价的候选状态。初始分成接受状态组和非接受状态组两组，然后反复对每个组按“每个符号转移到哪个组”来细分，直到没有组再分裂。实现时最容易错的是符号表不完整，我在这里用全局symbols统一遍历，缺失转移用 -1 兜底。

def minimize_dfa(dfa: DFA) -> DFA: dfa = strip_unreachable(dfa) symbols = sorted({sym for row in dfa.transitions for sym in row}) accept = set(dfa.accepts) non_accept = set(range(dfa.n_states)) - accept partition = [g for g in [accept, non_accept] if g] def group_of(s: int) -> int: for i, g in enumerate(partition): if s in g: return i return -1 while True: new_partition = [] changed = False for group in partition: buckets = {} for s in group: # 核心 key：每个符号的转移目标所属的组编号 key = tuple(group_of(dfa.transitions[s].get(sym, -1)) for sym in symbols) buckets.setdefault(key, set()).add(s) if len(buckets) == 1: new_partition.append(group) else: changed = True new_partition.extend(buckets.values()) partition = new_partition if not changed: break mapping = {s: i for i, g in enumerate(partition) for s in g} new_start = mapping[dfa.start] new_accepts = {i for i, g in enumerate(partition) if any(s in dfa.accepts for s in g)} new_trans = [] for g in partition: rep = next(iter(g)) # 组内状态等价，任取一个代表元 row = {} for sym in symbols: t = dfa.transitions[rep].get(sym, -1) if t != -1: row[sym] = mapping[t] new_trans.append(row) return DFA(len(partition), new_start, new_accepts, new_trans)

逻辑说明：group_of(-1)返回 -1，这相当于把所有“无转移”的状态归成一个隐含的“非法目标组”。这样一来，两个状态如果某个符号一个有转移一个没有转移，它们的 key 会不一样，从而被正确拆分。mapping把每个原状态映射到它所在新组的编号，最后生成转移表时只用组内任意一个代表元，因为划分法保证同组状态在所有符号下行为一致。参数上，symbols是全局符号表，千万不能只取某个状态的transitions.keys()，否则符号集合不齐，两个不同状态会被错误地判定为等价。

跑完1(0|1)*101的 DFA 后，最小化通常能再压缩掉一两个状态。拿压缩前后的 DFA 对同一批字符串测试，结果必须完全一致，这是验证“等价”的最直接手段。

4.3 Hopcroft 算法值不值得换：复杂度与写法对比

划分法最坏时间复杂度是 O(k·n²)，其中 k 是符号表大小，n 是状态数，对课程设计规模完全够用。Hopcroft 算法能到 O(k·n·log n)，但代价是代码里要维护一个待处理的工作队列、每个符号对应一组反向转移表，以及一套“split”的迭代逻辑，实现难度比划分法高一个量级。很多开源正则引擎选择 Hopcroft，是因为它们要处理几十万状态的 DFA，这是性能刚需；如果你的状态数在一千以内，划分法跑起来都是毫秒级。

我的建议是：先写划分法跑通正确性，如果后面真的遇到大规模 DFA 再换 Hopcroft。换算法之前，把“正则式到最小化 DFA”的完整链路搭好，然后用随机字符串对拍保证新旧结果一致，否则根本不敢改。

5. 避坑与排查：5 个让结果“看起来对但其实是错的”的经典问题

5.1 空分支“()”：解析后栈顶多一个空 NFA

现象：输入a()或(()*)这类含空括号的表达式时，程序可能在build_nfa里弹出不存在的元素，或者莫名其妙生成一个只含 ε 边的 NFA。

原因：括号内部没有任何 token，转后缀时没有内容入栈，构造 NFA 时碰到)对应的栈底是空的，最终栈里可能只有一个空子图。

解决：我一般在词法阶段就拦截空括号，直接抛ValueError("empty group")。如果产品里确实需要表示“空串”，不要用()而是显式定义一个符号，比如ε或""，并在symbol_nfa里构造一个直接接受空串的两状态 NFA。这个策略能让你在解析阶段就暴露问题，而不是等到构建 NFA 时栈空。

5.2 ε-closure 写漏一层：确定化结果少状态

现象：DFA 能匹配大部分字符串，但包含空串或需要多次 ε 跳转的用例全部失败，比如a*不接受空串。

原因：常见实现是closure = set(states)后，只对传入状态做一层 ε 边扩展，没有把新加入的状态继续扩展。NFA 里 ε 边可以串联、成环，必须用栈/队列反复处理直到收敛。

解决：把epsilon_closure写成 while 循环版，每加入一个新状态就继续检查它的 ε 出边。自检方法：a*的 DFA 必须接受空串，(a|)*的 DFA 也必须接受空串。如果这两个用例不过，先查 ε-closure 再查子集构造的初态处理。

5.3 frozenset 和状态对象混用：子集构造的哈希坑

现象：TypeError: unhashable type: 'set'，或者同一个子集在dict里出现多次，DFA 状态数膨胀。

原因：子集构造法里 DFA 状态是 NFA 状态集合，如果直接用set当字典键会爆炸；如果自己写了State类但忘了__hash__和__eq__，Python 默认按对象 id 哈希，同一个子集在不同轮次构造出的集合对象不同，永远命中不了缓存。

解决：NFA 状态一律用整数编号，DFA 状态一律用frozenset[int]当键。不要试图把 NFA 对象放进frozenset，对象哈希不可控而且慢。代码里state_index的所有键都写成frozenset(...)，取值时再转回普通set做遍历。

5.4 符号表不完整：最小化阶段死状态合并错位

现象：最小化之后，DFA 对没在正则式里出现过的字符（比如正则式只有0、1，测试字符串里出现2）行为异常；或者手工推最小化的结果和代码输出对不上。

原因：最小化的key只用dfa.transitions[s].keys()遍历，两个状态如果有不同的转移符号集合，key 的长度和顺序都不一样，等价性判断就失真了。另外，缺一个“死状态”会让那些没有转移的符号直接消失，划分时可能把两个本来不同的状态错误合并。

解决：构造 DFA 时定义全局alphabet，最小化阶段遍历全局符号表，缺失转移用 -1 兜底。更稳妥的做法是显式补一个死状态：所有未定义转移都指向死状态，死状态上所有符号都自环且非接受状态。这样转移表是完整的，最小化结果也更规整。代价是多一个状态，但换来的是调试时不会“状态凭空消失”。

5.5 黑匣子判断法：打印转移表比看代码更快

现象：算法写完，单测也过了，但换几个复杂正则式结果就是不对，盯着代码看半天找不到问题。

原因：人的眼睛不适合追踪递归和集合扩张过程，而转移表把状态和符号摊平了，错位的地方一眼就能看出来。我曾经在concat_nfa里把偏移量算错，NFA 图看起来是连通的，但打印 DFA 转移表才发现目标状态编号根本对不上。

解决：写一个print_trans_table(dfa, alphabet)，格式固定为行列对齐的文本表，再手工推导一个简单正则式（比如a(b|c)*）的预期转移表对照。对比表格比对比代码快得多。这个方法在后面对拍调试里也一直用得上。

6. 进阶验证：DOT 可视化、随机字符串对拍与测试习惯

6.1 输出 DOT 图：让 NFA 的 ε 边无处可藏

把 NFA 或 DFA 输出成 Graphviz 的 DOT 文本，不需要装任何 Python 包，生成.dot文件后用网页版 Graphviz 或命令行dot -Tpng渲染即可。我习惯把 ε 边画成虚线，接受状态用双圈，这样图一出来，结构问题比看代码直观得多。

def nfa_to_dot(nfa: NFA, name: str = "nfa") -> str: lines = [f"digraph {name} {{", " rankdir=LR;"] for s in range(nfa.n_states): shape = "doublecircle" if s == nfa.accept else "circle" lines.append(f' {s} [shape={shape}];') for s in range(nfa.n_states): for sym, targets in nfa.transitions[s].items(): label = "ε" if sym == "" else sym for t in targets: lines.append(f' {s} -> {t} [label="{label}"];') lines.append("}") return "\n".join(lines)

逻辑说明：DOT 的输出只依赖状态编号和转移表，不会引入额外依赖。渲染时如果看到某个子图有奇怪的 ε 环或孤立状态，基本就是构造阶段的偏移量或 ε 边写错了。参数上，rankdir=LR让图横向展开，状态多时比纵向更易读。

6.2 随机正则式 + re.fullmatch 对拍：一条命令跑 1000 组用例

最小化做完之后，最有效的验收方法是把结果和 Python 标准库re对拍。用一个生成器随机造正则式，限定语法只包含小写字母、数字、|、*、+、?、括号，这些符号的语义和re模块一致，不会因为\d、.的差异造成误报。然后随机生成字符串，用re.fullmatch和自研 DFA 分别判断，任何不一致都说明中间某一步写错了。

import random import re def gen_regex(rng: random.Random, depth: int = 0) -> str: chars = "01" if depth > 3 or rng.random() < 0.3: return rng.choice(chars) kind = rng.choice(["concat", "union", "star", "plus", "optional"]) if kind == "concat": return gen_regex(rng, depth + 1) + gen_regex(rng, depth + 1) if kind == "union": return "(" + gen_regex(rng, depth + 1) + "|" + gen_regex(rng, depth + 1) + ")" a = gen_regex(rng, depth + 1) if kind == "star": return "(" + a + ")*" if kind == "plus": return "(" + a + ")+" return "(" + a + ")?" def build_dfa_from_expr(expr: str, alphabet: set) -> DFA: postfix = to_postfix(insert_explicit_concat(expr)) nfa = build_nfa(postfix) return subset_construction(nfa, alphabet) rng = random.Random(42) alphabet = {"0", "1"} for i in range(1000): pat = gen_regex(rng) dfa = build_dfa_from_expr(pat, alphabet) s = "".join(rng.choice("01") for _ in range(rng.randint(0, 8))) expected = re.fullmatch(pat, s) is not None actual = dfa_match(dfa, s) if expected != actual: print("MISMATCH", pat, s, expected, actual) break else: print("all 1000 cases passed")

逻辑说明：gen_regex用深度限制避免生成超长嵌套导致 NFA 状态爆炸，rng.choice控制复杂度。参数上，rng = random.Random(42)固定种子，保证每次跑失败的用例可复现；alphabet必须包含测试字符串里可能出现的所有字符，这里只有0和1。re.fullmatch要求整个字符串完全匹配，和 DFA 的接受语义一致。跑完 1000 组全过，基本可以认为解析、构造、确定化、最小化这一整条链路没有大问题。

6.3 把对拍器做成 pytest 测试基线

最后把对拍脚本固化成一个测试文件，固定几个边界用例：a*接受空串、a|之类非法输入报错、(a?b)+这种组合表达式在随机对拍中表现。以后你为了性能去改epsilon_closure、换 Hopcroft 算法时，只要跑一遍测试就知道有没有破坏语义。我之前的习惯是只写核心算法不写测试，加一个随机对拍立刻跑出十几个不一致的用例，全部来自细节漏写。从那次开始，每次做完最小化都顺手存一个对拍基线，改动后跑一遍，相当于给未来的自己留了后悔药。希望帮到你。

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