1(0|1)*101正规式转DFA：从NFA到最小化DFA的完整手算与Python实现

简介一份面向编译原理学习者的正规式与有限自动机专题练习文档聚焦DFA构造、确定化与最小化等核心考点。内容围绕四个典型习题展开为正规式1(0|1)*101构造相应DFA、完成对图4.16的确定化、对图4.17的最小化以及设计接收“每个1后紧跟0”的DFA并写出对应正规式与正规文法。文档附有详细参考答案包含状态转移表、重新命名过程、子集法构造NFA并确定化的步骤以及最小化时分划等价类的完整推导适合正在复习编译原理课程、备考研究生入学考试或需要强化自动机理论的读者对照练习与查漏补缺。资源包共1个doc文件约63KB内容精炼紧凑便于直接查阅与打印。已有9900余人学习使用是一份经过大量读者验证的经典习题解析资料。1. 构造1(0|1)*101相应的DFA先搞清楚这个正规式匹配什么在编译原理的作业里“构造正规式1(0|1)*101相应的DFA”是一道很经典的题但也是翻车率很高的一道题。很多人第一眼会把1(0|1)*101理解成“字符串里包含101就通过”然后画出完全错误的状态图。实际上这个正规式的含义是整个字符串必须以1开头并且必须以101结尾中间的(0|1)*可以吃掉任意多个0或1甚至可以为空。也就是说1101可以匹配101不能匹配1001也不能匹配。这道题的难点不在正规式本身有多复杂而在于从正规式到NFA、再从NFA到DFA的每一步都藏着容易忽略的细节。这篇文章会从语法树拆解开始手动走完Thompson构造、子集构造法、DFA最小化三步最后给出一份可以直接抄作业的Python实现。适合正在学《编译原理》自动机部分的学生也适合需要手工设计词法分析器状态表的从业者。读完你不仅能做出这一道题还能把整套“正规式转DFA”的流程迁移到其他表达式上。2. 从正规式到NFA先把1(0|1)*101拆成状态图这个环节的目标是把1(0|1)*101变成一个带ε-转移的NFA。NFA允许同一个状态对同一个输入有多个转移也允许不消费字符就移动所以它比DFA更容易从正规式直接构造出来。我们后面再通过子集构造法把它转成DFA。2.1 拆语法树1、(0|1)*、101三段怎么连接先按运算符优先级把正规式拆开。1(0|1)*101完整的括号形式是1 ((0|1)*) (1 0 1)也就是三部分顺序连接第一部分是单个字符1要求字符串的第一个字符必须是1。第二部分是(0|1)*表示任意多个0或1组成的串可以是空串。第三部分是101注意它是三个字符连续排列不是“包含101”这种整体概念。这个拆法决定了后面NFA的状态划分。1和101是固定字符各自需要至少一个状态(0|1)*是一个循环结构需要允许在任意时候跳出循环进入101的匹配。如果在拆解阶段就理解错了后面画出来的状态图一定错。为了验证理解先手工试几个串1101由1 空 101构成匹配11101由1 1 101构成匹配101总长度只有3缺少中间段不匹配00101开头不是1不匹配。记住这几个例子后面所有步骤都要以它们为准。2.2 用Thompson构造法画出NFA的每一步提一个常见的做法Thompson构造法为每个正规式片段分配一个开始状态和一个接受状态片段之间用ε-转移连接。这样构造出来的NFA状态多但结构清晰而且后面子集构造法能自动消除冗余。针对1(0|1)*101我一般会先画一个直观版NFA状态按“读到了正规式的哪一部分”来命名NFA状态含义输入0输入1ε转移S0起始状态还没读任何字符无{S1}无S1已读固定开头1无无{S2}S2正在读(01)*可以循环{S2}{S2}S3准备匹配后缀101的第一个字符无{S4}无S4已匹配后缀的1{S5}无无S5已匹配后缀的10无{S6}无S6已匹配完整的101接受无无无注意S2的ε转移到S3这是整个NFA的关键点。它表示在(0|1)*这个循环里的任何一个时刻NFA都可以“不消费字符”地跳出去开始匹配后缀101。如果后续字符是1、0、1就走到S6接受如果不是这条路径就自然断掉不影响其他路径继续在S2绕圈。用这个NFA走一下匹配1101的路径S0读1进入S1S1通过ε进入S2S2再通过ε进入S3S3读1进入S4S4读0进入S5S5读1进入S6接受。走11101时S2里多绕一圈吃掉中间的1后面的路径一样。这样理解起来比硬记转移表直观得多。2.3 为什么这里必须用ε-转移这个正规式的不确定性来自一个真实的选择读完开头的1之后下一个字符到底算(0|1)*的一部分还是算后缀101的第一个字符在“11101”里中间那个1是循环部分而最后的101是后缀在“1101”里循环部分为空第二个字符1直接就是后缀开头。同一个位置可以是两种身份的字符NFA必须同时保留两种可能。ε-转移就是用来表达这种“并行选择”的。不写ε直接在S2上增加“读1到S4”的转移也能实现部分效果但会对(0|1)*的构造造成混乱尤其是当正规式变成更复杂的嵌套结构时。Thompson构造法统一使用ε虽然状态多但每一块的接口是标准的后面做子集构造时不容易漏掉路径。3. 用子集构造法把NFA转成DFA逐步计算与转移表子集构造法的核心是把NFA在某个输入符号后的所有可能状态打包成一个集合这个集合就是DFA的一个状态。因为DFA不允许不确定性所以它必须一次性记住NFA的“所有当前位置”。3.1 ε-闭包是第一步初始状态不是S0而是S0的闭包在子集构造法里每次得到一个新的NFA状态集合后第一件事是求它的ε-闭包。ε-闭包的定义是从集合中的每个状态出发沿着任意条ε-转移能到达的所有状态加上状态本身。这个例子的起始状态S0没有ε转移所以ε-closure({S0})就是{S0}看起来很简单。但千万别因为简单就跳过这一步。如果正规式以(0|1)*开头初始闭包会包含很多状态漏掉一个就会让整个DFA错位。我见过太多人在这一步图省事直接在纸上写“初态是S0”结果后续转移表算得越认真错得越远。计算闭包的工具是用栈或队列做传递闭包。从初始状态S0出发把所有能通过ε到达的状态都加进来由于S2有ε到S3S1有ε到S2所以闭包往往是多层嵌套的。这个例子恰好初态简单但S1的闭包就要包含S2和S3。3.2 逐个算出DFA的7个状态现在开始正式推演。先给每个DFA状态取一个字母名避免后面表格写成长串的NFA状态集合。初始DFA状态AA ε-closure({S0}) {S0}从A读0S0没有0转移得到空集记作DEAD。从A读1得到S1再对{S1}求ε-闭包B ε-closure({S1}) {S1, S2, S3}注意S1的ε到S2S2的ε到S3所以闭包一次传递下来成了三个状态。B是DFA中真正开始有动作的状态。接着从B出发算。B读0时只有S2能通过0到S2所以C ε-closure({S2}) {S2, S3}B读1时S2通过1到S2S3通过1到S4所以D ε-closure({S2, S4}) {S2, S3, S4}然后算C。C读0还是S2到S2闭包仍是{S2,S3}所以C读0回C。C读1S2到S2S3到S4所以得到D。D读0时S2到S2S4到S5闭包得到E {S2, S3, S5}D读1时S2到S2S3到S4S4没有1转移所以回到D。E读0时S2到S2S5没有0转移闭包回到C。E读1时S2到S2S3到S4S5到S6闭包得到F {S2, S3, S4, S6}从F出发F读0S2到S2S4到S5得到EF读1S2到S2S3到S4得到D。至此所有状态都闭合了。完整的DFA转移表如下DFA状态NFA状态集合输入0输入1是否接受A{S0}DEADB否B{S1,S2,S3}CD否C{S2,S3}CD否D{S2,S3,S4}ED否E{S2,S3,S5}CF否F{S2,S3,S4,S6}ED是DEAD空集DEADDEAD否这个表就是子集构造法的直接产物。可以看到接受状态只有F因为它包含NFA的接受状态S6。走一遍“1101”A读1到BB读1到DD读0到EE读1到F接受和手工分析一致。3.3 用Python验证子集构造法的结果手工算完一定要用代码验证尤其是初学阶段纸上的闭包特别容易漏。下面这段Python实现可以直接跑输入NFA状态转移表和ε转移表输出DFA状态和转移关系。# NFA转移表trans[state][symbol] 目标状态集合 trans { 0: {1: {1}}, 1: {}, 2: {0: {2}, 1: {2}}, 3: {1: {4}}, 4: {0: {5}}, 5: {1: {6}}, 6: {}, } # ε转移表eps[state] 通过ε直接到达的状态集合 eps { 1: {2}, 2: {3}, } def eps_closure(states, eps): stack list(states) cl set(states) while stack: s stack.pop() for t in eps.get(s, []): if t not in cl: cl.add(t) stack.append(t) return cl def move(states, symbol, trans): nxt set() for s in states: nxt | trans.get(s, {}).get(symbol, set()) return nxt def subset_construct(trans, eps, alphabet, start, accept): start_set frozenset(eps_closure({start}, eps)) dfa_states [start_set] worklist [start_set] dfa_trans {} while worklist: cur worklist.pop() for symbol in alphabet: nxt frozenset(eps_closure(move(cur, symbol, trans), eps)) if nxt not in dfa_states: dfa_states.append(nxt) worklist.append(nxt) dfa_trans[(cur, symbol)] nxt accepting [s for s in dfa_states if accept in s] return dfa_states, dfa_trans, accepting states, tbl, acc subset_construct(trans, eps, [0, 1], 0, 6) for i, s in enumerate(states): row [states.index(tbl[(s, ch)]) for ch in [0, 1]] print(f状态{i}: {sorted(s)} 读0-{row[0]} 读1-{row[1]} 接受{s in acc})这段代码里eps_closure用栈实现传递闭包保证S1能一路闭包到S3。move只做一步输入转移不处理ε所以每次构造新状态后必须立即再求一次闭包。这是整个子集构造法的核心顺序move一次closure一次。如果代码输出的状态编号和手算顺序不同不用慌只要转移关系一致、接受状态正确即可顺序取决于栈的弹出顺序。4. DFA最小化把7个状态合并成6个去掉等价状态子集构造法得到的DFA通常不是最小的里面有些状态行为完全相同可以合并。真正投入词法分析器之前最小化这步值得做因为状态越少转移表越小运行时缓存命中率也越高。这个例子只合并了一个状态但流程是完整的。4.1 为什么要做最小化等价状态的判据两个DFA状态等价意味着从它们出发对任意输入串都会得到相同的接受/拒绝结果。判断方法是从接受状态和非接受状态的划分开始逐步细分组内迁入目标所属的组。这个算法叫划分细化也叫Hopcroft算法的简化版。在这个DFA里接受状态只有F其他状态都不接受所以初始划分一定是{F} 和 {A,B,C,D,E,DEAD}两组。这一步看似简单但很多人一开始把接受状态和非接受状态混在一起后面的迭代就全乱。记住接受性不同的状态永远不可能等价。4.2 划分法三轮迭代逐步把状态拆开初始划分P0P0 {F} {A, B, C, D, E, DEAD}第一次迭代看每个非接受状态在输入0和输入1时分别落到哪一组。关键差异在EE读1进入F接受组而其他非接受状态读1都落在非接受组。因此E必须单独拆出来P1 {F} {E} {A, B, C, D, DEAD}第二次迭代再看{A,B,C,D,DEAD}这一组。D读0进入E而E已经不在这个组里所以D和别人不一样拆出来P2 {F} {E} {D} {A, B, C, DEAD}第三次迭代观察{A,B,C,DEAD}。A读1到BB读1到DC读1到DDEAD读1到DEAD。B和C的读1目标都是D当前单独组而A读1到B还在本组DEAD读1到DEAD还在本组所以B和C可以抱团A和DEAD不能和他们混在一起P3 {F} {E} {D} {B, C} {A} {DEAD}再检查{B,C}B读0到C读1到DC读0到C读1到D行为完全一致不再分裂。{A}和{DEAD}内部都只有一个状态自然稳定。最终划分就是6组比原来的7个状态少了一个。4.3 最小化后的DFA长什么样把{B,C}合并成一个新状态G得到最小化DFA状态含义输入0输入1接受A还没读字符等开头1DEADG否G已读开头1且在(01)*中循环或准备进入后缀GDD已读后缀101中的第一个1ED否E已读后缀的10GF否F已接受完整匹配ED是DEAD死状态DEADDEAD否这个DFA比原始表少一个状态但接受的语言完全一致。G的含义是“既能继续循环又能随时开始匹配后缀”它把原先B和C这两个表现相同的状态收敛成了一个。以后写词法分析器时状态名可以直接用这里的字母转移表就是一份标准的驱动表。5. 构造1(0|1)*101的DFA时最容易踩的5个坑这一节把从正规式到DFA全过程中最常见的坑集中列出来。每条都是“现象 → 原因 → 解决”的结构照着排查能省很多时间。5.1 把“1(0|1)*101”理解成“包含101”现象构造出来的DFA能接受0101、00101这类不以1开头的串。 原因把正规式看成了(0|1)*101忽略了最前面的固定1或者把连接关系理解成“串中某个位置出现101即可”。 解决第一步就拆语法树明确是三段连接1、(0|1)*、101。状态S1专门用来消费开头的1不存在从起始状态直接进入循环的可能。5.2 子集构造时漏算ε-闭包的传递性现象手算时把ε-closure({S1})写成{S1,S2}少了S3导致后续所有状态都不对。 原因漏掉了“闭包的闭包”这种传递关系。S1到S2S2又到S3闭包必须一直传递到没有新状态为止。 解决用栈或队列实现传递闭包先把种子状态入栈每弹出一个状态就加入它的ε目标直到栈空。这个过程宁可多算几轮也不要只算一层。5.3 只算move不算closure或者顺序反了现象从某个DFA状态读入字符后直接把move结果当作新状态比如把{S2}当成C而没有扩展成{S2,S3}。 原因move返回的是NFA消耗一个字符后到达的状态但NFA随后还能不消耗字符继续移动必须再求一次ε-闭包。 解决记住固定顺序先move再closure。任何一次生成新DFA状态都要完整做这两步。这也是3.3代码里subset_construct的核心模式。5.4 最小化时初始划分把接受态和非接受态混在一起现象最小化结果不稳定迭代好几轮还在分裂或者合并了不该合并的状态。 原因初始划分把F和其他状态放进了同一个组等价性判据从第一步就错了。 解决强制先分成两组接受状态一组非接受状态一组。之后再按转移目标所在组分裂。这个原则对所有DFA最小化都适用不是这一道题的特例。5.5 不画死状态导致转移表有空洞现象转移表里某个状态缺了某个输入的转移例如从A读0没有定义实际模拟时程序直接报错或返回错误结果。 原因DFA要求转移函数是完整的每个状态对每个输入都必须有下一个状态。子集构造法产生的空集本身就是一个状态。 解决把空集命名为DEAD所有缺失的转移都显式指向DEAD。注意DEAD自己也必须有到DEAD的转移否则它也会变成“空洞”。最小化后也要重新检查一遍确保状态表是一张完整的方阵。6. 把这个DFA做成可用的词法分析器模拟器与验证技巧最后一步把最小化后的DFA落地成能跑的代码。这一节给出一个可直接复制的DFA模拟器以及一套随机对比验证方法避免手工状态表写错。6.1 用Python直接模拟最小化DFA# 最小化后的DFA转移表 transition { A: {0: DEAD, 1: G}, G: {0: G, 1: D}, D: {0: E, 1: D}, E: {0: G, 1: F}, F: {0: E, 1: D}, DEAD: {0: DEAD, 1: DEAD}, } start_state A accept_states {F} def match_dfa(s): state start_state for ch in s: if ch not in (0, 1): return False state transition[state][ch] if state DEAD: return False return state in accept_states这个模拟器的逻辑很简单从A开始逐个字符查表跳转一旦进入DEAD直接判失败最后只要停在F就接受。需要改匹配其他正规式时只需要替换transition表、起始状态和接受状态集合模拟函数本身不用动。代码里对非0/1字符提前返回False是因为词法分析器通常还要处理其他符号这里是先把输入限制在字母表内。6.2 用随机测试反向验证DFA手算的转移表再小心也难免出错最有效的后悔药是拿随机串和标准正则引擎对拍。Python的re模块足够用来验证这个正规式。import random import re pattern re.compile(r1(0|1)*101) def random_binary_string(length): return .join(random.choice(01) for _ in range(length)) for _ in range(10000): s random_binary_string(random.randint(0, 12)) expected pattern.fullmatch(s) is not None actual match_dfa(s) if expected ! actual: print(f不一致: {s!r} 正则期望{expected} DFA结果{actual}) break else: print(10000个随机串全部一致)跑出来的不一致几乎都是因为DFA写错很少是正则引擎的问题。如果你改动了状态表记得把随机串长度上限提高一些字符串越长越容易覆盖深层状态组合。还可以在固定串测试里特别带上边界用例1101必须接受101必须拒绝11101必须接受00101必须拒绝。6.3 从状态表到词法分析器表驱动与状态压缩模拟器是词法分析器的最小原型。实际生产里会把transition表压成二维数组行是DFA状态编号列是输入字符编号值直接存下一行编号。这样可以去掉字典查找开销配合状态机和输入缓冲就是标准的表驱动词法分析器。更进一步可以在最小化时记录每个状态对应的“接受的Token类型”让一个DFA同时识别多个关键字而不是每个正规式单独建一台DFA。我个人的习惯是做完一版DFA先花十分钟写随机对拍脚本再拿边界串手跑一遍。这个习惯在写过几次复杂的正规式之后帮我避免了至少三处状态表笔误。希望帮到你。本文还有配套的精品资源点击获取