简介面向编译原理与形式语言与自动机课程学习者这份doc资源整理了构造DFA的典型习题与参考答案内容涵盖正规式1(0|1)101对应DFA的构建、图4.16的确定化、图4.17的最小化以及构造接收“每个1后直接跟0”的DFA并写出正规式与正规文法。包体为1个doc文档仅63KB文件虽小但解题步骤完整适合考前复习、作业对照与自学查漏。已有9964人浏览学习。文档通过状态转移表、重新命名、子集法及最小化分划等写法逐步展示从NFA到DFA再到最简DFA的转换过程并对关键状态决策给出说明最后一题补充了0(0|10)0等正规式表示便于系统掌握自动机构造方法。1. 正规式 1(0|1)*101为什么这道题不能靠“看”出 DFA正规式 1(0|1)*101 对应的 DFA是自动机课程里出现频率极高的一道手工推导题。表面看它只是“以 1 开头、最后三位是 101 的二进制串”但直接凭感觉画状态图十有八九会在边界串上翻车要么漏掉死态要么把 NFA 闭包内部的接受状态误当成整体接受状态导致 101、111 这些本应拒绝的串被错误接受。本文从语言拆解开始完整走一遍推导链先把正规式变成 ε-NFA再用子集法确定化接着做最小化最后用可复现的脚本做样例回归。这条路同样适用于任何“正规式转 DFA”的手工题适合正在准备考试、写课程报告或需要把转换过程讲清楚再动手实现的从业者。2. 先把语言边界掰开1(0|1)*101 接受与拒绝的串长什么样2.1 逐段拆解连接、闭包、连接之后到底拼接了什么正规式 1(0|1)101 由三段组成开头的单个字符 1中间的 (0|1)末尾的三个字符 101。运算优先级上* 先作用于 (0|1)内部的“或”再被闭包包裹整个式子可以写成L { 1 w 101 | w 是任意 0/1 串 }这里的“”是字符串拼接不是逻辑与。很多人会把这道题理解成“开头是 1而且最后三位是 101”从集合角度看这个描述和正规式表示的语言碰巧等价但推导时容易出问题因为拼接语义要求三段在字符串里先后出现且不能重叠。正规式 1(0|1)*101 描述的最短串是先去取闭包为空得到 1 101即 1101而不是 101。这一点在后面的 NFA 构造和验证里会反复用到。初学者最容易犯的错误是把 (0|1)* 理解为“任意匹配”忽略了它只是语言中间的一个切片。例如串 1101 的正确切法是 1、空串、101串 10101 的切法是 1、0、101而串 101 无论怎么切都无法同时满足开头 1 和末尾 101 分开存在因为长度不够所以必须拒绝。2.2 边界串列表哪些进、哪些出最短串为什么是 1101为了后面验证 DFA 时不至于只靠感觉先把关键样例固定下来。我通常会把接受和拒绝的串各挑三五个做成一张对照表这张表会一直用到最后一章的脚本验证里。| 串 | 是否属于 L(1(0|1)*101) | 原因与推荐切法 | | --- | --- | --- | | 1101 | 接受 | 1 空串 101是整个语言的最短串 | | 10101 | 接受 | 1 0 101 | | 11101 | 接受 | 1 1 101 | | 110101 | 接受 | 1 01 101 | | 101 | 拒绝 | 长度只有 3无法把开头 1 和末尾 101 分开 | | 01101 | 拒绝 | 第一个字符不是 1 | | 11011 | 拒绝 | 开头满足但最后三位是 011不是 101 | | 111 | 拒绝 | 最后三位是 111且长度不足 |这张表很有价值。它告诉你验证一个 DFA 是否正确不能只拿一个正例跑通就结束必须同时覆盖“长度不足”“开头错误”“结尾错误”三类反例。后面第 5 章的避坑点和第 6 章的脚本验证都是围绕这张表展开的。2.3 滑动窗口视图正则表达式在跟踪末尾三位如果要用直觉理解这个 DFA 的形态可以把它看成一个滑动窗口。语言等价于“长度不小于 4、首字符为 1、最后三位为 101”的二进制串集合。处理一个串时真正需要记住的信息只有两块开头是不是已经确认是 1以及当前最近两个字符是什么。因为当新字符 c 读入时新的最后三位可以由旧倒数第二位、旧最后一位和 c 拼出来。这就是为什么最终得到的 DFA 状态数不会太少除了初始态和死态还需要若干状态来记忆尾部信息。一个常见误区是只记忆“最近三位是不是 101”这会导致 101 这种短串被错误接受因为长度约束被丢掉了。滑动窗口只是辅助理解的工具真正手工推导时我仍然建议走标准三段式构造而不是凭直觉画状态这样每一步都有据可查。3. 用标准三段式构造 NFA从正规式到 ε-NFA3.1 基础符号 NFA 的写法1、0、1 三个片段单个字符 a 的 NFA 是最基础的单元一个起始状态一条标注为 a 的边一个结束状态。把正规式 1(0|1)*101 拆散后需要准备这些片段开头字符 1状态 q0 读入 1 到达 q1中缀闭包 (0|1)*后面单独搭后缀 101需要三个连续转移分别是 1、0、1。后缀 101 我习惯用一组独立状态表达q4 读入 1 到 q5q5 读入 0 到 q6q6 读入 1 到 q7。q7 是整个 NFA 唯一的最终接受状态。这样命名的好处是后续子集法计算时只要子集里出现 q7就说明该子集是 DFA 的终态判断起来非常直接。3.2 给 (0|1)* 搭闭包两个状态加一个 ε 回环(0|1)* 的 NFA 可以只用一个循环状态完成用 q2 作为闭包入口q3 作为循环体。q2 通过 ε 边进入 q3q3 上有 0 和 1 两个自环。这样 q3 每走一次自环就相当于读入一个 0 或 1而 q2 允许直接空走匹配闭包取空的情况。单独看这个闭包子结构时q2 和 q3 都可以视为内部“可结束”的状态。但必须注意把它们拼接进完整正规式后这两个状态不再是整体 NFA 的接受状态因为整个表达式后面还拖着 101 三个字符。很多人在这里被内部终态带偏把 q2、q3 当成整体终态这是后面第 5 章要重点排查的坑。闭包的出口也要处理q3 通过 ε 边连到后缀 101 的起点 q4。这样从闭包走出空串或任意中缀后都能无缝进入末尾 101 的匹配。3.3 串成完整 ε-NFA 并整理状态转移表把 q1开头 1 的结束状态用 ε 边连到 q2q3 用 ε 边连到 q4整体 NFA 就成型了。状态转移表如下状态ε01是否为整体接受态q0——{q1}否q1{q2}——否q2{q3}——否q3{q4}{q3}{q3}否q4——{q5}否q5—{q6}—否q6——{q7}否q7———是这张表里ε 边承担了所有“自动跳转”q1 跳到闭包入口q2 跳到循环体q3 在闭包内循环同时也能跳到 q4 去开始匹配 101。读入 0 或 1 时只有 q3 和与后缀相关的 q5、q6 会产生实际状态迁移。整体接受态只在 q7 上闭包内部的两个状态不参与最终的接受判断。4. 子集法确定化逐行算出 DFA 的转移表4.1 ε 闭包先算清每个 NFA 状态的“隐形邻居”子集法确定化的第一步是计算 ε 闭包。一个状态的 ε 闭包就是它能通过若干条 ε 边到达的所有状态集合包含它自己。这道题里最关键的几个闭包是ε-closure(q0) {q0}初始状态没有 ε 边所以闭包就是自己ε-closure(q1) {q1, q2, q3, q4}因为 q1 到 q2q2 到 q3q3 到 q4ε-closure(q2) {q2, q3, q4}ε-closure(q3) {q3, q4}其余 q4 到 q7 都没有 ε 边闭包是单元素集合。计算闭包时不要漏连坐关系。q1 能到 q2q2 能到 q3q3 能到 q4所以 q1 的闭包必须包含 q4。这一步出错后面整个子集表都会错位。4.2 从初态 S0 出发逐步生成子集确定化从初始状态的 ε 闭包开始。令 S0 ε-closure(q0) {q0}然后反复计算每个子集读入 0 和 1 之后再取 ε 闭包得到新子集。完整的推导过程如下当前子集读入 0读入 1S0 {q0}X ∅B {q1, q2, q3, q4}B {q1, q2, q3, q4}C {q3, q4}F {q3, q4, q5}C {q3, q4}C {q3, q4}F {q3, q4, q5}F {q3, q4, q5}G {q3, q4, q6}F {q3, q4, q5}G {q3, q4, q6}C {q3, q4}H {q3, q4, q5, q7}H {q3, q4, q5, q7}G {q3, q4, q6}F {q3, q4, q5}X ∅X ∅X ∅这里最容易算错的一步是 F 读入 0。F 里有 q5而 q5 在 NFA 中有一条 0 边到 q6所以 F 读 0 必须得到 G {q3, q4, q6}而不是仍然回到 C。很多人因为只盯着闭包循环状态 q3把 q5 的 0 边漏掉导致 q6 永远进不了状态集后缀 101 永远无法匹配完成。另一处关键是 G 读入 1G 里的 q4 走 1 边到 q5q6 走 1 边到 q7所以得到 H {q3, q4, q5, q7}。这是整个计算中第一次出现 q7 的子集也就是 DFA 的终态。4.3 加上死态、标注终态得到可直接画图的 DFA对上面的子集重新命名并把 X 这个空集显式保留为死态 D就得到一份完整的 DFA 转移表。注意A 是初态Q 是终态其余都是中间态状态01是否为接受态ADM否DDD否MMN否NPN否PMQ否QPN是这份表里的 M、N、P、Q 对应原始子集中的合并结果M 由 B 和 C 合并而来N 是原 FP 是原 GQ 是原 H。为什么 B 和 C 能合并看子集表B 和 C 在 0 和 1 上的去向完全一致而且都不含 q7所以它们等价。用这张表可以快速手推几个串。比如 1101A 读 1 到 MM 读 1 到 NN 读 0 到 PP 读 1 到 Q最终落在接受态101A 读 1 到 MM 读 0 到 MM 读 1 到 NN 不是接受态拒绝。整体状态数为 6比最小化前的 7 个子集少了一个这就是等价状态合并的效果。5. DFA 构造避坑5 个最容易做错翻车的细节5.1 把 NFA 闭包内部的接受态当成整体终态现象推导过程中发现子集 B、C 都包含 q2、q3而 q2、q3 在闭包子结构里是“可结束”的状态于是把 B、C、F、G 都标成 DFA 终态。结果 101、111 这类串全部被错误接受。原因NFA 拼接时闭包内部的接受状态没有在整体层面“作废”。整个正规式后面还挂着 101闭包内部能停不代表整个表达式能停。解决整体接受态只看子集是否包含 q7。B、C、F、G 都只含闭包和 101 前缀状态只有 H {q3, q4, q5, q7} 含 q7所以 DFA 终态只有一个 Q。5.2 死态缺失转移表不完整现象A 读入 0 时没有对应状态转移表里留下空项。手写证明题时老师会直接圈出转移函数不完整用程序实现时字典查找直接抛异常。原因子集法遇到空集 ∅ 时很多人习惯直接丢弃没有为“彻底不接受”的路径建模。解决把空集命名为死态 DD 在读入 0 和 1 时都回到 D。这不是多余的负担DFA 的定义本来就要求转移函数是全函数缺少死态就是定义不完整。5.3 最小化时把接受态和非接受态合并现象F 和 H 在读入 0、1 后分别去 G、F 和 G、F行为完全一致。有人因此把 F 和 H 合并成一个状态结果 DFA 失去终态所有串都变成拒绝。原因两个状态等价除了要求每个输入上的后继等价还要求它们同为接受态或同为非接受态。F 不是终态H 是终态这一条就不满足行为相同只是必要条件。解决最小化时先按“终态 / 非终态”分成两大组再逐组细分。这道题的最小化结果是 6 个状态比初始 7 个子集少 1 个因为只有 B 和 C 可以合并。5.4 用“最后三位 101”直推时漏掉开头必须是 1现象直接按“最后三位是 101”设计状态机结果 101 被接受1101 反而可能因为转移设计不合理被拒绝或接受错位。原因滑动窗口视图只在“已经确认开头正确”的前提下有效。正规式 1(0|1)*101 是拼接关系开头的 1 与末尾的 101 必须分成两段存在最短串因此是 1101。解决如果要用直觉法做交叉验证必须额外增加“开头是否已确认是 1”的标记并且用 101、1101 两个串做双向检查。更稳妥的做法是回到第 3、4 章的标准流程避免直觉法覆盖不到边界。5.5 只用正例不用反例验证覆盖不全现象1101、11101、110101 全部接受就认为 DFA 正确后来交换检查发现 01101 也能走出一条非死态路径但没被终态吸收说明测试集中缺少反例。原因正例验证的是“不该漏的没漏”反例验证的是“不该收的没收”。手工验证时人倾向于选容易构造的正例忽略拒绝路径。解决固定一张验证表至少包含三正三反。正面用 1101、10101、11101反面用 101、01101、11011。如果做程序验证可以直接穷举长度 1 到 6 的全部二进制串用脚本一次性比对这个方法会在第 6 章给出。6. 收尾技巧把 DFA 跑起来反推正规式6.1 用一份不到 30 行的脚本验证 DFA手工画完状态图后最实用的验证方式是把转移表翻译成一段极短的脚本。下面这份代码直接对应最小化后的 6 状态 DFA状态 0 到 5 依次是 A、D、M、N、P、Q# 最小化后的 DFA 转移表 # 状态编号: 0A, 1D(死态), 2M, 3N, 4P, 5Q(终态) dfa { 0: {0: 1, 1: 2}, 1: {0: 1, 1: 1}, 2: {0: 2, 1: 3}, 3: {0: 4, 1: 3}, 4: {0: 2, 1: 5}, 5: {0: 4, 1: 3}, } accept {5} def run(word): state 0 for ch in word: state dfa[state][ch] print(f{word}: {ACCEPT if state in accept else REJECT}) for w in [1101, 10101, 11101, 101, 01101, 11011, 111]: run(w)脚本逻辑很直接初态固定为 0每个字符查一次字典完成状态迁移结束后判断当前状态是否在 accept 集合里也就是状态 5。运行结果应当是1101、10101、11101、110101 接受101、01101、11011、111 拒绝。如果哪个串的结果和你预期不符说明转移表或状态编号对不上。这个方法比肉眼盯状态图可靠得多也方便后面穷举所有长度小于等于 6 的二进制串做全量回归。6.2 用消去法把 DFA 反推回正规式做交叉实验验证 DFA 和 NFA 是否一致除了跑样例还有一个更彻底的办法把 DFA 反推成正则表达式看能否回到 1(0|1)*101。常见做法是给 DFA 加一个新的初态和终态形成广义 NFA然后按顺序消去中间状态。每消去一个状态就把经过它的路径压缩成一条带正规式标签的边最后剩下的两个状态之间那条边的标签就是等价的正规式。以这个六状态 DFA 为例消去死态 D 后路径基本不受影响继续消去中间状态会发现所有回到 M 的环在压缩后形成 (0)* 一类结构而指向 Q 的路径经过反复化简最终收敛成 1(0|1)*101。整个过程比较费纸但作为交叉实验很有说服力如果反推结果和题目不一致说明前面某一步的转移表构造或者状态合并出了问题需要回去重查。6.3 交付前必查的 6 项清单最后把这些动作整理成一份固定清单我每次做这类题都会过一遍初态 A 读入 0 是否进入死态而不是停在 A整个 DFA 是否只有一个接受态 Q1101 是否接受101 是否拒绝01101 是否拒绝11011 是否拒绝转移表中是否保留了死态 D 的完整自环最小化后状态数是否为 6如果还是 7检查 B 和 C 是否漏合并。我第一次做这道题时偷懒直接用“最后三位 101”猜状态结果在 101 这类短串上翻车后来才意识到开头约束和长度约束必须同时跟踪。现在不管题目多简单我都会按“拆语言、搭 NFA、子集化、最小化、跑反例”这套流程完整走一遍这套流程比“看懂标准答案”重要得多希望帮到你。本文还有配套的精品资源点击获取