*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 和一个公共终止状态 76 分别用 ε 边连到 2 和 43 和 5 分别用 ε 边连到 7。这就是选择的拼法多进多出变成一头进一头出暴露头是 6暴露尾是 7。再给 (0|1) 套上星号。星号的汤普森规则是新增包壳起始 8 和包壳终止 98 用 ε 连到内部起始 68 用 ε 连到 9内部终止 7 用 ε 连回内部起始 67 也用 ε 连到 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、10 是整体起始0 用字符 1 连到 1。给 101 的“1-0-1”分配状态 10、11、12、13、14、1510 用 1 连到 1111 用 ε 连到 1212 用 0 连到 1313 用 ε 连到 1414 用 1 连到 1515 是整体终止。连接操作的本质是“前一个组件的终止状态用 ε 边连到后一个组件的起始状态”。整体是 1 后面接 (0|1)* 再后面接 101所以状态 1 用 ε 边连到 8(0|1)* 的终止状态 9 用 ε 边连到 10。全部拼完后整个 NFA 的起始状态是 0终止状态是 15。完整的 NFA 转移关系见下表。NFA状态ε 转移0 转移1 转移0——118——2—3—37——4——557——62, 4——76, 9——86, 9——910——10——111112——12—13—1314——14——1515———这个表就是后续所有工作的原料。注意 8 和 7 的 ε 转移完全相同都是指向 6 和 9这是星号包壳的对称性造成的不必觉得奇怪。检查 NFA 构造是否正确可以随机挑一个字符串沿着 ε 边模拟一遍比如 11010 读 1 到 1沿 ε 到 8再沿 ε 到 6、9、10跳过闭包直接沿 ε 到 10 读 1 到 11ε 到 12 读 0 到 13ε 到 14 读 1 到 15到达终止状态。逻辑通顺。3. 子集构造法把 NFA 变成 DFA3.1 ε-闭包怎么算不漏子集构造法的目标是把“一个状态可能同时在多个 NFA 状态里”的情况变成“DFA 的一个确定状态”。核心操作是 ε-闭包从一个 NFA 状态集合出发反复把能通过 ε 边到达的状态加进来直到集合不再变大。这个过程必须收敛才算完很多人只算一层就停手后面的闭包状态没进来转移表就会错。从整体起始状态 0 开始ε-闭包({0}) {0}因为状态 0 没有 ε 边这个闭包非常干净。设 DFA 起始状态 S0 {0}。对每个 DFA 状态分别看输入 0 和 1 时NFA 能从集合中哪个状态走字符边再把走到的目标状态的 ε-闭包求出来。以 S0 为例S0 中只有状态 00 只有一条 1 边到 1所以 S0 在输入 1 时走向 ε-闭包({1})。状态 1 有 ε 边到 88 有 ε 边到 6 和 96 有 ε 边到 2 和 49 有 ε 边到 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 到 77 到 6 和 96 到 2 和 49 到 10结果是 {2, 3, 4, 6, 7, 9, 10}记为 S2。输入 1 时目标集合是 {5, 11}分别求闭包后合并5 到 7 再到 6、9、2、4、1011 到 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 到 312 到 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 到 510 到 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。所有状态都算过了没有新子集构造结束。完整转移表如下。DFA状态NFA状态集合输入0输入1S0{0}ΦS1S1{1, 8, 9, 6, 10, 2, 4}S2S3S2{2, 3, 4, 6, 7, 9, 10}S2S3S3{2, 4, 5, 6, 7, 9, 10, 11, 12}S4S3S4{2, 3, 4, 6, 7, 9, 10, 13, 14}S2S5S5{2, 4, 5, 6, 7, 9, 10, 11, 12, 15}S4S3填表时建议画一个队列辅助每发现新子集就入队等它出队时算它的转移。用纸笔做的时候不要把转移结果写在原状态旁边就完事要单独整理成表格因为下一步还要对状态分组。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 去 S3S2 输入 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。重写转移表时每个输入符号的目标都要替换成新组名这一步最容易写错替换完之后务必回查原表逐格对照。最小化状态原状态输入0输入1是否接受T0{S0}DEADT1否T1{S1, S2}T1T2否T2{S3}T3T2否T3{S4}T1T4否T4{S5}T3T2是DEAD{Φ}DEADDEAD否验证一个字符串1101 在最小化 DFA 上的路径是 T0 --1-- T1 --1-- T2 --0-- T3 --1-- T4落在接受状态和原 DFA 行为一致。再验证 101T0 --1-- T1 --0-- T1 --1-- T2非接受符合预期。合并后的 DFA 状态数从 6 个变 5 个虽然只省了一个但整个最小化流程是完整的。考试里这一步通常能拿全部分数。5. 手算 1(0|1)*101 的 DFA4 个必翻车点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 时少一点玄学、多一点确定性。本文还有配套的精品资源点击获取 
长河君 · 2026/10/13 4:21:59 · 阅读 1.2k 正则表达式转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 和一个公共终止状态 76 分别用 ε 边连到 2 和 43 和 5 分别用 ε 边连到 7。这就是选择的拼法多进多出变成一头进一头出暴露头是 6暴露尾是 7。再给 (0|1) 套上星号。星号的汤普森规则是新增包壳起始 8 和包壳终止 98 用 ε 连到内部起始 68 用 ε 连到 9内部终止 7 用 ε 连回内部起始 67 也用 ε 连到 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、10 是整体起始0 用字符 1 连到 1。给 101 的“1-0-1”分配状态 10、11、12、13、14、1510 用 1 连到 1111 用 ε 连到 1212 用 0 连到 1313 用 ε 连到 1414 用 1 连到 1515 是整体终止。连接操作的本质是“前一个组件的终止状态用 ε 边连到后一个组件的起始状态”。整体是 1 后面接 (0|1)* 再后面接 101所以状态 1 用 ε 边连到 8(0|1)* 的终止状态 9 用 ε 边连到 10。全部拼完后整个 NFA 的起始状态是 0终止状态是 15。完整的 NFA 转移关系见下表。NFA状态ε 转移0 转移1 转移0——118——2—3—37——4——557——62, 4——76, 9——86, 9——910——10——111112——12—13—1314——14——1515———这个表就是后续所有工作的原料。注意 8 和 7 的 ε 转移完全相同都是指向 6 和 9这是星号包壳的对称性造成的不必觉得奇怪。检查 NFA 构造是否正确可以随机挑一个字符串沿着 ε 边模拟一遍比如 11010 读 1 到 1沿 ε 到 8再沿 ε 到 6、9、10跳过闭包直接沿 ε 到 10 读 1 到 11ε 到 12 读 0 到 13ε 到 14 读 1 到 15到达终止状态。逻辑通顺。3. 子集构造法把 NFA 变成 DFA3.1 ε-闭包怎么算不漏子集构造法的目标是把“一个状态可能同时在多个 NFA 状态里”的情况变成“DFA 的一个确定状态”。核心操作是 ε-闭包从一个 NFA 状态集合出发反复把能通过 ε 边到达的状态加进来直到集合不再变大。这个过程必须收敛才算完很多人只算一层就停手后面的闭包状态没进来转移表就会错。从整体起始状态 0 开始ε-闭包({0}) {0}因为状态 0 没有 ε 边这个闭包非常干净。设 DFA 起始状态 S0 {0}。对每个 DFA 状态分别看输入 0 和 1 时NFA 能从集合中哪个状态走字符边再把走到的目标状态的 ε-闭包求出来。以 S0 为例S0 中只有状态 00 只有一条 1 边到 1所以 S0 在输入 1 时走向 ε-闭包({1})。状态 1 有 ε 边到 88 有 ε 边到 6 和 96 有 ε 边到 2 和 49 有 ε 边到 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 到 77 到 6 和 96 到 2 和 49 到 10结果是 {2, 3, 4, 6, 7, 9, 10}记为 S2。输入 1 时目标集合是 {5, 11}分别求闭包后合并5 到 7 再到 6、9、2、4、1011 到 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 到 312 到 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 到 510 到 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。所有状态都算过了没有新子集构造结束。完整转移表如下。DFA状态NFA状态集合输入0输入1S0{0}ΦS1S1{1, 8, 9, 6, 10, 2, 4}S2S3S2{2, 3, 4, 6, 7, 9, 10}S2S3S3{2, 4, 5, 6, 7, 9, 10, 11, 12}S4S3S4{2, 3, 4, 6, 7, 9, 10, 13, 14}S2S5S5{2, 4, 5, 6, 7, 9, 10, 11, 12, 15}S4S3填表时建议画一个队列辅助每发现新子集就入队等它出队时算它的转移。用纸笔做的时候不要把转移结果写在原状态旁边就完事要单独整理成表格因为下一步还要对状态分组。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 去 S3S2 输入 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。重写转移表时每个输入符号的目标都要替换成新组名这一步最容易写错替换完之后务必回查原表逐格对照。最小化状态原状态输入0输入1是否接受T0{S0}DEADT1否T1{S1, S2}T1T2否T2{S3}T3T2否T3{S4}T1T4否T4{S5}T3T2是DEAD{Φ}DEADDEAD否验证一个字符串1101 在最小化 DFA 上的路径是 T0 --1-- T1 --1-- T2 --0-- T3 --1-- T4落在接受状态和原 DFA 行为一致。再验证 101T0 --1-- T1 --0-- T1 --1-- T2非接受符合预期。合并后的 DFA 状态数从 6 个变 5 个虽然只省了一个但整个最小化流程是完整的。考试里这一步通常能拿全部分数。5. 手算 1(0|1)*101 的 DFA4 个必翻车点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 时少一点玄学、多一点确定性。本文还有配套的精品资源点击获取