1(0|1)*101正规式转DFA：从NFA到状态表验证

简介编译原理与形式语言课程中“有穷自动机与正规式”章节的经典习题解答文档面向计算机专业本科生、考研备考者及自学自动机理论的学习者。文档围绕四个核心问题展开构造正规式1(0|1)*101相应的DFA、对图4.16进行确定化、对图4.17进行最小化以及构造满足“每个1后都紧跟0”的DFA并给出其正规式。解答过程完整包含初始状态划分、ε-闭包与子集构造法、状态重命名、状态转移表以及最终DFA图示每一步均给出清晰的推导思路与结果便于读者验证自己的解题过程。压缩包仅含1个doc文件大小约63KB内容紧凑、易于打印和移动端阅读。目前已有9963人学习浏览适合正在复习编译原理、准备研究生入学考试或希望提升自动机构造、确定化与最小化实操能力的读者。1. 从正规式 1(0|1)*101 到 DFA先把“101 匹不匹配”这关过了构造正规式 1(0|1)*101 相应的 DFA是编译原理、形式语言与自动机课程里出现频率极高的一道题。很多人第一眼觉得它简单等真画状态图就会发现闭包里的 ε 怎么处理101 到底算不算合法串状态表画完用什么用例验证这篇笔记按我平时做题的顺序来先把正规式拆开再给一个紧凑 NFA 和完整子集构造表最后把踩过的坑和验证脚本一起放出来。适合正在准备考试、做课程设计或者想搞清楚正则表达式引擎跳转表怎么来的读者。2. 正规式语义拆解1(0|1)*101 到底匹配哪些串2.1 运算符优先级与表达式结构正规式里运算符的优先级不是从左到右读的。闭包*的优先级最高其次是连接最后才是选择|。所以1(0|1)*101不能直接理解成“字符串 101 出现在某个位置”而要按运算符优先级把结构拆成这个样子1 · ( (0|1)* ) · 1 · 0 · 1这里圆点表示连接。第一个字符是固定的1中间括号里是0|1再整体取闭包最后三个字符固定是1、0、1。也就是说这个正规式由五个片段拼接开头一个1中间一个任意长度的0/1串结尾一个固定的101。我一般在草稿上会再简化一步把第一个1和结尾的1分开看。1(0|1)*101真正要求的是第一个字符必须是1最后一个字符是1倒数第二个是0倒数第三个是1。中间那一段可以是空串也可以是任意 0/1 组合。这个“中间段可以为空”的结论直接决定了后面 NFA 里 ε 转移怎么画。很多资料会把(0|1)*直接说成“任意二进制串”这个说法大方向对但容易让人忽略一个问题中间段和尾部101是连接关系不是重叠关系。连接意味着先有开头的1再走完中间段才轮到尾部的101。如果中间段为空最小匹配串应该是1101而不是101。2.2 边界条件哪些串在语言里哪些不在把语言定义写清楚后面所有验证都围绕这个边界来。我常用一张表把典型串分成两类输入串是否匹配理由1101匹配中间段为空1 10111101匹配中间段为11 1 10110101匹配中间段为01 0 101110101匹配中间段为101 10 101101不匹配长度只有 3头部 1 和尾部 101 重叠1001不匹配末尾是001不是10111011不匹配末尾是011不是1010101不匹配开头不是1这张表里最容易翻车的是101。单看字符串它确实以1开头也以101结尾但正规式1(0|1)*101的连接语义要求至少有一个位置放中间段哪怕中间段是空串。空串也是“占了一个片段位置”所以最小字符串是1 101 1101。101相当于让开头的1同时充当尾部101的第一个字符这在形式语言里是不允许的。另一个容易忽略的是11011。它开头是1但结尾三位是011不符合要求。有人在画 DFA 时只记住“第一个字符是 1”忘了还要同时监控末尾三位于是把这类串错误地接受了。所以正规式语义分析这一步价值不是理论好看而是帮你定义出后续必须用测试用例守住的边界。2.3 为什么我选择“先语义后 NFA”而不是一上来就展开 Thompson正规式到 DFA 的通用路线是正规式 → NFA → 子集构造法 → DFA → 最小化。这套流程永远不会错课程考试也认可。但手工做题时标准 Thompson 构造会引入大量 ε 转移状态一多子集构造就特别容易漏算。我的习惯是先做两分钟的语义分析这个正规式描述的语言是什么最小串是什么最明显的反例是什么想清楚这几个问题再去构造 NFA状态表对不对一眼就能看出来。前面这张匹配表就是后续所有验证的“基准测试集”。哪怕 NFA 画得和标准答案不一样只要跑出来的接受/拒绝结果一致大概率方向没问题。3. 从 NFA 到 DFA一张状态表把 1(0|1)*101 推到底3.1 构造一个紧凑 NFA状态 B 的自环就是 (0|1)*标准 Thompson 构造每一步都引入新状态适合计算机程序自动执行但手工画这道题时状态太多。我常用一个等价化简既然(0|1)*表示“任意 0/1 串”就可以把它压缩成一个自环状态。NFA 状态设计如下A起始状态负责读开头的1。B已经读完开头1正在处理中间(0|1)*可以不断读 0 或 1。C准备匹配尾部101的第一个1。D匹配完尾部101的第一个1准备匹配0。E匹配完10准备匹配最后一个1。F接受状态。对应的 NFA 状态转移表NFA 状态输入 0输入 1εA无B无BBBCC无D无DE无无E无F无F无无无接受这里最关键的边是B --ε-- C。它表示中间(0|1)*可以选择一次也不循环直接从 B 进入尾部匹配。如果没有这条 ε 边最小串1101就无法被接受因为读完开头1后必须至少读一个中间字符才能进入尾部整个语言就变成了1(0|1)101和原正规式不等价。这个 NFA 虽然比标准 Thompson 精简但表达能力和完整展开版一致。如果你要交给老师审阅并且老师明确要求使用 Thompson 构造法可以把这个紧凑结构替换成标准闭包片段后续子集构造步骤不变。3.2 子集构造法从 NFA 状态集合推出 DFA 状态子集构造法的核心是两个操作ε 闭包和字符转移。ε 闭包是指从当前状态集合出发只靠 ε 边能到达的全部状态字符转移则是在闭包基础上再读一个输入字符然后对新状态集合继续求 ε 闭包。从起始状态 A 开始S0 ε-closure({A}) {A}输入 0 没有转移所以去死状态 D。输入 1 到 B再对 B 求 ε 闭包得到 {B, C}记为 S1。接着按同样方式逐个计算得到完整的子集构造表DFA 状态对应的 NFA 集合输入 0 后输入 1 后是否接受S0{A}DS1否S1{B, C}S1S2否S2{B, C, D}S3S2否S3{B, C, E}S1S4否S4{B, C, D, F}S3S2是D∅DD否手动算的时候最容易漏的是 S1 的初始闭包。从 A 读入1先到 B但 B 还有 ε 边到 C所以 S1 必须包含 C写成 {B, C}。如果只写 {B}后面整个状态表都会偏移一位导致本应接受的串全部卡住。S2 是 {B, C, D}输入 0 时B 的 0 转移仍是 BC 没有 0 转移D 的 0 转移是 E得到 {B, E}再求 ε 闭包得到 {B, C, E}也就是 S3。输入 1 时B 到 BC 到 DD 没有 1 转移得到 {B, C, D}仍是 S2。这说明 S2 在读 1 时会留在自己身上和后面测试串11101的行为一致。3.3 最终 DFA 状态转换表把上一步整理成可以直接画图、可以直接写进代码的跳转表DFA 状态输入 0输入 1是否接受S0DS1否S1S1S2否S2S3S2否S3S1S4否S4S3S2是DDD否这张表就是本题的核心产物。从 S0 出发逐个字符查表最后停在 S4 就接受否则拒绝。画状态图时S0 画一个入口箭头S4 画双圈表示接受态D 画成死状态两个输入都回到 D。大多数教材会把 D 省略但实际做代码验证时死状态不画出来程序很容易因为找不到转移而越界。3.4 拿典型串验证状态表状态表写完不能直接交差我习惯至少跑四个串。1101这是最小匹配串。路径是 S0 → S1 → S2 → S3 → S4接受。它验证的是中间闭包取空串的情况。11101路径是 S0 → S1 → S2 → S2 → S3 → S4接受。它验证的是中间闭包取一个1的情况。101路径是 S0 → S1 → S1 → S2最终停在 S2拒绝。这正好对应第 2 章说的边界问题。11011路径是 S0 → S1 → S2 → S3 → S4 → S2拒绝。它证明 DFA 没有因为中间出现过101就提前接受最后三位必须是011就按011拒掉。如果这四个串全通过状态表基本可以放心使用。4. 构造 DFA 常见问题排查五个高频翻车现场4.1 坑一把 101 本身当成合法输入现象拿输入串101去验证 DFA发现画出的状态图接受了它还觉得理所当然。原因用自然语言理解“以 1 开头、以 101 结尾”会认为101两个条件都满足。但正规式1(0|1)*101要求先有开头1再有中间段最后才放入尾部101三段是连接关系不允许头部和尾部共享字符。解决在接受态判断上增加“最小长度必须大于等于 4”的约束或者用最小串1101做基准测试。我们的 S4 接受态只有读完完整的1 循环 101才到达101会停在 S2不会误入 S4。4.2 坑二遗漏 B 到 C 的 ε 转移导致空循环失效现象NFA 里只有 B 的自环没有B --ε-- C。结果1101被拒绝11101反而能从循环里多消费一个1才能进入尾部。原因把(0|1)*理解成了“必须至少循环一次”忽略了闭包允许零次匹配。空串在形式语言里也是一个合法的中间段没有 ε 边就等于把零次情况删掉了。解决在构造闭包 NFA 时务必保留一条从循环体出口到后续片段的 ε 边。验证时一定要测1101它能暴露所有“循环至少一次”的错误。4.3 坑三子集构造时忘了对字符转移结果再次求 ε 闭包现象从初始状态读入1只得到 {B}没有把 B 的 ε 闭包 C 算进去。后面每一个 DFA 状态都比正确集合少一个元素最终状态表的接受路径全乱。原因子集构造法的完整公式是ε-closure(move(当前集合, 字符))。很多人只算了 move忘了外面那层 ε 闭包。解决每一步都强制写成两个动作先收集所有字符转移目标再对这个目标集合求 ε 闭包。初始状态也要先求 ε 闭包不能直接拿裸状态集合当起点。4.4 坑四接受状态判断标准错误现象NFA 的接受状态是 F但子集构造表里把包含 D 的集合也标成了接受或者把包含 F 的集合漏掉了。原因把 NFA 里状态 C、D、E 误认为“已经接近结束”就想标记为接受。接近结束不等于结束只有读到完整尾部101并进入 F 才算匹配完成。解决每次生成新的 DFA 状态集合时都检查这个集合里是否包含 F。本题只有 S4 包含 F所以只有 S4 是接受状态。S2 里虽然包含 C、D但没有 F必须拒绝。4.5 坑五省略死状态导致非法分支失控现象状态表里有几个格子没有填目标状态比如 S0 在输入 0 时直接留空。用程序模拟时遇到非法开头0会报 KeyError或者被误判为拒绝。原因死状态不是“可选项”而是 DFA 必须存在的状态。正规式要求开头必须是1输入0后不可能再进入接受态需要有一个明确的 D 状态把这些非法分支吸收掉。解决在最终状态表里保留 D并让 D 在 0 和 1 两个输入下都回到 D。这样无论是手工验证还是写程序所有输入都有明确去处。5. 验证与最小化给 DFA 做个体检再交差5.1 用一小段 Python 脚本自动验证状态表状态表是死数据写代码跑一遍最省事。我用一个字典直接描述跳转表然后用循环模拟输入串。# DFA 跳转表key 是 (状态, 输入字符) trans { (S0, 0): D, (S0, 1): S1, (S1, 0): S1, (S1, 1): S2, (S2, 0): S3, (S2, 1): S2, (S3, 0): S1, (S3, 1): S4, (S4, 0): S3, (S4, 1): S2, (D, 0): D, (D, 1): D, } accept {S4} def run_dfa(s: str) - bool: state S0 for ch in s: state trans[(state, ch)] return state in accept for s in [1101, 11101, 10101, 101, 1001, 11011]: print(s, run_dfa(s))逻辑说明run_dfa从 S0 出发每读一个字符就查一次跳转表最后看停在哪个状态。返回True表示接受False表示拒绝。参数说明trans完全对应第 3.3 节的状态表如果你自己画出的状态命名不同把字典里的状态名替换掉即可accept集合可以按你的接受状态修改。这段脚本没有任何依赖复制就能跑。运行结果应该依次是True True True False False False。如果某个结果不对回头检查对应的行和列多半是 ε 闭包或者接受态标错了。5.2 用划分法检查状态是否冗余得到的 DFA 有 5 个有效状态加 1 个死状态。是不是最简可以用划分法快速确认。先把状态分成两类接受态{S4}和非接受态{S0, S1, S2, S3, D}。然后看每个状态在输入 0 和输入 1 下的目标是否属于同一个类。例如 S3 在输入 1 时到接受态 S4而 S0、S1、S2 在输入 1 时都不会到接受态所以 S3 必须单独分出来。继续划分下去S0、S1、S2、S3、D 之间要么转移去向不同要么能到达的状态不同最终无法再合并。这个表可以直接当作最小 DFA 使用不需要再压缩。如果你是从标准 Thompson 完整 NFA 走过来的同学可能一开始会得到七八个状态再跑一遍划分法最后也会回到这几个状态上来。5.3 把 DFA 复用到其他场合这个跳转表不只是考试答案它本身就是一个词法分析器的最小状态控制表。把trans字典换成二维数组把状态换成整数下标再配一个输入缓冲就是很经典的手工词法分析器雏形。如果想改造成识别1(0|1)*110只需要把尾部三个状态 C、D、E 的字符转移改成1 - 1 - 0其余闭包结构完全不用动。从那以后我每构造一个 DFA都会强制走一遍同样的流程先列边界用例再画 NFA子集构造最后用脚本把接受串和拒绝串都跑一遍。虽然不能保证一次画对但至少交作业之前能把翻车概率压到最低。希望帮到你。本文还有配套的精品资源点击获取