企业官网建设流程全解析

简介：编译原理与形式语言课程中“有穷自动机与正规式”章节的经典习题解答文档，面向计算机专业本科生、考研备考者及自学自动机理论的学习者。文档围绕四个核心问题展开：构造正规式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 边界条件：哪些串在语言里，哪些不在

把语言定义写清楚，后面所有验证都围绕这个边界来。我常用一张表把典型串分成两类：

这张表里最容易翻车的是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 状态转移表：

这里最关键的边是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。

接着按同样方式逐个计算，得到完整的子集构造表：

手动算的时候最容易漏的是 S1 的初始闭包。从 A 读入1先到 B，但 B 还有 ε 边到 C，所以 S1 必须包含 C，写成 {B, C}。如果只写 {B}，后面整个状态表都会偏移一位，导致本应接受的串全部卡住。

S2 是 {B, C, D}，输入 0 时：B 的 0 转移仍是 B，C 没有 0 转移，D 的 0 转移是 E，得到 {B, E}，再求 ε 闭包得到 {B, C, E}，也就是 S3。输入 1 时：B 到 B，C 到 D，D 没有 1 转移，得到 {B, C, D}，仍是 S2。这说明 S2 在读 1 时会留在自己身上，和后面测试串11101的行为一致。

3.3 最终 DFA 状态转换表

把上一步整理成可以直接画图、可以直接写进代码的跳转表：

这张表就是本题的核心产物。从 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，子集构造，最后用脚本把接受串和拒绝串都跑一遍。虽然不能保证一次画对，但至少交作业之前，能把翻车概率压到最低。希望帮到你。

本文还有配套的精品资源，点击获取