企业官网建设流程全解析

简介：一份面向编译原理学习者的正规式与有限自动机专题练习文档，聚焦DFA构造、确定化与最小化等核心考点。内容围绕四个典型习题展开：为正规式1(0|1)*101构造相应DFA、完成对图4.16的确定化、对图4.17的最小化，以及设计接收“每个1后紧跟0”的DFA并写出对应正规式与正规文法。文档附有详细参考答案，包含状态转移表、重新命名过程、子集法构造NFA并确定化的步骤，以及最小化时分划等价类的完整推导，适合正在复习编译原理课程、备考研究生入学考试或需要强化自动机理论的读者对照练习与查漏补缺。资源包共1个doc文件，约63KB，内容精炼紧凑，便于直接查阅与打印。已有9900余人学习使用，是一份经过大量读者验证的经典习题解析资料。

1. 构造1(0|1)*101相应的DFA：先搞清楚这个正规式匹配什么

在编译原理的作业里，“构造正规式1(0|1)*101相应的DFA”是一道很经典的题，但也是翻车率很高的一道题。很多人第一眼会把1(0|1)*101理解成“字符串里包含101就通过”，然后画出完全错误的状态图。实际上这个正规式的含义是：整个字符串必须以1开头，并且必须以101结尾，中间的(0|1)*可以吃掉任意多个0或1，甚至可以为空。也就是说，1101可以匹配，101不能匹配，1001也不能匹配。

这道题的难点不在正规式本身有多复杂，而在于从正规式到NFA、再从NFA到DFA的每一步都藏着容易忽略的细节。这篇文章会从语法树拆解开始，手动走完Thompson构造、子集构造法、DFA最小化三步，最后给出一份可以直接抄作业的Python实现。适合正在学《编译原理》自动机部分的学生，也适合需要手工设计词法分析器状态表的从业者。读完你不仅能做出这一道题，还能把整套“正规式转DFA”的流程迁移到其他表达式上。

2. 从正规式到NFA：先把1(0|1)*101拆成状态图

这个环节的目标是把1(0|1)*101变成一个带ε-转移的NFA。NFA允许同一个状态对同一个输入有多个转移，也允许不消费字符就移动，所以它比DFA更容易从正规式直接构造出来。我们后面再通过子集构造法把它转成DFA。

2.1 拆语法树：1、(0|1)*、101三段怎么连接

先按运算符优先级把正规式拆开。1(0|1)*101完整的括号形式是1 ((0|1)*) (1 0 1)，也就是三部分顺序连接：

• 第一部分是单个字符1，要求字符串的第一个字符必须是1。
• 第二部分是(0|1)*，表示任意多个0或1组成的串，可以是空串。
• 第三部分是101，注意它是三个字符连续排列，不是“包含101”这种整体概念。

这个拆法决定了后面NFA的状态划分。1和101是固定字符，各自需要至少一个状态；(0|1)*是一个循环结构，需要允许在任意时候跳出循环进入101的匹配。如果在拆解阶段就理解错了，后面画出来的状态图一定错。

为了验证理解，先手工试几个串：1101由1 + 空 + 101构成，匹配；11101由1 + 1 + 101构成，匹配；101总长度只有3，缺少中间段，不匹配；00101开头不是1，不匹配。记住这几个例子，后面所有步骤都要以它们为准。

2.2 用Thompson构造法画出NFA的每一步

提一个常见的做法：Thompson构造法为每个正规式片段分配一个开始状态和一个接受状态，片段之间用ε-转移连接。这样构造出来的NFA状态多，但结构清晰，而且后面子集构造法能自动消除冗余。

针对1(0|1)*101，我一般会先画一个直观版NFA，状态按“读到了正规式的哪一部分”来命名：

注意S2的ε转移到S3，这是整个NFA的关键点。它表示：在(0|1)*这个循环里的任何一个时刻，NFA都可以“不消费字符”地跳出去，开始匹配后缀101。如果后续字符是1、0、1，就走到S6接受；如果不是，这条路径就自然断掉，不影响其他路径继续在S2绕圈。

用这个NFA走一下匹配1101的路径：S0读1进入S1，S1通过ε进入S2，S2再通过ε进入S3，S3读1进入S4，S4读0进入S5，S5读1进入S6，接受。走11101时，S2里多绕一圈吃掉中间的1，后面的路径一样。这样理解起来比硬记转移表直观得多。

2.3 为什么这里必须用ε-转移

这个正规式的不确定性来自一个真实的选择：读完开头的1之后，下一个字符到底算(0|1)*的一部分，还是算后缀101的第一个字符？在“11101”里，中间那个1是循环部分，而最后的101是后缀；在“1101”里，循环部分为空，第二个字符1直接就是后缀开头。同一个位置，可以是两种身份的字符，NFA必须同时保留两种可能。

ε-转移就是用来表达这种“并行选择”的。不写ε，直接在S2上增加“读1到S4”的转移，也能实现部分效果，但会对(0|1)*的构造造成混乱，尤其是当正规式变成更复杂的嵌套结构时。Thompson构造法统一使用ε，虽然状态多，但每一块的接口是标准的，后面做子集构造时不容易漏掉路径。

3. 用子集构造法把NFA转成DFA：逐步计算与转移表

子集构造法的核心是：把NFA在某个输入符号后的所有可能状态打包成一个集合，这个集合就是DFA的一个状态。因为DFA不允许不确定性，所以它必须一次性记住NFA的“所有当前位置”。

3.1 ε-闭包是第一步：初始状态不是S0，而是S0的闭包

在子集构造法里，每次得到一个新的NFA状态集合后，第一件事是求它的ε-闭包。ε-闭包的定义是：从集合中的每个状态出发，沿着任意条ε-转移能到达的所有状态，加上状态本身。

这个例子的起始状态S0没有ε转移，所以ε-closure({S0})就是{S0}，看起来很简单。但千万别因为简单就跳过这一步。如果正规式以(0|1)*开头，初始闭包会包含很多状态，漏掉一个就会让整个DFA错位。我见过太多人在这一步图省事，直接在纸上写“初态是S0”，结果后续转移表算得越认真错得越远。

计算闭包的工具是用栈或队列做传递闭包。从初始状态S0出发，把所有能通过ε到达的状态都加进来，由于S2有ε到S3，S1有ε到S2，所以闭包往往是多层嵌套的。这个例子恰好初态简单，但S1的闭包就要包含S2和S3。

3.2 逐个算出DFA的7个状态

现在开始正式推演。先给每个DFA状态取一个字母名，避免后面表格写成长串的NFA状态集合。

初始DFA状态A：

A = ε-closure({S0}) = {S0}

从A读0，S0没有0转移，得到空集，记作DEAD。从A读1，得到S1，再对{S1}求ε-闭包：

B = ε-closure({S1}) = {S1, S2, S3}

注意S1的ε到S2，S2的ε到S3，所以闭包一次传递下来成了三个状态。B是DFA中真正开始有动作的状态。

接着从B出发算。B读0时，只有S2能通过0到S2，所以：

C = ε-closure({S2}) = {S2, S3}

B读1时，S2通过1到S2，S3通过1到S4，所以：

D = ε-closure({S2, S4}) = {S2, S3, S4}

然后算C。C读0，还是S2到S2，闭包仍是{S2,S3}，所以C读0回C。C读1，S2到S2，S3到S4，所以得到D。D读0时，S2到S2，S4到S5，闭包得到：

E = {S2, S3, S5}

D读1时，S2到S2，S3到S4，S4没有1转移，所以回到D。E读0时，S2到S2，S5没有0转移，闭包回到C。E读1时，S2到S2，S3到S4，S5到S6，闭包得到：

F = {S2, S3, S4, S6}

从F出发：F读0，S2到S2，S4到S5，得到E；F读1，S2到S2，S3到S4，得到D。至此所有状态都闭合了。完整的DFA转移表如下：

这个表就是子集构造法的直接产物。可以看到，接受状态只有F，因为它包含NFA的接受状态S6。走一遍“1101”：A读1到B，B读1到D，D读0到E，E读1到F，接受，和手工分析一致。

3.3 用Python验证子集构造法的结果

手工算完一定要用代码验证，尤其是初学阶段，纸上的闭包特别容易漏。下面这段Python实现可以直接跑，输入NFA状态转移表和ε转移表，输出DFA状态和转移关系。

# NFA转移表：trans[state][symbol] = 目标状态集合 trans = { 0: {'1': {1}}, 1: {}, 2: {'0': {2}, '1': {2}}, 3: {'1': {4}}, 4: {'0': {5}}, 5: {'1': {6}}, 6: {}, } # ε转移表：eps[state] = 通过ε直接到达的状态集合 eps = { 1: {2}, 2: {3}, } def eps_closure(states, eps): stack = list(states) cl = set(states) while stack: s = stack.pop() for t in eps.get(s, []): if t not in cl: cl.add(t) stack.append(t) return cl def move(states, symbol, trans): nxt = set() for s in states: nxt |= trans.get(s, {}).get(symbol, set()) return nxt def subset_construct(trans, eps, alphabet, start, accept): start_set = frozenset(eps_closure({start}, eps)) dfa_states = [start_set] worklist = [start_set] dfa_trans = {} while worklist: cur = worklist.pop() for symbol in alphabet: nxt = frozenset(eps_closure(move(cur, symbol, trans), eps)) if nxt not in dfa_states: dfa_states.append(nxt) worklist.append(nxt) dfa_trans[(cur, symbol)] = nxt accepting = [s for s in dfa_states if accept in s] return dfa_states, dfa_trans, accepting states, tbl, acc = subset_construct(trans, eps, ['0', '1'], 0, 6) for i, s in enumerate(states): row = [states.index(tbl[(s, ch)]) for ch in ['0', '1']] print(f"状态{i}: {sorted(s)} 读0->{row[0]} 读1->{row[1]} 接受={s in acc}")

这段代码里，eps_closure用栈实现传递闭包，保证S1能一路闭包到S3。move只做一步输入转移，不处理ε，所以每次构造新状态后必须立即再求一次闭包。这是整个子集构造法的核心顺序：move一次，closure一次。如果代码输出的状态编号和手算顺序不同，不用慌，只要转移关系一致、接受状态正确即可，顺序取决于栈的弹出顺序。

4. DFA最小化：把7个状态合并成6个，去掉等价状态

子集构造法得到的DFA通常不是最小的，里面有些状态行为完全相同，可以合并。真正投入词法分析器之前，最小化这步值得做，因为状态越少，转移表越小，运行时缓存命中率也越高。这个例子只合并了一个状态，但流程是完整的。

4.1 为什么要做最小化：等价状态的判据

两个DFA状态等价，意味着从它们出发，对任意输入串都会得到相同的接受/拒绝结果。判断方法是从接受状态和非接受状态的划分开始，逐步细分组内迁入目标所属的组。这个算法叫划分细化，也叫Hopcroft算法的简化版。

在这个DFA里，接受状态只有F，其他状态都不接受，所以初始划分一定是{F} 和 {A,B,C,D,E,DEAD}两组。这一步看似简单，但很多人一开始把接受状态和非接受状态混在一起，后面的迭代就全乱。记住：接受性不同的状态永远不可能等价。

4.2 划分法三轮迭代：逐步把状态拆开

初始划分P0：

P0 = {F} + {A, B, C, D, E, DEAD}

第一次迭代，看每个非接受状态在输入0和输入1时分别落到哪一组。关键差异在E：E读1进入F（接受组），而其他非接受状态读1都落在非接受组。因此E必须单独拆出来：

P1 = {F} + {E} + {A, B, C, D, DEAD}

第二次迭代，再看{A,B,C,D,DEAD}这一组。D读0进入E，而E已经不在这个组里，所以D和别人不一样，拆出来：

P2 = {F} + {E} + {D} + {A, B, C, DEAD}

第三次迭代，观察{A,B,C,DEAD}。A读1到B，B读1到D，C读1到D，DEAD读1到DEAD。B和C的读1目标都是D（当前单独组），而A读1到B（还在本组），DEAD读1到DEAD（还在本组），所以B和C可以抱团，A和DEAD不能和他们混在一起：

P3 = {F} + {E} + {D} + {B, C} + {A} + {DEAD}

再检查{B,C}：B读0到C，读1到D；C读0到C，读1到D，行为完全一致，不再分裂。{A}和{DEAD}内部都只有一个状态，自然稳定。最终划分就是6组，比原来的7个状态少了一个。

4.3 最小化后的DFA长什么样

把{B,C}合并成一个新状态G，得到最小化DFA：

这个DFA比原始表少一个状态，但接受的语言完全一致。G的含义是“既能继续循环，又能随时开始匹配后缀”，它把原先B和C这两个表现相同的状态收敛成了一个。以后写词法分析器时，状态名可以直接用这里的字母，转移表就是一份标准的驱动表。

5. 构造1(0|1)*101的DFA时最容易踩的5个坑

这一节把从正规式到DFA全过程中最常见的坑集中列出来。每条都是“现象 → 原因 → 解决”的结构，照着排查能省很多时间。

5.1 把“1(0|1)*101”理解成“包含101”

现象：构造出来的DFA能接受0101、00101这类不以1开头的串。 原因：把正规式看成了(0|1)*101，忽略了最前面的固定1；或者把连接关系理解成“串中某个位置出现101即可”。 解决：第一步就拆语法树，明确是三段连接：1、(0|1)*、101。状态S1专门用来消费开头的1，不存在从起始状态直接进入循环的可能。

5.2 子集构造时漏算ε-闭包的传递性

现象：手算时把ε-closure({S1})写成{S1,S2}，少了S3，导致后续所有状态都不对。 原因：漏掉了“闭包的闭包”这种传递关系。S1到S2，S2又到S3，闭包必须一直传递到没有新状态为止。 解决：用栈或队列实现传递闭包，先把种子状态入栈，每弹出一个状态就加入它的ε目标，直到栈空。这个过程宁可多算几轮，也不要只算一层。

5.3 只算move不算closure，或者顺序反了

现象：从某个DFA状态读入字符后，直接把move结果当作新状态，比如把{S2}当成C，而没有扩展成{S2,S3}。 原因：move返回的是NFA消耗一个字符后到达的状态，但NFA随后还能不消耗字符继续移动，必须再求一次ε-闭包。 解决：记住固定顺序：先move，再closure。任何一次生成新DFA状态，都要完整做这两步。这也是3.3代码里subset_construct的核心模式。

5.4 最小化时初始划分把接受态和非接受态混在一起

现象：最小化结果不稳定，迭代好几轮还在分裂，或者合并了不该合并的状态。 原因：初始划分把F和其他状态放进了同一个组，等价性判据从第一步就错了。 解决：强制先分成两组：接受状态一组，非接受状态一组。之后再按转移目标所在组分裂。这个原则对所有DFA最小化都适用，不是这一道题的特例。

5.5 不画死状态，导致转移表有空洞

现象：转移表里某个状态缺了某个输入的转移，例如从A读0没有定义，实际模拟时程序直接报错或返回错误结果。 原因：DFA要求转移函数是完整的，每个状态对每个输入都必须有下一个状态。子集构造法产生的空集本身就是一个状态。 解决：把空集命名为DEAD，所有缺失的转移都显式指向DEAD。注意DEAD自己也必须有到DEAD的转移，否则它也会变成“空洞”。最小化后也要重新检查一遍，确保状态表是一张完整的方阵。

6. 把这个DFA做成可用的词法分析器：模拟器与验证技巧

最后一步，把最小化后的DFA落地成能跑的代码。这一节给出一个可直接复制的DFA模拟器，以及一套随机对比验证方法，避免手工状态表写错。

6.1 用Python直接模拟最小化DFA

# 最小化后的DFA转移表 transition = { 'A': {'0': 'DEAD', '1': 'G'}, 'G': {'0': 'G', '1': 'D'}, 'D': {'0': 'E', '1': 'D'}, 'E': {'0': 'G', '1': 'F'}, 'F': {'0': 'E', '1': 'D'}, 'DEAD': {'0': 'DEAD', '1': 'DEAD'}, } start_state = 'A' accept_states = {'F'} def match_dfa(s): state = start_state for ch in s: if ch not in ('0', '1'): return False state = transition[state][ch] if state == 'DEAD': return False return state in accept_states

这个模拟器的逻辑很简单：从A开始，逐个字符查表跳转，一旦进入DEAD直接判失败，最后只要停在F就接受。需要改匹配其他正规式时，只需要替换transition表、起始状态和接受状态集合，模拟函数本身不用动。代码里对非0/1字符提前返回False，是因为词法分析器通常还要处理其他符号，这里是先把输入限制在字母表内。

6.2 用随机测试反向验证DFA

手算的转移表再小心也难免出错，最有效的后悔药是拿随机串和标准正则引擎对拍。Python的re模块足够用来验证这个正规式。

import random import re pattern = re.compile(r'1(0|1)*101') def random_binary_string(length): return ''.join(random.choice('01') for _ in range(length)) for _ in range(10000): s = random_binary_string(random.randint(0, 12)) expected = pattern.fullmatch(s) is not None actual = match_dfa(s) if expected != actual: print(f"不一致: {s!r} 正则期望={expected} DFA结果={actual}") break else: print("10000个随机串全部一致")

跑出来的不一致几乎都是因为DFA写错，很少是正则引擎的问题。如果你改动了状态表，记得把随机串长度上限提高一些，字符串越长越容易覆盖深层状态组合。还可以在固定串测试里特别带上边界用例：1101必须接受，101必须拒绝，11101必须接受，00101必须拒绝。

6.3 从状态表到词法分析器：表驱动与状态压缩

模拟器是词法分析器的最小原型。实际生产里，会把transition表压成二维数组，行是DFA状态编号，列是输入字符编号，值直接存下一行编号。这样可以去掉字典查找开销，配合状态机和输入缓冲，就是标准的表驱动词法分析器。更进一步，可以在最小化时记录每个状态对应的“接受的Token类型”，让一个DFA同时识别多个关键字，而不是每个正规式单独建一台DFA。

我个人的习惯是：做完一版DFA，先花十分钟写随机对拍脚本，再拿边界串手跑一遍。这个习惯在写过几次复杂的正规式之后，帮我避免了至少三处状态表笔误。希望帮到你。

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