简介文档围绕《构造正规式1(0|1)*101相应的DFA》这道编译原理/形式语言经典习题系统整理了正规式转DFA、图4.16确定化、图4.17最小化以及构造接收“每个1都有0直接跟在右边”的DFA并写出正规式/正规文法等内容适合计算机专业学习形式语言与自动机、备考期末或考研复习的读者使用。包内仅含1个doc文件约63KB内容精炼包含状态转换表、子集构造、重新命名、最小化分划步骤及DFA状态图等关键细节可直接对照讲义图4.16、图4.17进行练习与校验。该资源已吸引9963人次学习说明其在高频考点上具有较高参考价值。通过这份资料读者可以完整掌握从正规式构造DFA的方法、NFA确定化与DFA最小化的一般流程并理解“每个1后紧跟0”这类约束语言的正规式设计思路对巩固自动机理论基础、提升解题速度有明显帮助。1. 正规式1(0|1)*101不是一道作业题它在教你理解编译器的词法分析器很多人第一次见到“构造正规式1(0|1)*101相应的DFA”是在编译原理课的课后习题里。别看它只是一个小式子它描述的是所有以1开头、中间任意0或1、最后以101结尾的二进制串比如1101、10101、111101都归它管0101、11011却不行。标题里“构造相应的DFA”这句话翻译成人话就是把这段语言描述变成一台确定有限自动机让它每读一个字符都能唯一决定下一步去哪不用猜、不用回溯。这个能力正是编译器里词法分析器的地基也是正则表达式引擎发生疑难性能问题时最后必须手算的那层东西。本文适合正在啃编译原理的学生、准备面试的开发者以及想彻底搞懂正则引擎底层的工程师。2. 从正规式到NFA用Thompson构造法把语言描述拆成机械规则2.1 为什么先绕道NFA而不是直接画DFA很多人的第一反应是直接对着1(0|1)101画DFA既然开头是1画一条“1”边中间是(0|1)画个自环最后是101画三个状态。听起来很顺但真正动手时会发现这个“中间任意0或1”和“最后以101结尾”之间存在交集——(0|1)*里的0或1可能会和最后的101重叠。比如输入1101时中间的星号到底匹配了几个字符、结尾的101从哪里算起直接画图很容易画错边界。我辅导过的人里十个有六个第一次直接画DFA都会翻车要么漏掉某个合法串要么多接受了不该接受的串。教材里给出的标准路线是先构造NFA再用子集构造法确定化成DFA。这条路看起来绕但每一步都是机械的不会依赖灵感和经验。正规式转NFA是纯语法驱动正规式里每个字符、每个运算符都有对应的图模板你只要照着模板套结果一定正确NFA转DFA又有一套固定算法不会产生主观判断。所以“先NFA后DFA”不是为了多学一个概念而是为了让“构造DFA”从艺术变成流水线。另外一个容易被新手忽略的理由是直接画DFA时人的注意力会集中在“怎么让状态最少”上结果写出一个看起来漂亮但有缺陷的机器。而NFA允许同一个状态对同一个字符有多条出路甚至允许ε空转移构造时的思维负担小得多。等确定化成DFA状态多几个没关系正确性有保障。2.2 Thompson构造法的五个原子操作Thompson构造法把正规式拆成五种基本结构单个字符、连接、选择、重复和括号。括号不产生新的NFA结构只决定运算顺序。核心规则如下表正规式片段NFA结构关键点单个字符 a新增两个状态起态经 a 到止态原子单元r1 r2 连接r1 的止态经 ε 连到 r2 的起态串接原子单元r1 | r2 选择新增起态分别 ε 到 r1、r2 起点r1、r2 止态 ε 到新增止态两侧是并行的r* 重复新增起止态起态 ε 到止态形成空跳同时 ε 到 r 的起点r 的止态 ε 回 r 的起点及止态回环负责多次或零次括号本身不建NFA它只是告诉你怎么分组。这套构造法有个讨喜的特点每一条规则只关心局部不关心整个正规式的语义所以不容易出错。从工程习惯来讲我常建议把正规式先按运算优先级拆成语法树再自底向上套模板而不是在脑子里一次性画完。这样哪怕正规式长到十几个运算符也能保证每个模板的边数和状态数可控。2.3 手拆1(0|1)*101完整NFA状态表与转移边先按优先级拆解。正规式1(0|1)101中括号优先级最高星号次之连接再次选择最低。因此它等价于1 · (0|1)· 1 · 0 · 1。拆成三段起始的1、(0|1)*、结尾的101。把它们首尾相接就是完整的NFA。为了不引入无谓的ε状态我在套用模板时对(0|1)*做了等价化简选择结构的两个分支0和1直接以字符转移边挂在入口状态上而不是再展开成各自的状态对。这种化简不改变NFA接受的语言但能让状态数从十几个压到11个。如果你不想化简按模板展开后得到的DFA是完全一样的。下面是本次推导使用的NFA状态0为起始状态10为接受源状态转移字符目标状态0111ε22ε32ε43ε23184054ε65ε36177ε38099110这条转移表的脉络很清晰状态0到1是开头那个“1”状态2是(0|1)*的入口状态3是出口。2到3之间的ε让星号可以直接跳过实现“零次重复”3再ε回2形成循环实现“多次重复”。状态4进入0或1分支的选择结构沿0边到5然后ε回3表示选了0沿ε到6再读1到7然后ε回3表示选了1。从3再往前走1、0、1就是结尾的101部分。提示这里最容易看晕的是3到2的ε边。它和2到3的ε边构成了一对双向ε边这正是星号“可以再来一次”的语义。缺少任何一条星号都会退化成“最多一次”。这个NFA的状态数有11个边数13条看起来比最终DFA还要多但它的结构完全跟着正规式走画图时几乎不需要思考。1到2之间的ε是1段的止态接到星号入口3到8之间的1是星号出口接到结尾101的起点。整体串起来之后NFA的转移关系就全部确定了。3. 从NFA到DFA子集构造法的逐步推导与状态表3.1 ε闭包和move集合确定化计算的两个工具子集构造法的思想是NFA的“同一状态多出路”本质上是一种猜测DFA的每个状态是NFA状态的一个子集把可能的去向全部收集起来就消除了猜测。两个工具缺一不可ε闭包从某个NFA状态集合出发只沿着ε边能到达的所有状态加上出发点自己。因为ε边不需要消耗输入字符所以闭包里的状态在“读下一个字符前”都是同时活跃的。move集合从某个NFA状态集合出发读入一个字符后能到达的所有目标状态不闭包。move计算完之后还要对这个目标集合再求一次ε闭包才算完整走完一步。先算出本例NFA每个关键状态的ε闭包后面推导要用状态ε闭包0{0}1{1, 2, 3, 4, 6}2{2, 3, 4, 6}3{2, 3, 4, 6}4{4, 6}5{5, 3, 2, 4, 6}6{6}7{7, 3, 2, 4, 6}8{8}9{9}10{10}这个闭包表怎么核对从1出发1经ε到22经ε到3和44经ε到6所以是{1,2,3,4,6}。从5出发5经ε到33经ε到22经ε到44经ε到6所以是{5,3,2,4,6}。我建议做闭包时用栈每扩展出一个新状态就压栈直到栈空这样不会漏。3.2 逐状态推导从起始闭包到全部DFA状态DFA的起始状态是NFA起始状态的ε闭包。然后每发现一个新集合就把它当作一个新的DFA状态继续计算它在0和1下的转移。整个过程如下。A0 ε-closure({0}) {0}不含接受状态10所以A0非接受。A0读0move({0}, 0)为空集没有NFA状态在0下从0出发。按DFA的定义这里必须指向死状态t。A0读1move({0}, 1) {1}闭包后B {1, 2, 3, 4, 6}非接受。B {1, 2, 3, 4, 6}B读0只有4有0出边到5move {5}闭包后C {5, 3, 2, 4, 6}非接受。B读13有1出边到86有1出边到7move {7, 8}闭包后D {7, 3, 2, 4, 6, 8}非接受。C {5, 3, 2, 4, 6}C读04有0出边到5move {5}闭包后仍是C。C读0是自环。C读16到73到8move {7, 8}闭包后仍是D。D {7, 3, 2, 4, 6, 8}D读04到58到9move {5, 9}闭包后E {5, 3, 2, 4, 6, 9}非接受。D读16到73到8move {7, 8}闭包后仍是D。D读1是自环。E {5, 3, 2, 4, 6, 9}E读04到5move {5}闭包后回到C。E读16到73到89到10move {7, 8, 10}闭包后F {7, 3, 2, 4, 6, 8, 10}。F包含NFA接受状态10所以F是DFA的接受状态。F {7, 3, 2, 4, 6, 8, 10}F读04到58到9move {5, 9}闭包后回到E。F读16到73到8move {7, 8}闭包后回到D。到这里没有新状态出现了。把推导结果整理成完整的转移表DFA状态输入0输入1是否接受A0tB否BCD否CCD否DED否ECF否FED是ttt否这就是可以从NFA直接得到的、未经化简的DFA。注意F读入1后回到D而不是停在自己或死状态。这说明F虽然是接受状态但读入后续字符后仍可能继续进入其他状态如果最终停在D或E则整个串被拒绝。这种“接受后再继续走”的行为正是词法分析器做最长匹配时需要的。3.3 补全死状态让DFA对任意输入都有定义严格意义上的DFA要求转移函数是全函数每个状态对字母表中每个字符都有且仅有一个转移。上面表里的t就是死状态陷阱状态专门接收那些“不该出现的输入”。比如输入0101以0开头A0读0就直接进t之后无论读什么都留在t最后停在非接受状态串被拒绝。很多教材画DFA时省略死状态因为“反正走不到”但工程实现里省略不得。你写一个词法分析器输入串可不会保证以合法前缀开头没有死状态就意味着状态机遇到第一个非法字符后整个程序不知道往哪走轻则空指针重则静默接受非法串。补全死状态的成本极低给t加两条自环。但收益是在代码里永远不需要判断“转移是否为空”。注意死状态必须是非接受状态。如果在化简或编码时不慎把t标成接受那任何非法输入都会被接受这是最隐蔽的错误之一。4. 验证DFA状态化简、测试串设计与走查4.1 用划分法最小化DFA从7个状态找等价类未经化简的DFA有7个状态A0、B、C、D、E、F、t。并不是每个状态都不可替代。划分法Moore算法的思路是先把状态按“是否接受”分成两块然后反复检查每个状态在0和1下的转移目标是否落在同一块里不在同一块的就从当前块里拆出去。初始划分非接受块N {A0, B, C, D, E, t}接受块A {F}。第一轮从块内区分每个状态的行为A0读0到t读1到B都在块N。B读0到C读1到D都在块N。C读0到C读1到D都在块N。D读0到E读1到D都在块N。E读0到C读1到F其中F在接受块与其他人行为不同E必须单独拆出。t读0到t读1到t都在块N。于是划分变为{A0, B, C, D, t}、{E}、{F}。第二轮再检查{A0, B, C, D, t}A0读0到t读1到B都落在{ A0, B, C, D, t }块内。B读0到C读1到D都落在同一块内。C与B行为一致。D读0到EE已经是独立块所以D与B、C的行为不同D要拆出去。t读0到t读1到t都在块内与A0暂时一致。划分变为{A0, B, C, t}、{D}、{E}、{F}。第三轮再看{A0, B, C, t}A0读0到t读1到B其中t属于{A0,B,C,t}块B也属于同一块。B读0到C读1到DD已经是独立块所以B与A0不同。C与B一致。t读0到t读1到t都在{A0,B,C,t}块内与A0一致。于是把A0和t也拆开。最终划分为{A0}、{B,C}、{D}、{E}、{F}、{t}。B和C真的等价它们读0都到C合并后的同一状态读1都到D从它们出发对任意输入串的行为完全一致没有理由保留两个状态。4.2 最小DFA的转移表与实测走查对最小化后的状态重新命名得到6状态DFA新状态对应旧状态输入0输入1是否接受S1A0S6S2否S2{B,C}S2S3否S3DS4S3否S4ES2S5否S5FS4S3是S6tS6S6否手工走查几个关键串验证这个表和正规式的语言是否一致“1101”S1读1到S2读1到S3读0到S4读1到S5停在接受态接受。它对应正规式中的1 空串 101。“10101”S1读1到S2读0到S2读1到S3读0到S4读1到S5接受。这对应1 0 101星号部分匹配了一个0。“11101”S1读1到S2读1到S3读1到S3读0到S4读1到S5接受。这对应1 1 101。“0101”S1读0直接到S6之后全在死状态拒绝。这符合“必须以1开头”的约束。“101”S1读1到S2读0到S2读1到S3停在非接受态S3拒绝。注意这个串不是正规式的合法串因为正规式要求结尾必须是101而完整串最少需要4位先写开头的1再接结尾的101。“11011”S1读1到S2读1到S3读0到S4读1到S5此时已经进入接受状态再读第五个字符1S5读1到S3最终停在非接受态拒绝。这个例子很有价值它说明“进入接受状态后继续读入”不会让DFA失效而是会继续计算最终是否停在接受态。4.3 设计一组有区分度的测试串给正规式构造DFA时测试串不能只挑几个“看起来对”的。我是这样设计的覆盖“开头必须是1”0101必须拒绝10101必须接受。专门测起始边。覆盖“长度下限”1013位拒绝11014位接受。正规式的最小串是1101不是101这是最容易记错的地方。覆盖“星号多次”11101接受。星号部分匹配了两个1验证回环没有被丢掉。覆盖“关注结尾而不是子串”11011拒绝。虽然“11011”的前四位1101合法但整个串不以101结尾必须拒绝。覆盖“接受状态不等于终止”11011走查时先到S5再跳出最终拒绝。以后写词法分析器时这个特性会影响你的最长匹配记录逻辑。把这些串连同期望结果一起列成表每次改DFA的构造代码时直接跑一遍能挡住大部分回归问题。5. 构造DFA的五个常见坑现象、原因与修复5.1 ε闭包漏算DFA悄悄丢掉合法路径现象手推出来的DFA看起来结构完整但测试“1101”时走到某一步突然没有转移了或者接受了错误的串。原因算ε闭包时漏掉了某条ε边。最常见的是算ε-closure({1})时只算到{1,2,3}忘了4还有ε到6导致后续所有包含4的状态都缺了6。解决闭包计算一律用栈或队列先把起点入栈弹出时把它的所有ε目标加入集合新加入的再入栈直到栈空。不要用眼睛“目测闭包”。5.2 忘记死状态实现时程序直接卡死现象写代码时DFA的转移表里没有t那一行测试“0101”时第一个字符0就返回了空转移程序报错或直接拒绝。原因手画DFA时省略死状态代码实现时也照抄了省略版。解决构造转移表时先补死状态行让每个状态对0和1都有定义。这一步成本极低却能让状态机的代码从“遇到非法字符就崩”变成“遇到非法字符进死状态、最终拒绝”。5.3 把“以101结尾”当成“包含101子串”现象断言“101”应该被接受但DFA拒绝断言“01011”应该被接受但DFA也拒绝。原因把正规式语言理解成“包含101子串的任意串”了。1(0|1)*101要求整个串以101收尾不是只要中间出现101就行。01011的子串里确实有101从第2位到第4位但整个串结尾是011不是101所以必须拒绝。解决每个正规式都先列三个正例和三个反例再动手构造对带星号的语言永远检查“星号匹配空串”时的最短合法串。5.4 状态表抄错环路消失接受的串变多现象按化简后的DFA表编码测试时发现“11101”被错误接受或者“11011”被错误接受。原因手工把状态表从纸上搬到代码时把某一行抄串了常见的是把C读1到D抄成C读1到C。环路一旦抄错状态机对某些串的计算结果完全不对。解决抄完表之后用一个很小的程序做对拍——把纸上推导的状态表和一个独立实现的子集构造法的输出逐行比对。如果两个表不一致先别怀疑程序一般是纸面抄写有误。5.5 弄混NFA接受状态和DFA接受状态现象DFA计算完成后发现接受状态集为空或者某个明显不含10的集合被标成了接受状态。原因DFA的每个状态是一个“NFA状态子集”它的接受条件是“这个子集里至少有一个原NFA的接受状态”而不是“整个子集恰好是原接受状态本身”。本例中F {7,3,2,4,6,8,10}它含有10所以F是接受状态而其他集合不含10统统不是。解决算完所有DFA状态后逐个检查集合与{10}的交集不为空才标接受。6. 把纸面构造变成工具子集构造法的代码骨架前面整个推导过程其实就是子集构造法的完整思想。这一节给出一个最小可用的Python骨架把它和本例的NFA表接起来输出DFA转移表再和手工推导的6状态表对拍。以后遇到别的正规式就不用重新画图、重新算闭包了。def epsilon_closure(states, eps_table): # 用栈扩展确保不漏ε边 stack list(states) closure set(states) while stack: s stack.pop() for nxt in eps_table.get(s, []): if nxt not in closure: closure.add(nxt) stack.append(nxt) return frozenset(closure) def move(states, ch, trans): # 读入一个字符后能到达的所有NFA状态 targets set() for s in states: targets.update(trans.get((s, ch), [])) return targets def subset_construction(trans, eps_table, start, accepts, alphabet(0, 1)): start_set epsilon_closure({start}, eps_table) dfa_states {start_set: 0} # 集合 - 状态编号 dfa_rows [] dfa_accepts set() if start_set accepts: dfa_accepts.add(0) queue [start_set] while queue: cur queue.pop() src dfa_states[cur] row {} for ch in alphabet: nxt epsilon_closure(move(cur, ch, trans), eps_table) if not nxt: row[ch] -1 # -1 表示死状态 elif nxt not in dfa_states: dfa_states[nxt] len(dfa_states) if nxt accepts: dfa_accepts.add(dfa_states[nxt]) queue.append(nxt) row[ch] dfa_states[nxt] else: row[ch] dfa_states[nxt] dfa_rows.append(row) dfa_rows.append({ch: -1 for ch in alphabet}) # 死状态行 return dfa_rows, dfa_accepts # 本例NFA状态0起始状态10接受 eps_table { 1: [2], 2: [3, 4], 3: [2], 4: [6], 5: [3], 7: [3], } trans { (0, 1): [1], (3, 1): [8], (4, 0): [5], (6, 1): [7], (8, 0): [9], (9, 1): [10], } rows, acc subset_construction(trans, eps_table, 0, {10}) for i, row in enumerate(rows): print(i, row) print(accepts:, acc)这段代码里的epsilon_closure返回的是frozenset用来当作字典键。move函数把trans当成一个“状态, 字符- 目标状态列表”的字典来查询如果某个状态在读入该字符时没有转移就跳过它。subset_construction主循环里每次弹出一个未处理集合就为0和1各计算一次目标闭包目标为空对应死状态用-1占位目标已经在dfa_states里就复用编号否则登记新状态并入队。accepts集合记录的是DFA状态编号而不是NFA状态集合。把这段代码跑出来的表和4.2节的S1到S6表对照编号0到5对应S1到S6accepts里记录的编号对应S5。如果对不上问题多半出在NFA表抄错了而不是算法的问题。这几年我调试词法分析器最怕的其实不是DFA表庞杂而是手推和程序各算各的最后对不上。现在我的习惯是先把正规式拆成NFA用这段骨架跑一遍生成DFA再拿几个关键串走查一遍确认无误后才继续往下做。希望帮到你。本文还有配套的精品资源点击获取