简介面向编译原理与形式语言课程的Python实现资料完整覆盖正则表达式转NFA、NFA确定化为DFA、DFA最小化三个核心环节涉及子集构造与状态等价类划分等经典算法适合正在完成课程设计、备战考试或复习自动机理论的学生。压缩包共9个文件包含3个Python源码、2个Markdown说明文档、3张流程示意图及1份License整体约243KB代码与文档分层存放配有目录说明便于快速定位源码、图片与报告。目前已有355人学习。资料不仅提供NFA.py、DFA.py、MINI.py等可直接运行的脚本还通过图文README和作业报告详细说明了类设计、变量选择、幂集构造与Hopcroft最小化的实现细节以及测试输出和中间结果展示能够帮助读者快速理解NFA与DFA的转换逻辑和状态化简原理。对于需要提交编译原理课程报告的学生这份资源既能作为算法参考也能作为项目结构与文档撰写的范例实用价值较高。1. 这份正则式转 NFA 与 DFA 最小化的 Python 实现解决的不是算法题而是作业闭环如果你正在刷编译原理的课程设计大概率会撞上这个经典组合正则式转 NFA、NFA 确定化、DFA 最小化。理论书上的定义到了动手写代码时第一个卡点往往不是算法本身而是不知道用什么数据结构去表达“不确定的状态转移”和“epsilon 闭包”。我拆这份资源时最直观的感受是代码不是为了炫技写的而是对着作业需求一步步铺开的NFA.py、DFA.py、MINI.py 三个文件正好对应三个阶段还带一份 Markdown 报告适合当课程设计的骨架。适合两类人一类是正在写作业但不想整个推倒重来的学生另一类是想把形式语言理论落到 Python 代码上的从业者。2. 正则式转 NFAThompson 构造法背后的状态组织方式2.1 为什么必须用 epsilon 边来拼接子自动机在做 NFA 构造之前得先纠正一个常见的理解偏差。我们不是先解析出完整的正则表达式树再去一次性生成 NFA而是采用 Thompson 构造法把正则式拆成最小的语法单元每个单元对应一个子 NFA 片段然后用 epsilon 转移把片段粘起来。epsilon 边的作用就是“免费跳转”它让子自动机之间的连接不需要消费输入字符这也是 NFA 不确定性的来源之一。这份资源的第一层价值就在于把 NFA 的数据结构定义得足够朴素。它用字典来表示状态转移键是源状态编号值是一个列表列表里存的是(字符, 目标状态)或(ε, 目标状态)。这样的设计在后续做确定化时遍历转移关系非常方便不需要额外维护邻接矩阵。我在拆代码时看到 NFA.py 里核心的add_transition函数就是往字典里追加条目没有什么高深的技巧但胜在简洁。2.2 用栈结构模拟正则表达式的优先级在实际构造 NFA 之前必须先解决“如何把正则式拆成片段”的问题。很多初学者在这里翻车是因为直接用 Python 的re模块去解析用户输入的正则式然后试图从匹配结果反推自动机结构。这个路子走不通因为re模块是基于回溯的匹配引擎不是基于自动机构建的它不会给你暴露 NFA 的状态转移表。正确的做法是自己写一个小的解析器用两个栈来模拟运算优先级一个操作数栈存 NFA 片段一个运算符栈存|、*、连接符和括号。这里的“连接符”不需要用户显式输入而是在解析过程中检测到两个相邻的字符或子表达式时隐式压入的。比如正则式ab解析器会在a和b之间插入一个连接操作等价于a·b。核心处理逻辑我简化整理如下def regex_to_postfix(pattern): # 把中缀正则式转成后缀形式方便后续用栈构造 NFA # 其中 . 表示连接操作| 表示并操作* 表示闭包 output [] op_stack [] precedence {|: 1, .: 2, *: 3} for ch in pattern: if ch.isalnum(): # 普通字符直接输出 output.append(ch) elif ch (: # 左括号压栈 op_stack.append(ch) elif ch ): # 右括号弹栈直到左括号 while op_stack and op_stack[-1] ! (: output.append(op_stack.pop()) op_stack.pop() # 弹出左括号 else: # 运算符 while (op_stack and op_stack[-1] ! ( and precedence.get(op_stack[-1], 0) precedence.get(ch, 0)): output.append(op_stack.pop()) op_stack.append(ch) while op_stack: output.append(op_stack.pop()) return .join(output)这段代码把a(b|c)*d这样的中缀正则式转成后缀形式abc|*·d·。核心逻辑是借用运算符优先级把隐式的连接运算符.显式化括号内的内容先处理。参数说明pattern是用户输入的正则式output是后缀表达式列表后续遍历它就能顺序构造 NFA。值得注意的是这段代码假设输入正则式已经合法没有做括号匹配的校验实际使用时可以在入口处先做一次完整的合法性检查。拿到后缀表达式之后NFA 的构造就变成机械的入栈出栈操作。遇到字符就创建一个两状态子自动机遇到运算符就弹出对应的子自动机并进行合并。这类实现思路和计算器求值很像但每个元素从“数字”换成了“NFA 片段”。合并时的关键点是必须新建一个唯一的起始状态和接受状态然后用 epsilon 边连接原片段的起止状态这样每个运算符产生的子自动机仍然保持“单入单出”的结构为下一步继续拼接做好准备。3. NFA 确定化epsilon 闭包与子集构造法的完整实现逻辑3.1 epsilon 闭包计算的迭代细节NFA 确定化的第一步是计算每个状态集合的 epsilon 闭包。这个操作在资源里对应的核心函数是epsilon_closure它在 DFA.py 里被反复调用。闭包的定义不难理解从一个状态集合出发沿 epsilon 边能到达的所有状态都要包含进来而且这个过程是递归的因为 epsilon 边可以串联形成一条跳转链。很多实现会用递归去写闭包函数但 Python 的递归深度默认只有 1000如果正则式嵌套很深很容易触发RecursionError。这份资源里用的是显式的栈迭代避免了这个问题。我把它对应的核心逻辑整理如下def epsilon_closure(state_set, nfa): # state_set 是当前关注的状态集合nfa 是已经构造好的 NFA 对象 # 返回 state_set 的 epsilon 闭包即所有通过 epsilon 边可达的状态 closure set(state_set) stack list(state_set) while stack: state stack.pop() # 查找从当前状态出发的所有 epsilon 转移 for target in nfa.transitions.get(state, {}).get(ε, []): if target not in closure: closure.add(target) stack.append(target) return closure这个函数值得细看两处。第一处是nfa.transitions.get(state, {}).get(ε, [])这里用了两层.get()来避免KeyError因为并不是每个状态都有 epsilon 转移。第二处是stack的使用每发现一个新的可达状态就把它压栈继续探索它的 epsilon 边直到栈为空时闭包计算才结束。参数说明state_set是一个 set建议传入时保证元素是整数状态编号nfa.transitions是形如{状态编号: {字符: [目标状态列表]}}的字典。从工程角度看这个函数是整个确定化过程里调用最频繁的基础设施它的正确性直接决定后面 DFA 状态是否完整。3.2 子集构造法如何避免状态爆炸NFA 确定化的核心循环是从起始状态的闭包开始对输入字母表中的每个字符计算所有可达状态的闭包形成一个新的 DFA 状态。如果这个新状态之前没出现过就加入待处理队列。这个过程叫子集构造法也叫 powerset construction。在实现时最常见的性能问题是 DFA 状态数量理论上是指数级的。虽然实际正则式产生的 NFA 状态数不多但如果不加控制地盲目扩展仍然可能出现“状态爆炸”。解决思路在资源里体现得很直接用字典dfa_states记录已生成的 DFA 状态key 是对应的 NFA 状态集合的冻结集合frozensetvalue 是 DFA 状态编号。这样在循环中只需要检查当前集合是否已经在字典里就能避免重复计算。def subset_construction(nfa, alphabet): # nfa 是 NFA 对象alphabet 是输入字母表集合 # 返回 DFA 的转移表、起始状态和接受状态集合 dfa_transitions [] # 每个元素是 {字符: 目标DFA状态} dfa_state_map {} # frozenset - DFA 状态编号 start_state frozenset(epsilon_closure({nfa.start}, nfa)) dfa_state_map[start_state] 0 dfa_transitions.append({}) queue [start_state] accepting_states set() while queue: current queue.pop(0) current_id dfa_state_map[current] for char in alphabet: next_set set() # 遍历当前集合中的所有 NFA 状态 for state in current: targets nfa.transitions.get(state, {}).get(char, []) next_set.update(targets) if next_set: next_closure frozenset(epsilon_closure(next_set, nfa)) if next_closure not in dfa_state_map: new_id len(dfa_transitions) dfa_state_map[next_closure] new_id dfa_transitions.append({}) queue.append(next_closure) next_id dfa_state_map[next_closure] dfa_transitions[current_id][char] next_id # 如果当前 DFA 状态对应的 NFA 集合包含原接受状态 if current nfa.accepting: accepting_states.add(current_id) return dfa_transitions, 0, accepting_states这段代码里的queue.pop(0)是典型的 BFS 写法在状态量不大时完全够用。参数说明alphabet必须预先从正则式中提取出来一般是所有出现过的普通字符集合不包括 epsilondfa_transitions的索引就是 DFA 状态编号每个元素是一个字符到目标状态的映射accepting_states是在构造过程中顺带计算的只要 NFA 状态集合里包含原接受状态对应的 DFA 状态就是接受状态。这里有一个值得注意的细节current nfa.accepting判断的是集合是否有交集。如果你的 NFA 有多个接受状态这个条件可以正确处理不要改写为current nfa.accepting那是常见误用在存在多余 epsilon 跳转时会漏掉接受状态。4. DFA 最小化Hopcroft 划分如何正确合并不可区分状态4.1 划分的初始化为什么不能只看终态DFA 最小化最常用的方法是基于等价类划分。核心思路是把 DFA 的所有状态划分成若干组组内状态在任意输入串下都不可区分然后每组合并成一个状态。初始化划分时第一刀切在“终态”和“非终态”之间因为终态和非终态在接受性上的表现不同不可能等价。这一点初学者都能理解但真正的难点在于后续迭代划分时怎么判断组内的状态是否需要进一步分裂。判断规则是如果在某个输入字符下组内两个状态转移到的目标状态属于不同的组那这两个状态就不等价需要把原组拆开。这份资源里的 MINI.py 用的是迭代细化法不断检查每个组在字母表下的转移目标是否落在同一组内直到所有组都稳定。实现时有个细节容易忽略分组时不仅要把转移目标分组编号记下来还要记录是从哪个输入字符触发的否则下一次迭代分组的依据不完整。4.2 分裂过程的实现与状态重编号在实现分裂逻辑时我见过不少代码直接修改正在遍历的分组列表导致漏掉某些状态。正确的做法是维护一个“待检查的工作列表”每次从里面取出一个组进行分裂测试如果分裂出新的组再把新组加入工作列表。这本质上是 BFS 式的传播因为一个组分裂可能会影响其他组的等价关系。def minimize_dfa(dfa_transitions, accepting_states): # dfa_transitions 是子集构造得到的 DFA 转移表 # accepting_states 是接受状态集合 # 返回最小化后的 DFA 转移表、起始状态、接受状态集合 n len(dfa_transitions) # 初始化划分终态一组非终态一组 groups [set(accepting_states), set(range(n)) - set(accepting_states)] # 去掉空组 groups [g for g in groups if g] alphabet set() for t in dfa_transitions: alphabet.update(t.keys()) changed True while changed: changed False new_groups [] for group in groups: # 用转移目标所在组的编号作为签名 signature_map {} for state in group: sig [] for char in sorted(alphabet): target dfa_transitions[state].get(char, -1) # 找到 target 属于哪个组用组索引作为签名的一部分 group_idx -1 for idx, g in enumerate(groups): if target in g: group_idx idx break sig.append(f{char}:{group_idx}) sig_str |.join(sig) signature_map.setdefault(sig_str, set()).add(state) if len(signature_map) 1: changed True new_groups.extend(signature_map.values()) groups new_groups # 重新编号每个组映射到新的 DFA 状态 state_mapping {} new_transitions [] new_accepting set() for new_id, group in enumerate(groups): for old_state in group: state_mapping[old_state] new_id if old_state in accepting_states: new_accepting.add(new_id) for group in groups: old_rep next(iter(group)) new_trans {} for char in alphabet: target dfa_transitions[old_rep].get(char, -1) if target ! -1: new_trans[char] state_mapping[target] new_transitions.append(new_trans) new_start state_mapping[0] return new_transitions, new_start, new_accepting这段代码的核心是签名机制对每个状态计算它在所有输入字符下转移目标所在组的编号列表作为它的“签名”。如果组内状态的签名不同说明它们可以被区分需要分裂成多个组。changed标志确保循环直到没有组再分裂才终止。参数说明dfa_transitions里每个状态的转移表默认缺失的字符表示死状态代码里用-1来统一表示不存在的转移但在后续重编号时没有为死状态预留新编号这是一个容易忽略的点如果你的 DFA 中包含显式死状态需要在重编号之前为死状态单独分配一个编号否则状态映射会错位。这里有一个新手常犯的错误直接用old_rep的转移来代表整个组这在组内状态等价时是正确的但如果你的分组逻辑有 bug导致状态并未真正等价那么转移信息就会失真。所以最小化算法的验证必须放在最后用随机字符串在最小化前后的 DFA 上做一致性测试这一步不能省。5. 避坑记录从空白输出到状态爆炸的五个常见问题5.1 输出结果总是空白问题出在解析阶段现象程序没有任何报错但生成的 NFA 和 DFA 都是空结构或者只包含起始状态和接受状态中间的转移边一条都没有。原因正则式解析时隐式连接符没有正确处理。比如ab被解析成两个独立的字符没有生成连接操作导致 NFA 片段之间没有 epsilon 桥接。更隐蔽的情况是字符类[a-z]没有被展开直接被当成单个符号。解决在解析入口处打印后缀表达式检查是否出现了预期的.操作符。如果[a-z]这类字符类出现需要在预处理阶段把它展开为a|b|c|...|z的形式再送入解析器。我拆这份资源时注意到它的代码没有做字符类展开但作业里如果要求支持需要自己补这一段。5.2 epsilon 闭包计算少了间接可达的状态现象确定化后某些 DFA 状态对某个输入字符没有任何转移但手工推演 NFA 时这个字符明明可以走到某个可接受状态。原因闭包计算的循环写成了单层遍历只考虑了直接 epsilon 转移没有用栈或队列去展开间接转移。比如状态 A 有 epsilon 边到 BB 有 epsilon 边到 C单层遍历只能发现 B无法发现 C。解决改用显式栈每加入一个新状态就压栈继续探索。验证方法很简单构造一个包含两个连续 epsilon 边的 NFA跑一下闭包函数看看是否包含三个状态。我一般会加一个断言函数专门检查“闭包结果必须对 epsilon 转移封闭”不满足就抛异常。5.3 确定化后出现无效状态输入任意字符都回到自身现象生成的 DFA 里有一个状态对字母表中所有字符的转移都指向它自己而且它不是接受状态。原因没有显式定义死状态。在子集构造中如果某个字符下没有可达的 NFA 状态集合很多实现就跳过这条转移导致 DFA 状态转移表缺少该字符的处理。后续做最小化时这个空缺会被解释成“无转移”而其他状态可能会指向一个隐含的死状态造成不一致。解决在子集构造时为缺失的转移统一填入一个显式死状态编号比如-1或n1并把这个死状态也加入状态集合。最小化时对死状态单独处理不要让它参与分组。常见做法是给死状态单独编号并让它的所有转移指向自己。5.4 最小化后合并掉了接受状态现象最小化之后原本的接受状态集合发生了变化部分非接受状态变成了接受状态或者反过来。原因在重编号阶段用old_state in accepting_states来判断新状态是否接受这里没有问题。但如果你在分组时把终态和非终态分到了同一组就会出现不可逆的错误。通常原因是初始化分组时用了set(range(n)) - set(accepting_states)但这里的accepting_states如果是从子集构造阶段继承下来的可能包含了死状态的编号而死状态不应该参与终态判断。解决在最小化之前打印输出每一个 DFA 状态对应的 NFA 状态集合人工核对终态的映射关系。这是一个黑匣子步骤不打印中间结果很难发现问题。我习惯在子集构造和最小化之间增加一个断言assert accepting_states set(range(n))防止越界。5.5 Python 递归深度影响闭包计算现象正则式里包含大量交替和嵌套闭包比如(a|b|c|d|e)*运行时报RecursionError: maximum recursion depth exceeded。原因闭包计算如果用递归写法深层嵌套的 epsilon 链会耗尽递归栈。虽然递归写法看起来更清晰实测中确实会遇到这个边界。解决把递归改为显式栈迭代就是章节 3.1 里的写法。这是最稳妥的方案。如果坚持用递归可以在文件头部设置sys.setrecursionlimit(10000)但这只是延后问题不是根治。从那以后我每次写闭包计算都强制走显式栈迭代。6. 验证 DFA 的正确性用随机串测试和转移表可视化保住作业分数完成三个阶段的代码之后最容易被忽略的是验证环节。课程设计的验收不只看结果还会看你对代码正确性的把握程度。一个很实用的技巧是写一个随机字符串生成器在 NFA 和最小化后的 DFA 上分别模拟匹配比对结果是否一致。这个做法比分几个手写用例可靠得多因为随机测试能覆盖到状态组合的边界条件。模拟 NFA 匹配时要注意存在多条路径可以同时推进不能用简单的单路径模拟而是维护一个“当前可达状态集合”每个字符输入后先计算字符转移的并集再做 epsilon 闭包。而 DFA 模拟就简单得多每个字符输入后走唯一的转移边即可。把两者的结果对比如果出现不一致就缩小随机种子递归定位到导致不一致的最小字符串这个最小反例往往能直接指出你代码里的逻辑 bug。另外把 DFA 转移表打印成矩阵形式也能帮助快速排查。我用一个简单的函数输出状态行每行列出一组“字符-目标状态”再加上是否接受的标记。以下是我在验证 DFA 最小化时常写的一段辅助代码def print_dfa_table(transitions, start, accepting): # 打印 DFA 转移表方便人工核对 # transitions 是 {状态编号: {字符: 目标状态}}accepting 是接受状态集合 alphabet set() for t in transitions: alphabet.update(t.keys()) alphabet sorted(alphabet) print(f起始状态: {start}) print(状态.ljust(6) .join(ch.ljust(6) for ch in alphabet) 接受?) for state, trans in enumerate(transitions): row str(state).ljust(6) for ch in alphabet: target trans.get(ch, -) row str(target).ljust(6) row 是 if state in accepting else 否 print(row)在打印结果里我最关注两列一是是否存在某个状态对所有字符都转到自身且不是接受状态这通常意味着死状态没处理干净二是是否存在不可达的孤立状态因为这会影响最小化后的状态数量还可能让作业验收时讨论环节扣分。验证时我一般会跑三个层次的测试第一层是单字符测试比如正则式aNFA 和 DFA 都应该只接受a第二层是空串测试检查a*是否接受空串这是最常见的边界第三层是随机串批量测试样本量至少 5000 条字符串长度从 0 到 8 均匀分布。随机测试通过之后代码的正确性就站得住了。这份资源虽然没有自带测试脚本但按照这个思路补一段测试代码整体作业的完成度能高出不少。这个项目里最值得带走的东西不是三份代码文件本身而是“每一阶段都能被验证”的工程习惯。做编译原理课程设计时最恼人的是算法写完了却不知道对不对。从那以后我做这类自动化构造的任务都会强制走一遍“随机测试 最小反例定位”的流程治好了不少因为玄学翻车带来的失眠。希望帮到你。本文还有配套的精品资源点击获取