正则表达式转DFA全解析：1(0|1)*101的NFA构造、子集构造与最小化

简介：面向编译原理课程中“正规式与有穷自动机”章节的习题资料，主要服务需要掌握DFA构造、确定化与最小化技巧的高校本科生。资源包内仅有1个doc文档，约63KB，正文直接给出四道典型习题及参考答案，涵盖正规式1(0|1)*101对应DFA的完整构建、图4.16所示的NFA确定化过程、图4.17所示DFA的最小化分步推导，以及接收Σ={0,1}上每个1后紧跟0的字符串的DFA与正规式设计；解答中包含状态转移表、重新命名、终态/非终态划分等关键操作，便于读者对照理解。目前已有9964人浏览学习，是一份精炼且针对性强的编译原理复习材料。

1. 一道作业题，却是正则引擎的骨架

“构造正规式1(0|1)*101相应的DFA”看起来是编译原理课的一道手工作业，但它背后正是正则表达式引擎和词法分析器生成器的核心流程：先把正则式变成 NFA，再把 NFA 变成 DFA，最后把 DFA 尽量压小。标题里的正规式 1(0|1)*101 匹配的是“以 1 开头，中间是任意个 0 或 1，最后以 101 结尾”的字符串，最短的例子是 1101，而 101 本身反而不匹配。手算这一题，要依次用到汤普森构造法、子集构造法和状态最小化三个工具，它们分别对应词法分析器从规则到状态机的三个阶段。适合读这篇文章的人很明确：正在学编译原理或形式语言的学生，以及需要在工作中手写词法分析器或正则匹配模块的工程师。手动拆一遍之后，你对“为什么有的正则式很快、有的正则式会回溯到天荒地老”会有一个非常具体的体感。

2. 汤普森构造法：把 1(0|1)*101 拆成 NFA 状态图

2.1 为什么先造 NFA 而不是直接画 DFA

直接画出 DFA 需要人脑模拟所有可能的前缀，一旦正则式里出现闭包和选择，漏一条边是常有的事。NFA 则可以完全机械地构造：按正则式的语法结构递归拼接，每个子表达式对应一小块状态图，再把小块用 ε 边焊起来。这个过程保证正确性，也方便检查。

更实际的理由是工程层面的：词法分析器生成器内部就是“正则式 → NFA → DFA → 最小化”这样一条流水线，你手工做一遍，等于把生成器的核心流程走了一遍。常见做法是先把正则式按优先级拆成语法树，然后从叶子往上逐层构造。1(0|1)101 这棵语法树是：外层是一个连接，左子是单个字符 1，右子是 (0|1)和 101 的连接；101 又是一个连接链 1 → 0 → 1。拆到这里，构造就是机械活了。

先约定一条规则：每个字符的 NFA 是“一个起始状态、一个终止状态、一条带字符的边”，每个字符组件只暴露头尾两个状态，拼接时只动这两个暴露点。这条规则是汤普森构造法不乱的根。

2.2 三个最小件：字符、选择、星号各自的拼法

先看最基础的单字符组件。字符 1 的 NFA 就是两个状态一条边，字符 0 同理。下面表格列出本文用到的全部状态编号和转移关系，状态号从 0 编到 15，一眼能看出哪些状态属于哪个组件。

先造 (0|1) 这个选择件：给 0 的组件分配状态 2、3，给 1 的组件分配状态 4、5。新增一个公共起始状态 6 和一个公共终止状态 7，6 分别用 ε 边连到 2 和 4，3 和 5 分别用 ε 边连到 7。这就是选择的拼法：多进多出变成一头进一头出，暴露头是 6，暴露尾是 7。

再给 (0|1) 套上星号。星号的汤普森规则是：新增包壳起始 8 和包壳终止 9，8 用 ε 连到内部起始 6，8 用 ε 连到 9，内部终止 7 用 ε 连回内部起始 6，7 也用 ε 连到 9。注意这里的 7 到 6 这条 ε 边就是循环的关键，它让内部的 0 和 1 可以反复出现。到这一步，(0|1)* 的 NFA 暴露头是 8，暴露尾是 9，内部状态有 2、3、4、5、6、7。

这里最容易犯的错是把 8 到 9 的 ε 边漏掉。没有这条边，星号就只能匹配“至少一次”，不能匹配零次。1(0|1)*101 中的星号在字符串中间，零次意味着中间没有字符，所以 1101 应该能匹配。这个细节在子集构造时会直接影响初始子集的构成。

2.3 把三块拼起来：1、(0|1)*、101 的连接

剩下两个组件：开头的单个 1，以及结尾的 101。给开头的 1 分配状态 0、1，0 是整体起始，0 用字符 1 连到 1。给 101 的“1-0-1”分配状态 10、11、12、13、14、15：10 用 1 连到 11，11 用 ε 连到 12，12 用 0 连到 13，13 用 ε 连到 14，14 用 1 连到 15，15 是整体终止。

连接操作的本质是“前一个组件的终止状态用 ε 边连到后一个组件的起始状态”。整体是 1 后面接 (0|1)* 再后面接 101，所以：状态 1 用 ε 边连到 8，(0|1)* 的终止状态 9 用 ε 边连到 10。全部拼完后，整个 NFA 的起始状态是 0，终止状态是 15。完整的 NFA 转移关系见下表。

这个表就是后续所有工作的原料。注意 8 和 7 的 ε 转移完全相同，都是指向 6 和 9，这是星号包壳的对称性造成的，不必觉得奇怪。检查 NFA 构造是否正确，可以随机挑一个字符串沿着 ε 边模拟一遍，比如 1101：0 读 1 到 1，沿 ε 到 8，再沿 ε 到 6、9、10，跳过闭包直接沿 ε 到 10 读 1 到 11，ε 到 12 读 0 到 13，ε 到 14 读 1 到 15，到达终止状态。逻辑通顺。

3. 子集构造法：把 NFA 变成 DFA

3.1 ε-闭包怎么算不漏

子集构造法的目标是把“一个状态可能同时在多个 NFA 状态里”的情况变成“DFA 的一个确定状态”。核心操作是 ε-闭包：从一个 NFA 状态集合出发，反复把能通过 ε 边到达的状态加进来，直到集合不再变大。这个过程必须收敛才算完，很多人只算一层就停手，后面的闭包状态没进来，转移表就会错。

从整体起始状态 0 开始：ε-闭包({0}) = {0}，因为状态 0 没有 ε 边，这个闭包非常干净。设 DFA 起始状态 S0 = {0}。

对每个 DFA 状态，分别看输入 0 和 1 时，NFA 能从集合中哪个状态走字符边，再把走到的目标状态的 ε-闭包求出来。以 S0 为例：S0 中只有状态 0，0 只有一条 1 边到 1，所以 S0 在输入 1 时走向 ε-闭包({1})。状态 1 有 ε 边到 8，8 有 ε 边到 6 和 9，6 有 ε 边到 2 和 4，9 有 ε 边到 10，所以这个闭包是 {1, 8, 9, 6, 10, 2, 4}，记为 S1。S0 在输入 0 时没有可走状态，记作空集 Φ。空集暂时不管，最后统一补成死状态。

这里可以验证一个易错点：ε-闭包({1}) 里为什么没有 7？因为从 1 出发，能沿 ε 边到 8，再到 6、9，再到 2、4、10，但走到 7 必须经过 0 边或 1 边，这是不允许的。闭包只看 ε 边，这个边界意识一定要有。

3.2 逐行填子集转移表

接下来就是机械的 BFS：每次出现新的子集，就为它计算 0 和 1 两条转移，直到没有新子集出现。为了不重不漏，把每个子集按出现顺序编号，用纸笔从 S0 开始列。

计算 S1 = {1, 8, 9, 6, 10, 2, 4} 的转移。看集合中每个状态：状态 2 有 0 边到 3；状态 4 和 10 有 1 边，分别到 5 和 11；其他状态只有 ε 边或没有出边。输入 0 时目标集合是 {3}，ε-闭包({3})：3 到 7，7 到 6 和 9，6 到 2 和 4，9 到 10，结果是 {2, 3, 4, 6, 7, 9, 10}，记为 S2。输入 1 时目标集合是 {5, 11}，分别求闭包后合并：5 到 7 再到 6、9、2、4、10，11 到 12，所以结果是 {2, 4, 5, 6, 7, 9, 10, 11, 12}，记为 S3。

继续算 S2 = {2, 3, 4, 6, 7, 9, 10}。输入 0：状态 2 到 3，闭包后还是 S2，所以 S2 输入 0 回到自身。输入 1：状态 4 和 10 分别到 5 和 11，闭包合并后是 S3。

算 S3 = {2, 4, 5, 6, 7, 9, 10, 11, 12}。输入 0：状态 2 到 3，12 到 13。ε-闭包({3, 13}) 里，3 那条链给出 {2, 3, 4, 6, 7, 9, 10}，13 到 14 给出 14，合并成 {2, 3, 4, 6, 7, 9, 10, 13, 14}，记为 S4。输入 1：状态 4 到 5，10 到 11，闭包合并后是 S3，所以 S3 输入 1 回到自身。

算 S4 = {2, 3, 4, 6, 7, 9, 10, 13, 14}。输入 0：只有状态 2 走 0 边到 3，闭包后回到 S2。输入 1：状态 4、10、14 分别走到 5、11、15，ε-闭包({5, 11, 15}) 合并得到 {2, 4, 5, 6, 7, 9, 10, 11, 12, 15}，记为 S5。S5 是新状态，需要继续。

算 S5 = {2, 4, 5, 6, 7, 9, 10, 11, 12, 15}。输入 0：状态 2 和 12 分别到 3 和 13，闭包后是 S4。输入 1：状态 4 和 10 分别到 5 和 11，闭包后是 S3。所有状态都算过了，没有新子集，构造结束。完整转移表如下。

填表时建议画一个队列辅助：每发现新子集就入队，等它出队时算它的转移。用纸笔做的时候，不要把转移结果写在原状态旁边就完事，要单独整理成表格，因为下一步还要对状态分组。

3.3 从子集到等价 DFA：识别接受状态

NFA 的终止状态是 15，因此只要某个 DFA 子集包含 15，它就是接受状态。看表里只有 S5 包含 15，所以 S5 是唯一的接受状态。起始状态是 S0，也就是只包含 NFA 起始状态的集合。

把 Φ 补成一个死状态，让 Φ 在输入 0 和 1 时都回到 Φ。这样转移表才是一个完全的 DFA：每个状态对每个输入符号都有且仅有一个目标。目前这个 DFA 有 6 个状态加 1 个死状态。再检查一遍接受状态的定义：从 S0 出发，输入 1101 后所在状态应该是 S5。S0 --1--> S1 --1--> S3 --0--> S4 --1--> S5，正确落在接受状态。输入 101 时：S0 --1--> S1 --0--> S2 --1--> S3，不在 S5，匹配失败。这个结果和正则式的语义一致。

到这里，“构造正规式1(0|1)*101相应的DFA”的核心工作已经完成了一大半，剩余可以做的优化是状态最小化。先把这张表保存好，因为最小化之后状态会改变命名，原表是验证合并是否正确的重要依据。

4. 最小化 DFA：把六个状态压到五个状态

4.1 为什么要做最小化

子集构造法生成的 DFA 往往包含行为完全相同的状态。所谓行为相同，是指每个输入符号下它们分别去往的状态可以一一对应，最终到达的接受性也一致。这些状态留着不碍事，但会让转移表变大，词法分析器生成器最终生成的表驱动代码也会更长。更重要的是，在很多教材和考题里，最后一步会要求“构造相应的DFA”，隐含的期望就是最小化后的 DFA。

工程上，DFA 状态数和内存占用、构建时间直接相关。虽然 6 个状态和 5 个状态的差别在这里不明显，但同一个方法用在稍复杂的正则式上，状态数可能相差数倍。我一般会在拿到子集构造结果后立刻画一个“哪个状态能到哪个状态”的简表，当场判断哪些可以合并。

4.2 Hopcroft 划分的手算步骤

最小化的经典做法是 Hopcroft 划分，手动操作时可以这样走：先把所有状态按“接受/非接受”分成两组，然后反复检查同一组里的状态是否在所有输入符号下都落到同一组。只要有两个状态在某个输入上跑去不同组，它们就必须拆开。

具体到这个例子，接受状态是 S5，非接受状态是 S0、S1、S2、S3、S4，初始分组是 {S0, S1, S2, S3, S4} 和 {S5}。死状态单独放一边，因为它没有出边，不会被并进任何组。

逐组检查。非接受组里看 S0：它输入 0 去 Φ，而 S1、S2、S3、S4 输入 0 分别去 S2、S2、S4、S2，都不去 Φ，所以 S0 立刻被拆出去。再看 S4：它输入 1 去 S5，而 S1、S2、S3 输入 1 去 S3，目的地不同，S4 也被拆出去。剩下 {S1, S2, S3} 暂时同组。

继续检查 {S1, S2, S3}。S1 输入 0 去 S2，输入 1 去 S3；S2 输入 0 去 S2，输入 1 去 S3；这两个行为完全一致，可以留在一起。S3 输入 0 去 S4，而 S1、S2 输入 0 去 S2，在当前的划分下 S4 已经不是 S1、S2 所在组，所以 S3 被拆出去。最终非接受组拆成 {S0}、{S1, S2}、{S3}、{S4}，接受组是 {S5}，共 5 组。

4.3 本例从 S0..S5 到 T0..T4 的合并

把合并结果重新命名：T0 = {S0} 是起始状态，T1 = {S1, S2}，T2 = {S3}，T3 = {S4}，T4 = {S5} 是接受状态，再加死状态 DEAD。重写转移表时，每个输入符号的目标都要替换成新组名，这一步最容易写错，替换完之后务必回查原表逐格对照。

验证一个字符串：1101 在最小化 DFA 上的路径是 T0 --1--> T1 --1--> T2 --0--> T3 --1--> T4，落在接受状态，和原 DFA 行为一致。再验证 101：T0 --1--> T1 --0--> T1 --1--> T2，非接受，符合预期。合并后的 DFA 状态数从 6 个变 5 个，虽然只省了一个，但整个最小化流程是完整的。考试里这一步通常能拿全部分数。

5. 手算 1(0|1)*101 的 DFA：4 个必翻车点

5.1 ε-闭包漏算：算完一遍就收工

现象：子集转移表里某个状态的输入 0 和输入 1 结果总是少一个状态，导致后面所有闭包都跟着错，最后得到的 DFA 要么接受错误字符串，要么该接受的不接受。

原因：计算 ε-闭包时只沿着 ε 边走了一层。比如 ε-闭包({1}) 只算了 8，没继续算 8 到 6、9，再到 2、4、10，这样 S1 就变成 {1, 8}，后续转移全错。这是手算 NFA 转 DFA 时最高频的错误，没有之一。

解决：闭包必须用“重复直到集合不再增长”的方式算。一个实用技巧是用队列：把新加入的状态入队，处理完队列为空才算完。考试时把这个过程写成集合推导式，宁可多写两步也不要提前收手。

5.2 把星号当成“至少出现一次”

现象：认为 (0|1)* 一定会在字符串里至少出现一次，于是验证时把 1101 判为不合法，或者构造闭包时漏掉“零次”的 ε 边。

原因：星号的含义是“零次或多次”，对应汤普森构造里包壳起始 8 直接 ε 到包壳终止 9 的那条边。手算 NFA 时如果漏了这条边，子集构造的初始闭包里就不会有 9、10 这些状态，后续进入 101 组件的路径全部断开。

解决：造 (0|1)* 时先画两条从包壳起始出发的 ε 边：一条进内部，一条直接到包壳终止。检查时用字符串 1101 验证：中间 (0|1)* 取零次，字符串是 1 后面直接跟 101，应该被接受。任何把 1101 拒绝掉的做法都是星号理解错了。

5.3 忘记补死状态

现象：转移表里某些格子空着，比如 S0 输入 0 没有目标，后续匹配到不该接受的字符串时程序会报 key error 或直接判为接受。

原因：子集构造法在某个输入符号没有可走边时得到空集 Φ，如果不在表格里显式写出 Φ，等价 DFA 就不是一个完全定义的状态机。工程上表驱动的匹配器无法处理空转移格。

解决：把 Φ 作为正式的死状态补进表里，输入 0 和输入 1 都指向自己。最小化时死状态单独一组，永远不要和普通状态合并，否则非接受字符串会被错误接受。

5.4 最小化时看名字，不看行为

现象：两组状态名字看起来很像，比如 S1 和 S2 都包含 2、4、6、9、10，就认为它们等价直接合并；或者因为 S4 和 S5 都是大集合，误以为它们能并在一起。

原因：最小化合并的唯一依据是“在每个输入符号下分别去往的状态属于同一分组”。状态集合是否相似、状态编号是否接近都不重要。S1 和 S2 能合并是因为它们输入 0 都去 S2、输入 1 都去 S3，而不是因为它们共享了 2、4、6、9、10 这些状态编号。

解决：每轮划分严格按转移目标分组。用笔在每组旁边标出每个状态的 (输入0目标, 输入1目标)，只要目标不属于同一组就拆开。合并后逐格回查转移表，确认行为完全镜像才算结束。

6. 写一个 DFA 模拟器：用测试用例钉死正确性

6.1 转移表直接变成字典

最小化后的转移表可以用一个嵌套字典直接表达，这是最直观的验证方式。下面这段 Python 代码把表变成可执行程序，没有任何依赖，任何环境都能跑。

# 最小化后的 DFA 转移表：状态 -> 输入符号 -> 下一状态 trans = { "T0": {"0": "DEAD", "1": "T1"}, "T1": {"0": "T1", "1": "T2"}, "T2": {"0": "T3", "1": "T2"}, "T3": {"0": "T1", "1": "T4"}, "T4": {"0": "T3", "1": "T2"}, "DEAD": {"0": "DEAD", "1": "DEAD"}, } accept_state = "T4" def run_dfa(word: str) -> bool: state = "T0" for ch in word: if ch not in ("0", "1"): return False state = trans[state][ch] return state == accept_state

这段代码的逻辑很简单：起始状态是 T0，每读一个字符就查一次字典，把状态切到下一格，读完整个字符串后判断是否停在接受状态。字典的键是当前状态，值是“字符到下一状态”的映射，和转移表完全一一对应。注意死状态 DEAD 一旦进入就永远出不来，这是它叫“死状态”的原因。如果遇到 0 和 1 以外的字符，直接返回 False，因为正规式 1(0|1)*101 只接受二进制字符集。

6.2 正反用例怎么设计

验证一个 DFA 至少要覆盖三类字符串：能接受的典型串、不能接受的临近串、以及容易误导的空串。下面是这套用例，每一类背后都有一个对应的构造点。

cases = [ ("1101", True), # 星号取零次，最短合法串 ("11101", True), # 星号取一次（1） ("10101", True), # 星号取一次（0） ("110101", True), # 星号取两次（10） ("1110101", True),# 星号取三次（110） ("101", False), # 缺少开头的 1，其实以 1 开头但长度不足 ("110", False), # 结尾不是 101 ("1001", False), # 结尾是 001，不是 101 ("", False), # 空串必拒 ("11011", False), # 结尾是 011，不是 101 ] for word, expected in cases: actual = run_dfa(word) flag = "ok" if actual == expected else "FAIL" print(f"{word:10s} -> {actual} (expect {expected}) [{flag}]")

正例里覆盖了星号取零次、一次、多次的情况，以及 0 和 1 交替出现的情况；反例里覆盖了长度不足、结尾错误、空串三类边界。跑完如果全部输出 ok，说明最小化后的 DFA 行为正确。特别关注 101 这个串：它容易被误当成合法串，原因是人眼看到“1 开头、101 结尾”会下意识认为整个串就是 101，但正规式 1(0|1)*101 的语义决定了 1101 才是最短可接受串。

6.3 从正则式到 NFA 的通用递归构造

验证完这个具体例子，可以把方法泛化成一个递归构造器，让代码代替手工完成前文所有步骤。核心思路是用两个方法：一个负责把子表达式转成 NFA 片段，一个负责按连接、选择、星号三种操作拼接片段。

class NFA: def __init__(self): self.states = set() self.trans = {} # (state, symbol) -> set of states self.start = None self.accept = set() def add_state(self): s = len(self.states) self.states.add(s) self.trans.setdefault((s, "ε"), set()) return s def add_edge(self, src, sym, dst): self.trans.setdefault((src, sym), set()).add(dst) def char_nfa(ch): nfa = NFA() s, t = nfa.add_state(), nfa.add_state() nfa.start, nfa.accept = s, {t} nfa.add_edge(s, ch, t) return nfa def concat(*pieces): first = pieces[0] nfa = first for p in pieces[1:]: for src, sym, dst in p.all_edges(): # 简化伪遍历 nfa.add_edge(src, sym, dst) nfa.add_edge(nfa.accept.pop(), "ε", p.start) nfa.accept = p.accept return nfa def star(piece): nfa = piece s, t = nfa.add_state(), nfa.add_state() nfa.add_edge(s, "ε", nfa.start) nfa.add_edge(s, "ε", t) for acc in nfa.accept: nfa.add_edge(acc, "ε", nfa.start) nfa.add_edge(acc, "ε", t) nfa.start, nfa.accept = s, {t} return nfa

常见的做法是再写一个 union 函数处理选择，然后用子集构造把 NFA 变成 DFA。把转移表打印出来，就能直接当作词法分析器的表驱动部分使用。这就是标题里那道题在真实工程里的落点：编译器词法分析器、正则库的匹配核心、协议解析器里的字段匹配，都是同一套流程。

我以前手算这种题也翻过车，S1 和 S2 合并时看走眼过，后来养成了一个习惯：所有合并和转移都先在白纸上列成表，再用 6.2 节那种用例脚本跑一遍，两分钟就能验证完。自动化模拟器不会放过任何一条手算时漏掉的边。希望这些步骤和踩坑点能帮到你，至少在下次手算 NFA 转 DFA 时少一点玄学、多一点确定性。

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