正则表达式与NFA自动机：从Thompson构造到子集构造的Python实现

正则表达式和自动机的关系，很多人学完一遍语法规则就翻篇了，觉得这两样东西八竿子打不着——一个是写代码时用来匹配字符串的工具，一个是编译原理课上画状态圆圈箭头的理论模型。可真到了要手写一个词法分析器、或者要判断某条正则到底会不会回溯爆炸的时候，才会发现绕不开自动机这套底层机制。这篇内容就是把我自己在啃这块内容时踩过的坑、想通的关节整理出来，重点放在**非确定有限自动机（NFA）**和正则表达式之间的相互转换上，顺带把 Python 里怎么落地验证也讲清楚。

适合谁看：已经会写基本正则、想搞清楚"为什么这条正则能匹配"的人；正在学编译原理或形式语言、被 NFA 到 DFA 的转换绕晕的人；以及想用 Python 手动实现一个简易正则引擎、不想只当调包侠的人。下面所有内容都围绕"正则表达式如何等价地表示成一个非确定有限自动机"这条主线展开，中间穿插 Python 实现和实测经验。

1. 为什么正则表达式背后一定要有自动机

1.1 从"匹配"这件事的本质说起

先抛开所有语法糖，问一个朴素的问题：正则表达式到底在干什么？它其实是在描述一个字符串集合。比如a(b|c)*d描述的就是"以 a 开头、中间是任意多个 b 或 c、以 d 结尾"的所有字符串。这个集合可能是无限的，但你用有限长度的表达式就把它说清楚了。

既然正则描述的是集合，那"判断某个字符串是否属于这个集合"就是一个可计算的问题。而有限自动机恰恰就是描述"有限状态、逐字符读入、最后看落在哪个状态"的计算模型。它俩能对上，不是巧合，而是因为它们描述的是同一类语言——正则语言。这个结论有个很硬的名字叫Kleene 定理：一个语言是正则的，当且仅当它能被某个有限自动机识别，当且仅当它能用正则表达式表示。三者等价。

理解这一点很关键。它意味着你写下的每一条正则，理论上都能机械地翻译成一台自动机；反过来，每一台有限自动机也都能写回一条正则。这不是玄学，是有构造性证明的——证明过程本身就是一套可执行的算法，后面几节我会把这套算法拆开讲。

1.2 确定与非确定：一字之差，天壤之别

有限自动机分两种：确定有限自动机（DFA）和非确定有限自动机（NFA）。DFA 的特点是：在任何状态下读入任何字符，下一个状态是唯一确定的。NFA 则允许两种"不确定"：一是同一个状态读同一个字符可以跳到多个后继状态；二是允许不读入任何字符就跳转，也就是所谓的ε 转移（空转移）。

直觉上 NFA 比 DFA "强"，因为它能同时走多条路。但 Kleene 定理的另一半告诉我们：NFA 和 DFA 识别能力完全等价，任何 NFA 都能转成等价的 DFA。那为什么还要区分？因为表达便利性不同。用 NFA 去对应正则的构造极其自然——正则里的|对应分支，*对应回路，ε对应可选，几乎是一一映射。而 DFA 虽然跑起来快（每个字符一步，无回溯），但直接构造很别扭。所以工程上的标准套路是：正则 → NFA（Thompson 构造）→ DFA（子集构造）→ 最小化 → 执行。这条流水线是几乎所有正则引擎（包括 Python 的re模块底层思路）的骨架。

提示：Python 的re模块实际用的是回溯式引擎，并不严格走 NFA→DFA 这条路，但理解自动机模型对判断回溯风险和写高效正则有直接帮助，后面第 4 节会专门讲这个关联。

1.3 一个容易混淆的点：NFA 的"非确定"不是随机

初学最容易误解的地方：看到 NFA 一个状态能跳到多个后继，就以为它是"随机选一条路试试"。不是的。NFA 的接受语义是存在性——只要存在至少一条路径能读完整个串并停在接受状态，这个串就被接受。它本质上是"并行地走所有可能的路"，而不是"赌一条路"。这个语义差异在实现时非常关键：如果你用递归去模拟 NFA，遇到分支必须两个分支都试，任何一个成功即整体成功，而不是随便挑一个。

我用一个具体例子说明。考虑正则ab|ac，对应的 NFA 从起始状态读a之后会分叉到两条路，一条等b、一条等c。输入ac时，走b那条路会失败，但走c那条路成功，所以整体接受。如果实现时错误地"只走第一条分支"，就会把ac误判为拒绝。这个坑我在第一次手写 NFA 模拟器时结结实实踩过，调试了半天才发现是分支处理写成了"短路返回第一个结果"而不是"任一成功即成功"。

2. Thompson 构造：把正则拆成自动机积木

2.1 构造的核心思想：每个正则片段都是一台小机器

Thompson 构造的精髓在于递归组合。它不去想"整条正则对应什么大自动机"，而是规定：任何一个正则子表达式，都对应一台有唯一入口和唯一出口的小 NFA。然后按正则的语法结构，把这些小机器拼起来。因为每个片段都是"单入单出"，拼接时只需要把出口和入口用 ε 转移连起来，不用担心状态混乱。

具体来说，基本片段只有几种：

这张表就是整个构造的全部"积木"。你写正则时用的()、|、*、+、?，全都能归约到这几种基本组合。R+等价于RR*，R?等价于R|ε，所以不用单独处理。

2.2 用 Python 把积木搭起来

光看表不够，得动手。下面是我实际用的一套简化实现，核心是给每个片段分配两个状态编号（入口、出口），然后用邻接表存转移。转移用(字符, 目标状态)表示，字符为None代表 ε 转移。

class NFA: def __init__(self): self.trans = {} # state -> list of (char_or_None, next_state) self.start = None self.accept = None self._counter = 0 def new_state(self): s = self._counter self._counter += 1 self.trans[s] = [] return s def add_edge(self, src, ch, dst): self.trans[src].append((ch, dst))

有了这个骨架，单字符片段就是：

def build_char(nfa, ch): s, e = nfa.new_state(), nfa.new_state() nfa.add_edge(s, ch, e) return s, e

连接两个片段，就是把前一个的出口用 ε 连到后一个的入口：

def build_concat(nfa, frag1, frag2): s1, e1 = frag1 s2, e2 = frag2 nfa.add_edge(e1, None, s2) return s1, e2

选择片段需要新建入口和出口，入口 ε 分叉到两个子片段入口，两个子片段出口 ε 汇到新出口：

def build_alt(nfa, frag1, frag2): s, e = nfa.new_state(), nfa.new_state() s1, e1 = frag1 s2, e2 = frag2 nfa.add_edge(s, None, s1) nfa.add_edge(s, None, s2) nfa.add_edge(e1, None, e) nfa.add_edge(e2, None, e) return s, e

闭包片段同理，入口可以跳过、出口可以回跳：

def build_star(nfa, frag): s, e = nfa.new_state(), nfa.new_state() s1, e1 = frag nfa.add_edge(s, None, s1) # 进入子片段 nfa.add_edge(s, None, e) # 直接跳过（匹配零次） nfa.add_edge(e1, None, s1) # 回到子片段入口（再来一次） nfa.add_edge(e1, None, e) # 结束 return s, e

这套代码跑通之后，你会发现一个有意思的现象：状态数会膨胀得很快。一条中等复杂度的正则，Thompson 构造出来的 NFA 状态数大概是正则长度的两三倍。这不是实现问题，是构造本身的特性——每个操作符都要额外加状态。所以后面子集构造转 DFA 时，状态爆炸的风险是真实存在的，不是危言耸听。

2.3 构造过程中的两个实操细节

第一个细节：ε 转移的传递性。构造出来的 NFA 里，ε 转移可能连成链，比如状态 1 ε→ 2 ε→ 3。在模拟执行时，从状态 1 出发，实际上"同时"处于 1、2、3 三个状态。所以任何 NFA 模拟器都必须实现一个ε 闭包（epsilon closure）函数：给定一个状态集合，返回所有通过任意条 ε 转移能到达的状态集合。这个函数是 NFA 模拟的心脏，写错了整个匹配就全错。

def epsilon_closure(nfa, states): stack = list(states) closure = set(states) while stack: s = stack.pop() for ch, nxt in nfa.trans.get(s, []): if ch is None and nxt not in closure: closure.add(nxt) stack.append(nxt) return closure

第二个细节：片段拼接时的状态复用。上面代码里build_concat直接复用了两个片段的入口出口，没有新建状态，这是对的。但如果你在实现时图省事，每个操作都新建状态再连 ε，状态数会进一步膨胀，而且容易连出冗余的 ε 环。我的经验是：能复用就复用，只在选择、闭包这类真正需要"分叉/汇合"的地方新建状态。这样构造出来的 NFA 更紧凑，后续转 DFA 时也少受罪。

3. 子集构造：把 NFA 压成 DFA

3.1 为什么需要这一步，以及它的代价

NFA 跑起来要维护一个状态集合，每个字符都要对集合里所有状态做转移再求 ε 闭包，慢且实现复杂。DFA 则简单粗暴：一个当前状态，读一个字符跳一步，O(n) 时间搞定。所以工程上愿意花一次性成本把 NFA 转成 DFA，换取运行时的极致效率。

子集构造的核心洞察是：NFA 在某一时刻"可能处于的状态集合"，恰好可以作为 DFA 的一个状态。因为 NFA 读入一个字符后，新的可能状态集合完全由旧集合和这个字符决定，是确定的。于是 DFA 的每个状态就是一个 NFA 状态集合（子集），转移函数就是"对集合里每个状态按字符转移、再求 ε 闭包"。

代价是什么？DFA 的状态数最坏情况下是 2 的 NFA 状态数次方。虽然实际中很少达到最坏，但状态爆炸确实会发生。我实测过一条带多个可选分支的正则，NFA 只有二十来个状态，转出来的 DFA 却有上百个状态。所以真实引擎里通常会有"按需构造"的优化——用到哪个 DFA 状态才生成哪个，而不是一次性全展开。

3.2 手写子集构造的完整流程

流程分四步，我用伪代码加注释的方式讲清楚：

1. 计算起始状态集合：start_set = epsilon_closure({nfa.start})，这是 DFA 的初始状态。
2. 维护一个待处理队列，初始只有start_set；同时维护一个映射dfa_state -> set记录已生成的 DFA 状态。
3. 从队列取出一个集合，对字母表中每个字符 c，计算move(set, c)再求 ε 闭包，得到新集合。如果新集合没出现过，加入映射和队列，并记录一条 DFA 转移。
4. 重复直到队列空。任何包含 NFA 接受状态的集合，都标记为 DFA 的接受状态。

move函数的实现很直接：

def move(nfa, states, ch): result = set() for s in states: for c, nxt in nfa.trans.get(s, []): if c == ch: result.add(nxt) return result

然后对结果求epsilon_closure就得到新集合。整个循环写下来不到三十行，但调试时要注意：字母表要显式定义。NFA 里出现过的所有非 ε 字符构成字母表，遍历时必须按这个字母表走，不能漏字符，否则会少生成转移，导致 DFA 不完整。

3.3 一个具体例子走一遍

拿正则(a|b)*abb举例（这是编译原理教材里的经典例子，我这里用自己的话重走一遍）。Thompson 构造出的 NFA 有若干状态，起始集合经过 ε 闭包后包含多个状态。读入a后，集合会变化；读入b后，集合又变化。一路走下来，你会发现 DFA 的状态其实对应着"当前已经匹配到abb的哪个前缀"——这正是自动机在做模式识别的直观体现。

这个例子值得亲手画一遍。我的建议是：拿张纸，把 NFA 的每个状态编号，然后老老实实按子集构造一步步算，别偷懒用工具。算完再和工具结果对，对不上的地方就是理解有偏差的地方。我第一次算的时候在 ε 闭包上漏了一个状态，导致后面整条链都错了，回头查了半天才发现是某个状态的 ε 出边没算进去。

4. 自动机视角怎么帮你写出更好的正则

4.1 回溯爆炸的本质：NFA 模拟的低效路径

Python 的re用的是回溯引擎，本质上是深度优先地模拟 NFA。遇到a*这种贪婪量词，它会先尽量多吞字符，吞不动了再一个个吐回来试。遇到嵌套量词比如(a+)+b，回溯路径会指数级增长——这就是所谓的灾难性回溯（catastrophic backtracking）。

从自动机角度看，问题出在哪？NFA 的语义是"并行走所有路"，但回溯引擎是"串行走，走不通再退回来换一条"。当分支极多时，串行枚举所有路径的代价就是指数级的。而如果先把 NFA 转成 DFA，每个字符只有一条确定的路，根本不存在回溯，最坏也是线性时间。这就是为什么有些场景下"预编译成 DFA"能救命。

实测一个典型例子：正则(a|a)*b匹配一长串a后跟一个非b字符，回溯引擎会尝试 2 的 n 次方条路径。我用 Python 试过，二十几个a就能让匹配卡住好几秒。而同样的模式如果转成 DFA 执行，瞬间出结果。这个对比不是让你抛弃re，而是让你知道：当你写出带嵌套量词的正则时，脑子里要有一台 NFA 在并行分叉的画面，从而警惕路径爆炸。

4.2 从自动机结构反推正则写法

理解了 NFA 结构，写正则时会有几个反直觉但很实用的习惯：

• 能确定就别留分支。[abc]比(a|b|c)好，因为前者在自动机里是单条边带字符集，后者是三条 ε 分叉。字符集在 NFA 里不增加状态，分支会增加。
• 量词尽量贴着具体字符。a*的自动机结构比(a)*简单，后者多了一层 ε 包裹，虽然语义一样，但状态更多、回溯路径更长。
• 避免.*后面紧跟另一个.*。两个贪婪星号叠加，自动机里就是两层回路嵌套，回溯时组合爆炸。真需要跨段匹配，用非贪婪.*?或者更精确的字符类约束。

这些习惯不是背规则背出来的，是看着 NFA 图想明白的。我建议每个学正则的人至少手画一次(a|b)*abb的 NFA 和 DFA，画完你对"为什么这条正则慢"会有肌肉记忆级的判断力。

4.3 Python 里验证自动机行为的土办法

没有现成的自动机可视化工具时，我常用一个笨办法验证自己的理解：用 NFA 模拟器跑测试串，打印每一步的状态集合。状态集合的变化轨迹，就是自动机在"思考"的过程。如果某一步集合突然变空，说明这个字符走不通了；如果最终集合包含接受状态，就是匹配成功。

def nfa_match(nfa, text): current = epsilon_closure(nfa, {nfa.start}) for ch in text: current = epsilon_closure(nfa, move(nfa, current, ch)) if not current: return False return nfa.accept in current

这段代码不到十行，但它把 NFA 的语义表达得清清楚楚：当前可能状态集合、逐字符转移、ε 闭包、最终看是否含接受态。把它和re.fullmatch的结果对拍，能快速发现构造或模拟里的 bug。我当初就是靠这个对拍，发现自己build_star里漏了一条 ε 边，导致a*匹配不了空串。

5. 踩过的坑与排查链路

5.1 ε 闭包写成"只走一步"

这是最隐蔽的坑。ε 闭包必须传递闭包，即 A ε→ B、B ε→ C，则从 A 出发的闭包要包含 C。我第一版实现用了简单的"遍历一次出边"，结果遇到 ε 链就断在中间。表现是：某些本该匹配的串匹配失败，而且失败得很随机——取决于构造时 ε 链有多长。

排查方法：构造一条故意产生长 ε 链的正则，比如((a|b)|(c|d))，打印每个状态的闭包，看是否包含所有可达状态。修复就是把单次遍历改成用栈或队列的迭代，直到没有新状态加入为止，也就是上面epsilon_closure的写法。

5.2 子集构造时字母表漏字符

第二个坑在转 DFA 阶段。如果字母表只取了正则里"显式出现"的字符，而忽略了某些通过字符类隐含的字符，生成的 DFA 会缺转移。表现是：某些输入串走到一半发现"没有对应转移"，程序报错或静默失败。

排查链路是这样的：先打印 NFA 所有边的字符集合，去重得到真实字母表；再检查子集构造循环里遍历的是不是这个集合。我当时的 bug 是字符类[a-c]展开时只取了a和c，漏了b，导致含b的串全部匹配失败。修复很简单，但发现它花了我一个下午——因为失败现象和"正则写错"太像了，容易往错误方向查。

5.3 接受状态判定用"等于"而非"包含"

NFA 转 DFA 后，DFA 的接受状态是"包含 NFA 接受状态的子集"。我一开始写成了"子集恰好等于 {accept}"，结果凡是子集里混了其他状态的都判失败。正确写法是if nfa.accept in state_set。这个 bug 的迷惑性在于：简单正则能过，复杂正则就挂，因为简单正则的接受子集往往恰好只含一个状态。

注意：这三个坑的共同点是"简单用例能过、复杂用例才暴露"。所以测试用例一定要覆盖 ε 链、字符类、多分支这几种结构，别拿abc这种平凡串自测就以为万事大吉。

6. 从理论到工程：这套东西到底用在哪

6.1 词法分析器是最典型的落地场景

编译器前端的第一步是词法分析，把源码切成 token。每个 token 类型（标识符、数字、关键字、运算符）本质上就是一条正则。工程做法是把所有 token 的正则合并成一台大 NFA，再转 DFA，然后拿 DFA 去扫源码——每读一个字符走一步，走到接受状态就吐出一个 token。这就是为什么词法分析器能做到线性时间扫描，因为它底层是 DFA，没有回溯。

我手写过一个小型词法分析器验证这套流程：定义五六种 token 的正则，用 Thompson 构造拼成 NFA，子集构造转 DFA，最后扫描一段模拟代码。跑通那一刻对"正则和自动机是一回事"的理解才算真正落地。中间最麻烦的不是构造，是多个 token 正则合并时的优先级处理——最长匹配优先、同长度按定义顺序优先，这些规则要在 DFA 接受状态上额外打标记才能实现。

6.2 输入校验与协议解析里的隐形应用

很多输入校验场景，表面写的是正则，底层跑的是自动机。比如校验一个格式化的编号、一段结构化文本、一条配置项，用正则描述合法集合，引擎内部转成自动机去跑。理解这一点后，你会更清楚为什么某些正则校验特别慢——不是引擎差，是自动机状态爆炸了。

协议解析也是同理。某些文本协议的字段格式用正则描述后，可以编译成 DFA 做流式解析，边读边判，不需要把整个报文读进内存。这种流式能力正是 DFA 的天然优势：它只需要记住"当前状态"，不需要回看历史字符。

6.3 什么时候不该用自动机这套

说句实在话，不是所有场景都值得上自动机。如果你只是偶尔匹配一下日志里的时间戳，直接re一把梭完全够用，没必要为了"优雅"去手搓 NFA。自动机这套东西的价值在三个地方才凸显：需要极致性能且模式固定（预编译 DFA）、需要流式处理不能回看（DFA 天然支持）、需要形式化验证正确性（自动机可以数学证明，正则的边界情况靠测试很难穷尽）。

我的判断标准很简单：模式是运行时动态拼出来的、且可能很复杂，优先考虑转 DFA 或至少做回溯风险审查；模式是写死的简单匹配，re足够。别为了用而用，工具服务于问题。

7. 几个能立刻上手的练习建议

想把这块真正吃透，光看不够，得练。我按难度递进给三个练习，都是我自己做过、且做完有明显收获的：

第一个，手算(a|b)*abb的 NFA 和 DFA。别用工具，拿纸笔算，算完再用代码验证。这一步练的是子集构造的肌肉记忆，尤其是 ε 闭包别漏状态。

第二个，实现一个支持|、*、()和单字符的迷你正则引擎。用 Thompson 构造加 NFA 模拟，跑通后和re.fullmatch对拍一百个随机串。这一步会把前面所有坑都踩一遍，踩完就真会了。

第三个，给迷你引擎加 DFA 转换，并对比两种执行方式的性能。构造一条会引发回溯爆炸的正则，分别用 NFA 模拟和 DFA 执行跑长串，看时间差。这个对比会让你对"为什么要转 DFA"有切身体会，而不是停留在教材结论上。

最后分享一个我自己的体会：学自动机最容易犯的错是"看懂了但没写过"。教材上的图看十遍，不如自己写一遍构造代码、调一次 ε 闭包的 bug。那些坑——ε 链断掉、字母表漏字符、接受判定写错——只有亲手踩过，才会变成你脑子里的检查清单。等哪天你看到一条正则，脑子里能自动浮现出它的状态图、能预判它会不会回溯爆炸，这块内容才算真正长在你身上了。