简介面向编译原理课程学习者这份压缩包完整覆盖正则表达式到最小化DFA的经典转换流程包含正则式转NFA、NFA确定化转DFA、DFA最小化转MFA三个独立可运行的Python程序并配套Word设计报告详细说明各程序的设计思路、变量含义与实现要点适合正在完成相关作业或复习自动机理论的本科生及自学者。包内共10个文件以py源码、png示意图、md说明文档及docx报告为主整体仅498KB轻量易用3个Python程序对应三个转换模块3张PNG图片展示关键流程Word报告则对类设计与变量作了梳理。资源浏览/学习人数已达1050人内容兼具可运行代码与理论文档既能作为编译原理实验的参考实现也可为课程设计或期末复习提供完整范本。1. 正则式转NFA再转DFA再最小化一条能直接落地的编译原理老路拿到「正则式转NFA、NFA转DFA、DFA转MFADFA最小化」这类压缩包资源第一反应不应该是背公式而是确认一件事这三段转换能不能串成一条可运行的流水线。正则式不是机器能直接执行的东西NFA能跑但每个字符都要尝试多条路径DFA快但状态数可能膨胀最小化之后的DFA也就是标题里说的MFA才是词法分析器、规则引擎、文本搜索里真正落地的那张状态表。这条链路解决的就是一个问题把人类写的表达式变成一张确定、最小、可查表的自动机。适合三类人正在啃编译原理的学生想自己写词法分析器或正则引擎的工程师以及面试前想把这个经典考点彻底搞清楚的人。下面按这条链路拆开讲每步都给出能跑的实现和参数边界。2. 正则式转NFAThompson构造法与一个能跑的最小实现2.1 先立住为什么第一步必须生成NFA而非直接生成DFA直接由正则式构造DFA不是不行但要同时处理连接、并、闭包三种运算的嵌套状态含义会非常难设计。Thompson构造法的高明之处在于正则表达式的每种语法结构都对应一种固定的NFA拼装方式字符对应一条边连接就是把前一个接受态接到后一个起始态并集用两个新状态包住两个子NFA闭包用四个ε边绕一个环。整个过程可以完全递归地写出来不需要任何全局分析。这一步生成的是NFA天然允许两个特性ε转移和同一个符号的多条出边。前者让拼装变得简单后者让同一时刻可能需要探索多条路径。这两个特性也是NFA难直接用于工程的原因所以下一步必须子集构造。很多初学者在这里急着跳步想直接从正则式画DFA结果画到嵌套闭包就乱套。我自己的经验是老老实实先生成NFA每一步都能用代码和纸笔双重验证后面出了错也容易定位。2.2 数据结构与Thompson四段实现从字符到闭包NFA的数据结构不需要复杂状态用全局递增整数编号转移用三元组列表表示。符号统一用单个字符ε用None占位。先定义基础设施_state_counter 0 def new_state() - int: global _state_counter s _state_counter _state_counter 1 return s class NFA: def __init__(self): self.transitions [] # 每条边: (from_state, symbol, to_state) self.start None self.accept Nonetransitions里每个元素是(起点, 符号, 终点)符号为None就是ε边。状态不单独建对象用整数编号就够了画图、排错都方便。下面是Thompson构造法的四个核心函数def char_nfa(symbol: str) - NFA: n NFA() n.start new_state() n.accept new_state() n.transitions.append((n.start, symbol, n.accept)) return n def concat_nfa(a: NFA, b: NFA) - NFA: n NFA() n.start, n.accept a.start, b.accept n.transitions a.transitions b.transitions n.transitions.append((a.accept, None, b.start)) return n def union_nfa(a: NFA, b: NFA) - NFA: s, t new_state(), new_state() n NFA() n.start, n.accept s, t n.transitions a.transitions b.transitions n.transitions [(s, None, a.start), (s, None, b.start), (a.accept, None, t), (b.accept, None, t)] return n def star_nfa(a: NFA) - NFA: s, t new_state(), new_state() n NFA() n.start, n.accept s, t n.transitions a.transitions n.transitions [(s, None, a.start), (a.accept, None, a.start), (a.accept, None, t), (s, None, t)] return nconcat_nfa把a的接受态和b的起始态用一条ε边连起来b的接受态成为整体接受态。union_nfa新造一个起始态和一个接受态让它们分别通过ε边连接两个子NFA。star_nfa的四个ε边里(a.accept, None, a.start)是回环保证重复任意多次(s, None, t)保证闭包接受空串。所有子NFA的起点、终点都是新建状态互相不重叠所以直接拼接转移列表是安全的。参数上需要注意symbol必须是单个字符多字符符号要先行拆分否则后面move按字符匹配时会漏边。有了这四个函数还需要一个解析器把正则式字符串变成嵌套的NFA构造调用。按优先级从低到高处理|、连接、*、括号class Parser: def __init__(self, pattern: str): self.pattern pattern self.pos 0 def parse(self) - NFA: n self.parse_union() if self.pos ! len(self.pattern): raise ValueError(funexpected char at {self.pos}) return n def parse_union(self) - NFA: left self.parse_concat() while self.pos len(self.pattern) and self.pattern[self.pos] |: self.pos 1 right self.parse_concat() left union_nfa(left, right) return left def parse_concat(self) - NFA: left self.parse_factor() while self.pos len(self.pattern) and self.pattern[self.pos] not in |): right self.parse_factor() left concat_nfa(left, right) return left def parse_factor(self) - NFA: atom self.parse_atom() while self.pos len(self.pattern) and self.pattern[self.pos] *: self.pos 1 atom star_nfa(atom) return atom def parse_atom(self) - NFA: ch self.pattern[self.pos] if ch (: self.pos 1 inner self.parse_union() if self.pattern[self.pos] ! ): raise ValueError(missing )) self.pos 1 return inner if ch in |)*: raise ValueError(funexpected operator {ch}) self.pos 1 return char_nfa(ch)解析器是递归下降写法parse_union遇到|就继续吞右操作数parse_concat直到遇见|或)才停parse_factor只处理后缀*。这里有个容易忽略的参数约束表达式里的.、\d这类转义序列如果要支持应该在parse_atom阶段先展开成对应的字符集合再生成对应的子NFA而不是塞进char_nfa。工程上常见的字符类、?、、{n,m}都是在解析层做语法糖展开NFA构造层只认字符、ε、并、连接、闭包这五种原语。2.3 调试习惯先手推NFA再跑代码写完成套构造器之后别急着接下一步。我一般会拿纸笔对一个小正则手推一遍NFA再跑代码对照。比如对1(0|1)*101先手推1生成一条边(0|1)生成一个并集子NFA*在外面包一个闭包最后依次连接1、0、1三个字符NFA。手推能帮你确认每个子NFA的起点和终点编号跑代码时如果状态数对不上说明某个构造函数的转移列表拼接错了。这个习惯在整条链路里能省下大量排错时间因为NFA错了后面DFA和MFA全是错的。3. NFA转DFA子集构造法与「1(0|1)*101」的完整推导3.1 怎么求NFA等价的DFAε闭包和move是全部答案怎么求NFA等价的DFA标准答案是子集构造法。核心就两个操作。第一个是ε闭包从一个NFA状态集合出发把所有能通过ε边到达的状态都加进来。第二个是move给定一个状态集合和一个输入符号找所有从集合内状态出发、通过该符号边能到达的状态。DFA的每个状态就是NFA状态的一个子集转移关系由「吃一个符号后再求ε闭包」定义。def epsilon_closure(nfa: NFA, states: set) - frozenset: stack list(states) closure set(states) while stack: s stack.pop() for src, sym, dst in nfa.transitions: if src s and sym is None and dst not in closure: closure.add(dst) stack.append(dst) return frozenset(closure) def move(nfa: NFA, states: frozenset, symbol: str) - set: nxt set() for src, sym, dst in nfa.transitions: if src in states and sym symbol: nxt.add(dst) return nxtepsilon_closure用栈做遍历closure里的frozenset是为了让结果可以作为字典键。注意必须用visited性质的not in closure判断否则遇到ε环会死循环。move是纯粹的单层扫描不做ε扩展扩展交给调用它的epsilon_closure。这两个函数分开写比合并成一个「闭包加吃字符」的函数更清晰因为后面最小化和NFA模拟都要单独复用epsilon_closure。符号参数就用单个字符如果正则里出现过.这类通配符此时要把所有可匹配字符逐个展开调用move这也是为什么下一步的DFA构造需要显式传入字母表。3.2 子集构造的主体代码构造1(0|1)*101相应的DFA子集构造用BFS逐层生成DFA状态队列里放的是DFA状态编号每个DFA状态对应一个frozenset的NFA状态集合。对每个输入符号计算目标子集如果没见过就登记为新DFA状态def nfa_to_dfa(nfa: NFA, alphabet: list) - dict: start_subset epsilon_closure(nfa, {nfa.start}) seen {start_subset: 0} dfa {alphabet: list(alphabet), states: [start_subset], transitions: [], start: 0, accept: set()} if nfa.accept in start_subset: dfa[accept].add(0) queue [0] while queue: cur queue.pop() for sym in alphabet: nxt epsilon_closure(nfa, move(nfa, dfa[states][cur], sym)) if not nxt: continue # 空集合表示死状态先省略 if nxt not in seen: seen[nxt] len(dfa[states]) dfa[states].append(nxt) if nfa.accept in nxt: dfa[accept].add(seen[nxt]) queue.append(seen[nxt]) dfa[transitions].append((cur, sym, seen[nxt])) return dfa这里的alphabet必须在调用前确定常见做法是从正则式里扫描出现的字面字符再加上转义展开后的字符集合。seen字典避免重复状态同时把frozenset子集映射成整数状态号。判断接受态的关键是每次新建DFA状态时都要检查它对应的NFA状态子集是否包含原NFA接受态漏掉这一步是后续所有奇怪bug的根源。transitions里的三元组和NFA结构一致只是符号不再有None。把1(0|1)*101扔进这段代码得到的DFA有6个可达状态补全死态后是7个。为了让结果可读我把状态起成语义名整理成下面的表这就是题目热词里「构造1(0|1)*101相应的DFA」的答案当前状态读入0读入1含义q0起始qdq1还没读入开头那个1q1q1q2开头满足尚未开始匹配结尾的101q2q3q2已看到结尾101中的第一个1q3q1q4已看到结尾101中的前两位10q4接受q3q2已完整匹配到101qdqdqd死状态永远无法接受逐行验证一遍空串在q0不是接受态正确。1走到q1不是接受态正确因为1不满足1(0|1)*101。1101走q0→q1→q2→q3→q4接受正确。101走q0→q1→q1→q2拒绝正确因为101不以101结尾。这个表比直接看frozenset状态名直观得多工程里也常把DFA状态按语义命名对应词法分析里的token类型。3.3 死状态要不要画补全与省略的工程约定上面代码里if not nxt: continue把死状态跳过了DFA转移表里凡是没有对应转移的模拟时默认拒绝。这种省略写法在演示算法时很常见但到了最小化和测试阶段会有麻烦划分最小化时缺失转移会被特殊处理随机验证时模拟器遇到缺转移直接返回False。两种约定混用容易出分歧。我一般会提供两个入口nfa_to_dfa默认省略死状态适合画图再加一个complete_dfa把缺失转移补到显式的死状态。补全逻辑很直接加一个死状态编号把所有缺的转移指向它死状态自环全部符号。第4章的最小化算法我采用了「缺转移按特殊组处理」的方式所以省不省死状态都能跑但如果你要拿别人的DFA数据喂给标准Hopcroft实现最好先确认对方是否包含完整转移。这个约定问题在团队协作时很容易成为翻车点提前在函数注释里写清楚就行。4. DFA最小化从DFA到MFA的划分法与一次真实的最小化4.1 最少状态DFAMFA通过划分法把等价状态合并DFA转MFAMFA就是最小化DFA即状态数最少的等价DFA。标题里这个叫法在中文编译原理教材和作业资源包里很常见业界更多叫「DFA最小化」或「最少状态DFA」。为什么要做这一步子集构造产生的DFA状态对应NFA状态集合很可能出现两个集合行为完全一样的情况——它们接受相同的语言、对任何输入走到接受性相同的状态。这种状态留着只会让转移表变大、缓存命中变差没有任何收益。最小化的经典算法是划分法思路是反向合并先把状态分成接受组和非接受组然后反复检查每组内部每个状态是否对每个输入符号都转移到同一组。不一致就分裂直到所有组稳定。每一组里的状态就是等价的可以合并成一个MFA状态。这个算法听着简单实现里坑不少尤其是「用当前划分计算签名」和「多轮迭代直到稳定」这两步。4.2 手搓划分法初始化分组、反复细化、重命名状态先看核心实现def minimize_dfa(dfa: dict) - dict: n len(dfa[states]) accept, non_accept dfa[accept], set(range(n)) - dfa[accept] groups [] if non_accept: groups.append(frozenset(non_accept)) if accept: groups.append(frozenset(accept)) while True: new_groups [] changed False for g in groups: buckets {} for s in g: sig [] for sym in dfa[alphabet]: t None for f, c, dst in dfa[transitions]: if f s and c sym: t dst break if t is None: sig.append(-1) # 缺转移视为隐式死态 else: for gi, gg in enumerate(groups): if t in gg: sig.append(gi) break sig tuple(sig) buckets.setdefault(sig, []).append(s) if len(buckets) 1: changed True for ss in buckets.values(): new_groups.append(frozenset(ss)) groups new_groups if not changed: break remap {} for new_id, g in enumerate(groups): for s in g: remap[s] new_id min_dfa {alphabet: dfa[alphabet], states: [], transitions: [], start: remap[dfa[start]], accept: set()} for new_id, g in enumerate(groups): min_dfa[states].append(g) if any(s in dfa[accept] for s in g): min_dfa[accept].add(new_id) rep min(g) for sym in dfa[alphabet]: t None for f, c, dst in dfa[transitions]: if f rep and c sym: t dst break if t is not None: min_dfa[transitions].append((new_id, sym, remap[t])) return min_dfa关键在划分循环每个状态对每个符号产生一个「签名」签名里记录的是目标状态在当前划分里的组号缺转移记为-1代表进入隐式死态。同一组里签名不同的状态必须分裂。这里用的是旧划分计算签名新分裂推迟到下一轮生效属于同步更新不要边算边改groups否则一轮内就会产生连锁分裂结果虽然通常也对但很难推理。循环结束后把每个组重命名为一个MFA状态取组内最小原状态号作为代表来重建转移表。接受状态用any判断因为整组要么都接受、要么都不接受。用一个有冗余的DFA来验证这个函数。假设手工构造一个语言为{0,1}的DFA起始态0读0去1、读1去2状态1和2都接受且读0读1都去3状态3读任何符号都留在3。这里1和2行为完全相同最小化后应该合并原DFA状态数4最小化后状态数3。minimize_dfa跑出来初始划分是{1,2}和{0,3}两组检查{0,3}时0读0到1在{1,2}组、读1到2也在{1,2}组而3读0、读1都留在{0,3}组签名立刻不同于是0和3分裂。最终分组是{0}、{1,2}、{3}1和2成功合并。这个例子说明划分法吃的是「行为」不是「编号」。4.3 对1(0|1)*101最小化它已经是最小状态把第3章那个7状态DFA喂给minimize_dfa结果可能出乎意料一个状态都合并不了。逐轮划分看得很清楚轮次当前分组本轮分裂出的状态初始{q0,q1,q2,q3,qd}{q4}第1轮{q0,q1,q2,qd} {q3} {q4}q3第2轮{q0,q1,qd} {q2} {q3} {q4}q2第3轮{q0,qd} {q1} {q2} {q3} {q4}q1第4轮{q0} {qd} {q1} {q2} {q3} {q4}q0第1轮q3分裂是因为它读1到接受态q4而同一组的其它状态读1都到非接受态。第2轮q2分裂因为它读0到已独立的q3。第3轮q1分裂因为它读1到已独立的q2。第4轮q0和qd终于分开qd读所有符号都留在组内q0读1却到了q1。最终每组只剩一个状态MFA就是原DFA本身。这不是代码错了而是这类带「进度」语义的DFA天然接近最小q1到q4每个状态对应匹配结尾101的不同进度对任何输入的后缀行为都不同而qd是真正的死态两者不可能等价。这个案例值得单独记住——最小化不是总能压缩状态数它保证的是「不会比最小更多」。以后你看到某个DFA最小化前后状态数没变先别怀疑算法想想是不是每个状态都有不可替代的语义。5. 避坑五个容易在转换链路上翻车的细节5.1 ε闭包只算一层a*直接卡在半路现象对a*构造NFA后模拟空串返回False或者a只匹配到一次就停。原因epsilon_closure只遍历了直接ε出边没有用栈继续扩展。star_nfa里有(accept, None, start)这样的回环ε闭包必须沿着这个环一直走直到没有新状态为止。写成单层循环的闭包遇到ε环必然漏状态DFA起始子集会少一整个循环上的状态。解决按epsilon_closure那段代码的栈式写法每个状态入栈时判重出栈时扫描所有出边。判重集合同时就是闭包结果别用两个set来回倒腾。5.2 死状态被省掉最小化跑出一张乱跳的表现象nfa_to_dfa里continue跳过空集结果minimize_dfa跑完某些串的接受结果和原DFA不一致。原因缺转移在划分时被记为-1重建MFA转移表时又跳过None目标相当于把「隐式死态」和某些真实状态混在一个签名维度里处理。如果原DFA里有状态只差「缺转移与否」这一项划分法可能把它们错误地分到同一组。解决两条路选一条。要么在最小化之前调用补全函数把死状态显式加进去要么像我上面的实现一样在划分签名里固定把缺转移记为-1并确保-1不和任何真实组号冲突。无论选哪条都要在代码注释里写明约定否则后半个项目组的人一定会踩回来。5.3 共享NFA对象构造上层表达式边串味现象对(a|b)*做完闭包再去构造(a|b)*aNFA里莫名多出几条指向(a|b)内部的边。原因star_nfa和concat_nfa都直接用了传入的NFA对象如果同一个子NFA被两个上层构造引用它的转移列表就被叠加了两次。Thompson构造假设每个子NFA只被使用一次违反这个前提就会串味。解决一种办法是在每个构造函数入口复制传入NFA的转移列表保证上层构造不修改子对象另一种更省心的做法是约束解析器保证每个递归返回的NFA对象只进入一个上层构造。我习惯用复制的方式毕竟解析器改了优先级逻辑后对象复用关系会变得更难审计。5.4 新建DFA状态时漏判接受空串直接被吞现象正则式a*的DFA起始状态不是接受态模拟空串返回False但a*明明匹配空串。原因nfa_to_dfa里只在初始化起始子集时检查了一次nfa.accept in start_subset后续新建DFA状态时忘了检查。空串的接受性完全取决于起始子集漏了这一步整个语言里所有以空串为前缀的情况都会错。解决把if nfa.accept in nxt写进nxt的新状态登记分支并且对起始子集单独做一次同样的检查。顺带养成的习惯是写完nfa_to_dfa立刻手工断言空串、单字符、长串三个用例把接受性先钉死再往下走。5.5 每次运行状态编号都变排查全靠肉眼找现象同一个正则式跑两次程序NFA和DFA的状态编号完全不同想对比两份中间结果只能人工翻译。原因_state_counter是全局的只要之前构造过别的NFA编号起点就偏移。调试时容易让人误以为结果不稳定。解决在构造入口处保存一次_state_counter快照或者把整条链路的中间结果导出成JSON包含NFA转移、DFA转移、MFA转移三份数据。这样复现问题时能锁定某一份现场。评论区里常见的「我的DFA比你多一个状态」八成就是没有记录现场两边编号对不上导致的。6. 验证随机串一致性测试与Graphviz可视化兜底6.1 三份自动机一条断言随机串一致性测试代码写完第一步不是看表是随机打一串进去让NFA、DFA、MFA三个结果互相仲裁。NFA模拟我用独立的回溯搜索不走子集构造的同一套代码这样两边实现互相独立匹配结果一致才说明转换没把语言改掉def simulate_nfa(nfa: NFA, s: str) - bool: def dfs(idx: int, state: int, visited: set) - bool: if (idx, state) in visited: return False visited.add((idx, state)) if idx len(s): if state nfa.accept: return True for f, sym, t in nfa.transitions: if f state and sym is None and dfs(idx, t, visited): return True return False for f, sym, t in nfa.transitions: if f state and sym is None: if dfs(idx, t, visited): return True for f, sym, t in nfa.transitions: if f state and sym s[idx]: if dfs(idx 1, t, visited): return True return False return dfs(0, nfa.start, set()) def simulate_dfa(dfa: dict, s: str) - bool: cur dfa[start] for ch in s: t None for f, c, dst in dfa[transitions]: if f cur and c ch: t dst break if t is None: return False cur t return cur in dfa[accept]随机测试脚本围绕这个断言展开固定随机种子随机生成0到12长度的0/1串分别喂给simulate_nfa、simulate_dfa和最小化后的simulate_dfa三个结果必须完全一致。遇到不一致就先缩短串长再二分定位多数时候问题出在ε闭包或者死状态处理。跑通2000条随机串再把手推的那几个边界串空串、只含开头字符、恰好完整匹配加进用例集。6.2 把NFA/DFA/MFA渲染成DOT图再排查逻辑断言全部通过后我会再把三份自动机丢给Graphviz看一眼。给自动机结构写一个极简的DOT导出def to_dot(machine: dict, name: str auto) - str: lines [fdigraph {name} {{] for i, subset in enumerate(machine[states]): shape doublecircle if i in machine[accept] else circle label ,.join(str(s) for s in sorted(subset)) lines.append(f {i} [label{label}, shape{shape}];) for f, c, t in machine[transitions]: lines.append(f {f} - {t} [label{c}];) lines.append(}) return \n.join(lines)把DFA和MFA两份DOT并排渲染能直观看到哪些状态被合并、哪些死状态被保留。工具链上有时候渲染出的图像一个毛线团多半是NFA里的ε环没有在渲染层折叠这时候把ε边单独标灰优先看DFA图。我现在的习惯是改任何一版构造器先跑随机一致性再渲染两张图对照最后才去优化状态数。这个顺序帮我挡掉了好几次「看起来全对、一跑长串就翻车」的隐性bug。希望帮到你。本文还有配套的精品资源点击获取
