简介面向编译原理课程中的不确定有限自动机NFA转确定有限自动机DFA并最小化实验这份资源提供可直接运行的C源代码和完整实验报告适合郑州大学ZZU及其他高校本科生用于课程实践或复习备考。源代码基于子集构造法完成NFA到DFA的转换并通过剔除不可达状态、合并等价状态实现最小化代码注释清晰、结构紧凑实验报告则详细记录实验目的、算法设计、测试用例与排错思路并包含输入实例的逐步推导过程方便对照理解。资源包为zip压缩格式共两个文件分别是C源文件和实验报告文档整体大小约七百余KB轻量且覆盖完整实验链路。目前已有四百余人学习下载适合正在攻克编译原理实验或想深入理解自动机理论的同学直接参考。1. 编译原理实验的必修题NFA转DFA并最小化到底在考什么把NFA确定化成DFA再最小化这套流程在编译原理实验里几乎是必做题。以ZZU郑州大学的编译原理实验为例常见要求是给一份NFA定义先用子集构造法转成等价DFA再用划分细化算法压缩状态数最后交付代码加实验报告。很多人拿到题第一反应是“直接调个正则库匹配不就行了”但实验真正考的是你手写自动机转换的算法能力——这正是词法分析器从正则规则到可执行代码之间最关键的工序。下面直接上一套能跑通的数据结构和代码从NFA读入一路做到最小化DFA输出中间穿插实验报告怎么写、以及我当年踩过的几个坑。2. 子集构造法落地用Python把NFA确定化成DFA2.1 NFA数据结构选型字典、集合与状态命名做这个实验我首选Python不是因为它快而是set和dict用起来太顺手。子集构造法的核心是“把一组NFA状态当成一个DFA状态”这种集合运算在C里要自己写并集和相等比较在Python里就是一次集合操作的事。数据结构我建议这样组织class NFA: def __init__(self, states, alphabet, transitions, start, finals): self.states states # set[str]全部状态名 self.alphabet alphabet # list[str]不含 ε self.transitions transitions # dict[(str, str)] - set[str] self.start start # str初态 self.finals finals # set[str]终态集合transitions用“源状态, 符号”二元组做key比嵌套字典更省事move函数里查一次dict就能拿到全部目标setdefault合并多条转移也方便。嵌套dict在这个规模下要多写一层循环没必要。alphabet用list不用set是为了保序后面输出DFA转移表时按字母表顺序陈列报告里对齐好看逻辑也不容易乱。finals用set是因为后面判断“NFA状态子集是否含终态”要用集合交集。从文件读入时同一对源状态, 符号可能有多条转移读的时候直接合并到同一个set里。这一步很关键NFA允许同一个符号从同一状态出发到多个状态漏掉合并move取目标时就会丢转移后面生成的DFA残缺不全。2.2 epsilon闭包与move两个基础函数先写稳ε-closure的含义是“从一组状态出发不消费任何输入只靠ε边能到达的全部状态”。实现用栈做DFS不用递归因为NFA里可能存在ε环比如A经ε到B、B又经ε回A递归写法遇到环直接无限递归实验输入里这种环很常见。def epsilon_closure(nfa, states): stack list(states) # 用list当栈DFS遍历 closure set(states) # 闭包必须包含自身 while stack: s stack.pop() for t in nfa.transitions.get((s, ε), set()): if t not in closure: closure.add(t) stack.append(t) return closure注意closure初始化为states本身这是闭包定义的一部分从这些状态出发、不读入任何字符自己当然可达。transitions.get((s, ε), set())的第二个参数给空set是为了让没有ε转移的状态安全跳过省掉一个if判断这个写法在处理缺失key时特别好用。move则相反只走一步、不传递def move(nfa, states, symbol): result set() for s in states: if (s, symbol) in nfa.transitions: result | nfa.transitions[(s, symbol)] return resultmove的语义是“从这些状态出发读入一个symbol后可能到达的原始NFA状态集合”它不做ε传播ε传播交给closure。我第一次写这个实验时顺手在move后面接了个递归把“一步跳”变成“多步跳”生成的DFA状态数直接翻倍手算怎么都对不上。这个教训记到现在move就是查邻接表别加戏。2.3 子集构造主循环frozenset当状态名子集构造的做法是每个DFA状态对应一个NFA状态集合初态是初态的ε闭包然后BFS/DFS扩散对每个符号做“move再closure”得到新集合若没见过就加入状态表并记录转移。这个集合就是DFA状态的“真名”打印报告时会用到。def subset_construction(nfa): dfa_sets [] # 每个DFA状态对应一个frozenset dfa_trans {} # (dfa_id, symbol) - dfa_id dfa_finals set() start_set frozenset(epsilon_closure(nfa, {nfa.start})) dfa_sets.append(start_set) if set(start_set) nfa.finals: dfa_finals.add(0) queue [0] while queue: cur queue.pop(0) for sym in nfa.alphabet: moved epsilon_closure(nfa, move(nfa, set(dfa_sets[cur]), sym)) if not moved: continue nxt frozenset(moved) if nxt in dfa_sets: target dfa_sets.index(nxt) else: dfa_sets.append(nxt) target len(dfa_sets) - 1 if moved nfa.finals: dfa_finals.add(target) queue.append(target) dfa_trans[(cur, sym)] target return dfa_sets, dfa_trans, dfa_finals这里最容易翻车的是dfa_sets里的元素类型。如果直接存setnxt in dfa_sets做相等比较时会对set取哈希Python立刻抛TypeError: unhashable type: set。所以要在“入库”的时候统一转成frozenset既保证可哈希又保证内容相等时index能找到。queue里存的是DFA状态编号也就是dfa_sets的下标用它做dict key比直接存frozenset更快也方便后面重命名。有个细节queue.append(target)不能漏。子集构造的扩散就靠这个队列漏了它会导致生成完初态就停住转移表缺一大半。这种错很隐蔽因为程序不报错只是结果少了状态排查时容易怀疑人生。2.4 状态输出与死状态标记实验报告里经常要求展示“DFA状态号对应哪些NFA状态”调试时更要能看见。所以输出函数我会写成def print_dfa(dfa_sets, dfa_trans, dfa_finals, alphabet, start0): print(DFA状态数:, len(dfa_sets)) for i, s in enumerate(dfa_sets): flag (终态) if i in dfa_finals else print(f状态{i}: {sorted(s)}{flag}) print(转移表:) for i in range(len(dfa_sets)): row [] for sym in alphabet: row.append(f{sym}-{dfa_trans.get((i, sym), -)}) print(f{i}: , .join(row))打印转移表时对缺失转移统一打-表示死状态。报告里手写推导用的是∅程序里打-两张图一对照语义是通的。另外打印状态子集一定要sorted(s)固定顺序否则set输出每次顺序都可能变截图和手算对不上老师会以为程序有随机性。3. DFA最小化划分细化算法的完整实现与参数选择3.1 等价状态的定义什么时候两个状态能合并DFA状态数越少词法分析器运行时查表的开销越低。最小化就是找出等价状态并合并。两个状态等价是指从它们出发、喂同样的字符串得到的接受结果完全一致——任何一个串都不能把两者区分开。反过来如果存在一个字符串从一个状态出发能到终态、从另一个出发不能那它们就必须分裂。划分细化算法从最粗的划分开始终态集合和非终态集合各成一组。为什么初始就这么分因为空串就能区分终态和非终态这两个集合里的状态不可能等价。分完初始组后反复迭代如果同组两个状态在某个符号下走去了不同的组说明这个符号把二者区分开了要按“转移目标组的组合”把组内状态再拆细。直到某轮循环组数不再增长划分就是最细的。这个算法也叫表格填充法的逆向版表格法先假设全部状态等价再逐步标记不等价对划分细化则是从最细的“终态vs非终态”开始不断切分。课设里两个都能用但划分细化代码更好写终止条件的证明也更直观。3.2 划分细化主循环按转移签名做分裂实现上每一轮对每个组内的状态算一个“签名”签名的每一项是该状态在某个符号下的目标组编号。签名相同的状态留在同一组签名不同的分裂开。def get_group_id(groups, target): if target is None: return -1 for i, group in enumerate(groups): if target in group: return i return -1 def minimize_dfa(state_count, dfa_trans, finals, alphabet): groups [] if finals: groups.append(set(finals)) non_finals set(range(state_count)) - set(finals) if non_finals: groups.append(non_finals) groups [g for g in groups if g] # 去掉空组 while True: new_groups [] for group in groups: split {} for state in group: sig tuple( get_group_id(groups, dfa_trans.get((state, sym))) for sym in alphabet ) split.setdefault(sig, set()).add(state) new_groups.extend(split.values()) if len(new_groups) len(groups): break groups new_groups id_map {} for new_id, group in enumerate(groups): for old_state in group: id_map[old_state] new_id new_trans {} for (state, sym), target in dfa_trans.items(): new_trans[(id_map[state], sym)] id_map[target] new_finals {id_map[f] for f in finals} return len(groups), new_trans, new_finalsget_group_id单独抽出来是有原因的如果写内层循环每次查组号都要遍历所有组整体复杂度会升到 O(n³)实验规模下虽然能跑但报告里写复杂度分析时不好看。另一个原因是它统一处理了“死状态”——某个状态在某个符号下没有转移dfa_trans.get返回None这里统一映射成-1。这样所有无转移的状态天然分到同一类不会因为None和-1的差异被误拆成两组。终止条件就是len(new_groups) len(groups)一轮跑完组数没变说明所有组内状态在任意符号下都走进了同一组不可再分。这里有个隐蔽的坑new_groups.extend(split.values())时如果某个组内所有状态在某个符号下都走死状态split里只有一个分组这没问题但split.values()里如果混入空set组数会被撑大导致死循环。所以前面groups [g for g in groups if g]这行过滤必须保留稳定可靠。3.3 预处理删除不可达状态与死状态归类子集构造产生的DFA状态未必都可从初态到达但最小化算法会把不可达状态也纳入分组最终状态数虚高和手算结果对不上。标准做法是先BFS扫一遍只保留从0号状态可达的状态def reachable_states(state_count, dfa_trans): seen {0} stack [0] while stack: s stack.pop() for (src, sym), target in dfa_trans.items(): if src s and target not in seen: seen.add(target) stack.append(target) return seen这里state_count是子集构造后DFA的状态数初态编号约定为0。遍历dfa_trans时用src s筛出当前状态的所有出边虽然效率一般但课设状态量级没问题胜在直观。筛完以后把不可达状态从状态表、转移表、终态集合里一并剔除再去做最小化结果才是干净的。死状态某些符号无转移的处理也在这个阶段完成。我见过有人专门建一个额外的“陷阱状态”补齐所有缺失转移再跑最小化最后再把陷阱状态删掉。这种做法标准教材爱写因为形式化证明方便但实验代码里纯属自找麻烦。直接用get_group_id里-1的映射方式死状态被统一归类最小化过程中它们自然合并输出时打-就行了不用真造一个状态。3.4 重编号与最小化后的转移表拼接minimize_dfa内部返回的id_map把旧DFA状态号映射到新组号但新组号的顺序取决于groups列表的排列顺序每次运行可能不稳定。我习惯在minimize_dfa返回前把组按“组内最小原状态号”排序这样重编号后0号初态、小号状态的分布更符合直觉报告截图也更整齐。实际跑通以后对比三份输出原NFA、子集构造的DFA、最小化后的DFA。最小化后的状态数应该小于等于转换后的状态数而且语言完全一致。这个“语言等价”不是肉眼看出来的需要用测试串实际跑具体验证脚本放到最后一章。最小化的历史经验是状态数压缩最多发生在含有大量不可达状态或对称结构的NFA上比如识别(a|b)*的NFA有三个状态转DFA直接合并成一个最小化环节反而无事可做这是正常现象。4. 从代码到实验报告ZZU实验的完整交付方案4.1 NFA输入文件格式五行五元组怎么读实验通常要求从文件读NFA定义我用的格式是“前四行固定元信息之后每行一条转移”A B C a b A C A a B A ε B B b C第一行是全部状态第二行是字母表不要把ε写进去第三行初态第四行终态之后每行一条“源状态 符号 目标状态”。读入时把相同源状态, 符号的多条转移合并到同一个set里代码可以这样写def read_nfa(path): lines [line.strip() for line in open(path, encodingutf-8) if line.strip()] states set(lines[0].split()) alphabet lines[1].split() start lines[2].strip() finals set(lines[3].split()) transitions {} for line in lines[4:]: src, sym, dst line.split() transitions.setdefault((src, sym), set()).add(dst) return states, alphabet, transitions, start, finalssym如果是ε程序自动当特殊符号处理不会进alphabet。曾经有个同学把ε写进了第二行字母表子集构造时对ε也调move结果DFA输出里多出“ε-…”这一列整张转移表全歪了。这个错误层级很低但一旦发生后面所有推导全是废的读文件时加一个断言能提前拦下assert ε not in alphabet, 字母表不能包含 ε4.2 main流程一条龙读入、转换、剪枝、最小化、打印main函数把前面所有模块串起来。为了报告里手算对照我一般把“转换后的DFA”和“最小化后的DFA”都打印一份中间再补一个“删除不可达状态后的重编号”步骤让每一步的输入输出都看得见def main(): states, alphabet, transitions, start, finals read_nfa(nfa.txt) nfa NFA(states, alphabet, transitions, start, finals) dfa_sets, dfa_trans, dfa_finals subset_construction(nfa) print( 子集构造得到的DFA ) print_dfa(dfa_sets, dfa_trans, dfa_finals, alphabet) state_count len(dfa_sets) reachable reachable_states(state_count, dfa_trans) mapping {old: new for new, old in enumerate(sorted(reachable))} trans_compact { (mapping[s], ch): mapping[t] for (s, ch), t in dfa_trans.items() if s in mapping and t in mapping } finals_compact {mapping[f] for f in dfa_finals if f in mapping} min_count, min_trans, min_finals minimize_dfa( len(mapping), trans_compact, finals_compact, alphabet ) print( 最小化后的DFA ) print_dfa(min_count, min_trans, min_finals, alphabet)enumerate(sorted(reachable))保证新编号按原编号升序排列不会把0号初态弄丢。if s in mapping and t in mapping这行把指向不可达状态的转移直接丢弃指向死状态的转移也就不存在了。输出时注意print_dfa接收的是状态数而不是dfa_sets因为最小化后没有原始状态集合可对应打印子集那一行需要留空或者只打编号别让程序抛错。4.3 实验报告结构算法描述、复杂度、结果截图ZZU这类课程实验报告一般有固定模板但核心章节不外乎这几块。问题描述里写清“给定NFA求等价最小DFA”数据结构说明里画一张NFA类的字段表把transitions的key格式写明白算法流程里放伪代码或流程图并给出复杂度分析。复杂度这块要写准确子集构造最坏情况下DFA状态数是指数级即 O(2ⁿ)n为NFA状态数每个状态对每个字符做一次move和一次closure闭包最坏O(n)所以整体最坏 O(2ⁿ × m × n)m为字母表大小。最小化按我这里实现的划分细化每轮遍历所有状态×字母表组数最多n轮所以 O(k × n²)k为字母表大小。这个复杂度分析和代码实现是对得上的写进报告比直接抄课本的O(n log n)可信得多。还建议在报告里保留“关键函数对照表”像epsilon_closure、move、subset_construction、minimize_dfa每个都配两三句话的算法要点。截图要包含NFA输入文件、转换后DFA转移表、最小化后DFA转移表。截图前先跑一遍代码确认所有状态子集打印都用了sorted()顺序稳定。4.4 四个可手算的测试用例从单状态到ε环测试用例的设计决定了报告的可信度。下面这组用例从小到大覆盖了边界情况每一行都能手算验证数字完全确定用例NFA特征子集构造后DFA状态数最小化后状态数这个用例在验证什么1a*单状态自环11自环与move的基本路径2a*b*含ε转移22ε闭包与“初态集合含终态”3(ab)*含ε环114ab两个等价终态32用例3最容易触发边界bug初态集合{0,1,2}本身就是终态集合初始划分只有一个组如果minimize_dfa里对“非终态集合为空”的情况没做防御要么死循环要么直接崩。用例4的设计意图是“1、2两个终态都没有出边它们等价”最小化后合并成一个终态状态数从3降到2这是整个实验里唯一能直观展示“最小化在起作用”的地方报告中要重点截图。5. 避坑NFA转DFA最小化最容易翻车的5个细节5.1 set当dict key一运行就TypeError现象程序刚启动子集构造里执行nxt in dfa_sets时抛TypeError: unhashable type: set。原因dfa_sets列表里直接append了set而list.index和in判断都需要对元素做哈希Python的set可变、不可哈希。解决所有要存进dfa_sets的集合统一转frozenset转换点放在nxt frozenset(moved)这一行就够其他位置的set照常用。这个坑几乎是第一次写子集构造必踩的我当年也在同一行卡了半小时。5.2 move和closure写反DFA状态数对不上现象生成的DFA缺少部分转移或者状态数比手算的明显多怎么调都对不上。原因子集构造的标准步骤是“先move取直接目标再对目标集合做closure”。写成“先closure再move”等于把ε边当成了普通输入边ε路径跨过了本不该跨过的状态闭包被无限放大。解决把流程固定成epsilon_closure(move(nfa, T, symbol))这一条式子最好写成独立函数def next_dfa_state(nfa, current_set, symbol): return epsilon_closure(nfa, move(nfa, current_set, symbol))给这个函数起个一眼能看懂的名字以后每次调用都不容易写反。5.3 划分细化死循环空组害人不浅现象minimize_dfa里的while True迟迟不退加print调试后看到new_groups数量一直在涨。原因分裂时产生的空set也被append进了new_groups。空组不包含任何状态但它会让组数虚增终止条件len(new_groups) len(groups)永远不成立。解决每次构造new_groups后立刻过滤空组同时初始构建groups时也把空集合剔掉。这行过滤代码看着不起眼少了它程序就是个死循环属于典型的“缺一行翻车”。5.4 死状态编号不统一最小化结果乱跳现象最小化以后同一个DFA状态对某个符号的转移目标一会儿是2、一会儿是3不同运行结果还不一样。原因get_group_id对“无转移”的情况返回了NoneNone混进签名tuple里和-1不相等导致两个语义上都是死状态的目标被分到不同组状态编号随字典遍历顺序漂移。解决get_group_id里对None统一返回-1。签名tuple里的每一个元素只可能是组号或-1类型统一、语义统一分组结果就稳定了。写代码时给dfa_trans.get的返回值一个明确约定——查不到就是None映射成-1一以贯之。5.5 手算推导和程序输出编号对不上现象报告里手写的DFA状态编号和程序打印出来的对不上老师核对时一眼看出问题。原因程序按BFS扩展顺序给DFA状态编号也就是dfa_sets的下标手算时一般按字母顺序或自己的习惯编号两种编号天然不一致。解决打印时输出“状态i {NFA状态子集}”的对照表比如状态0 {A, B, C}手算推导也按这个子集写。编号不同没关系子集一致就说明算法结果是对的。这个对照表既是调试工具也是实验报告的必备内容。6. 验证与进阶用对拍脚本确认最小化前后自动机等价6.1 simulate函数让DFA真正跑起来最小化做完最怕的就是“看起来对实际语言变了”。肉眼检查转移表只能发现低级错误真正靠谱的是写一个模拟器让最小化前后的两个DFA跑同一批字符串逐条比对接受结果def simulate(trans, start, finals, word): state start for ch in word: nxt trans.get((state, ch)) if nxt is None: return False state nxt return state in finalstrans是(状态, 符号) - 状态的字典查不到转移说明走进死路直接判拒。对于最小化后的DFA因为死状态已经被丢掉get返回None的语义就是“拒绝”。这个函数只有十行却能验证整条转换链路的正确性。6.2 随机对拍与枚举验证有了simulate接着写对拍随机生成几千条只含字母表的字符串分别在两个DFA上跑结果不一致就报警。import random def cross_check(trans1, start1, finals1, trans2, start2, finals2, n5000): alphabet [a, b] for _ in range(n): length random.randint(0, 12) word .join(random.choice(alphabet) for _ in range(length)) r1 simulate(trans1, start1, finals1, word) r2 simulate(trans2, start2, finals2, word) if r1 ! r2: print(不一致:, word, r1, r2) return False return True随机串有盲区严格做法是枚举所有长度不超过阈值的串比如product(alphabet, repeatlength)对length从0到12全枚举。有限自动机一旦不等价最短反例串不会超过两状态数的乘积课设状态数几十个的情况下枚举到12已经非常稳。我第一次交实验时没做这步结果最小化后的DFA丢掉了一条关键转移语言从“以abb结尾”变成“包含abb”老师拿个反例串当场就点出来了。后来凡是做跟自动机相关的实验或工具我都先写对拍脚本再写报告这已经是改不掉的习惯了。这个验证脚本顺手留下来以后做词法分析器、正则引擎都能复用。希望帮到你。本文还有配套的精品资源点击获取