*101转DFA：NFA确定化、最小化与验证避坑指南)
简介：面向编译原理与形式语言与自动机课程学习者，这份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：从正规式到 ε-NFA
3.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 到 q5，q5 读入 0 到 q6，q6 读入 1 到 q7。q7 是整个 NFA 唯一的最终接受状态。这样命名的好处是，后续子集法计算时，只要子集里出现 q7，就说明该子集是 DFA 的终态，判断起来非常直接。
3.2 给 (0|1)* 搭闭包：两个状态加一个 ε 回环
(0|1)* 的 NFA 可以只用一个循环状态完成：用 q2 作为闭包入口，q3 作为循环体。q2 通过 ε 边进入 q3，q3 上有 0 和 1 两个自环。这样 q3 每走一次自环，就相当于读入一个 0 或 1，而 q2 允许直接空走，匹配闭包取空的情况。
单独看这个闭包子结构时，q2 和 q3 都可以视为内部“可结束”的状态。但必须注意：把它们拼接进完整正规式后，这两个状态不再是整体 NFA 的接受状态，因为整个表达式后面还拖着 101 三个字符。很多人在这里被内部终态带偏，把 q2、q3 当成整体终态，这是后面第 5 章要重点排查的坑。
闭包的出口也要处理：q3 通过 ε 边连到后缀 101 的起点 q4。这样从闭包走出空串或任意中缀后，都能无缝进入末尾 101 的匹配。
3.3 串成完整 ε-NFA 并整理状态转移表
把 q1（开头 1 的结束状态）用 ε 边连到 q2，q3 用 ε 边连到 q4，整体 NFA 就成型了。状态转移表如下：
| 状态 | ε | 0 | 1 | 是否为整体接受态 |
|---|---|---|---|---|
| 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 到 q2，q2 到 q3，q3 到 q4；
- ε-closure(q2) = {q2, q3, q4}；
- ε-closure(q3) = {q3, q4}；
- 其余 q4 到 q7 都没有 ε 边，闭包是单元素集合。
计算闭包时不要漏连坐关系。q1 能到 q2，q2 能到 q3，q3 能到 q4，所以 q1 的闭包必须包含 q4。这一步出错，后面整个子集表都会错位。
4.2 从初态 S0 出发逐步生成子集
确定化从初始状态的 ε 闭包开始。令 S0 = ε-closure(q0) = {q0}，然后反复计算每个子集读入 0 和 1 之后，再取 ε 闭包得到新子集。完整的推导过程如下：
| 当前子集 | 读入 0 | 读入 1 |
|---|---|---|
| S0 = {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 读入 1：G 里的 q4 走 1 边到 q5，q6 走 1 边到 q7，所以得到 H = {q3, q4, q5, q7}。这是整个计算中第一次出现 q7 的子集，也就是 DFA 的终态。
4.3 加上死态、标注终态，得到可直接画图的 DFA
对上面的子集重新命名，并把 X 这个空集显式保留为死态 D，就得到一份完整的 DFA 转移表。注意，A 是初态，Q 是终态，其余都是中间态：
| 状态 | 0 | 1 | 是否为接受态 |
|---|---|---|---|
| A | D | M | 否 |
| D | D | D | 否 |
| M | M | N | 否 |
| N | P | N | 否 |
| P | M | Q | 否 |
| Q | P | N | 是 |
这份表里的 M、N、P、Q 对应原始子集中的合并结果：M 由 B 和 C 合并而来，N 是原 F，P 是原 G，Q 是原 H。为什么 B 和 C 能合并？看子集表，B 和 C 在 0 和 1 上的去向完全一致，而且都不含 q7，所以它们等价。
用这张表可以快速手推几个串。比如 1101：A 读 1 到 M，M 读 1 到 N，N 读 0 到 P，P 读 1 到 Q，最终落在接受态；101：A 读 1 到 M，M 读 0 到 M，M 读 1 到 N，N 不是接受态，拒绝。整体状态数为 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 时没有对应状态，转移表里留下空项。手写证明题时，老师会直接圈出转移函数不完整；用程序实现时，字典查找直接抛异常。
原因：子集法遇到空集 ∅ 时，很多人习惯直接丢弃，没有为“彻底不接受”的路径建模。
解决：把空集命名为死态 D，D 在读入 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 转移表 # 状态编号: 0=A, 1=D(死态), 2=M, 3=N, 4=P, 5=Q(终态) 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 是否只有一个接受态 Q；
- 1101 是否接受，101 是否拒绝；
- 01101 是否拒绝，11011 是否拒绝；
- 转移表中是否保留了死态 D 的完整自环；
- 最小化后状态数是否为 6，如果还是 7，检查 B 和 C 是否漏合并。
我第一次做这道题时偷懒，直接用“最后三位 101”猜状态，结果在 101 这类短串上翻车，后来才意识到开头约束和长度约束必须同时跟踪。现在不管题目多简单，我都会按“拆语言、搭 NFA、子集化、最小化、跑反例”这套流程完整走一遍，这套流程比“看懂标准答案”重要得多，希望帮到你。
本文还有配套的精品资源，点击获取
