简介面向编译原理课程设计的完整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. 正则式转 NFAThompson 构造法与解析器的三个细节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: 正闭包 aa 的终态能回 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(fstart{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 还没有补死状态比如输入字符串里出现2dfa_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这是性能刚需如果你的状态数在一千以内划分法跑起来都是毫秒级。算法最坏时间复杂度实现难度建议场景划分法O(k·n²)低课程设计、状态数 1000HopcroftO(k·n·log n)高引擎内部、状态数 10000我的建议是先写划分法跑通正确性如果后面真的遇到大规模 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 [fdigraph {name} {{, rankdirLR;] 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 的输出只依赖状态编号和转移表不会引入额外依赖。渲染时如果看到某个子图有奇怪的 ε 环或孤立状态基本就是构造阶段的偏移量或 ε 边写错了。参数上rankdirLR让图横向展开状态多时比纵向更易读。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 算法时只要跑一遍测试就知道有没有破坏语义。我之前的习惯是只写核心算法不写测试加一个随机对拍立刻跑出十几个不一致的用例全部来自细节漏写。从那次开始每次做完最小化都顺手存一个对拍基线改动后跑一遍相当于给未来的自己留了后悔药。希望帮到你。本文还有配套的精品资源点击获取