第 4 章 · 02 NFA 与 DFA:两种自动机的取舍

第 4 章 · 02 NFA 与 DFA:两种自动机的取舍

本节摘要:上一节建立了「正则 = 自动机」,这一节讲自动机的两种类型:DFA(确定有限自动机)与 NFA(非确定有限自动机)。两者能力相同(能识别的语言一样),但性格迥异:DFA 匹配快但构造可能状态爆炸;NFA 构造简单但匹配需要处理「非确定性」。这个取舍,是正则引擎设计(以及下一节回溯 vs DFA 的路线选择)的核心。理解 NFA 与 DFA 的差别,你才能看懂为什么不同正则引擎表现不同。

内容来源:基于正则理论整理的导读。

学习目标

阅读完本节,你应当能够:

1. 说清 DFA(确定)与 NFA(非确定)的定义差别。
2. 解释「非确定性」的两层含义:同一输入多条出边、ε 转移(空输入跳转)。
3. 说清两者的取舍:DFA 匹配快但状态可能爆炸;NFA 构造简单但匹配需处理非确定。
4. 理解两者识别的语言能力相同(等价定理)。

一、学习价值:这是正则引擎的核心取舍

正则引擎实现的两条路线——DFA 式与回溯式(下一节)——直接对应这里讲的 DFA 与 NFA 两种自动机。理解这一节的取舍,你就理解了:

• 为什么 grep 默认用 DFA(快)但 Python re 用回溯(支持反向引用)。
• 为什么有的正则在某些引擎上快、在另一些上慢(回溯的指数爆炸)。
• 为什么没有「绝对更好」的正则引擎,只有「特定场景合适」的。

二、认知拆解:DFA 与 NFA

DFA(确定有限自动机)

DFA 的规则严格:在任何状态,对任何输入字符,有且仅有一个确定的下一状态。

DFA 示例(识别 ab):
        a           b
(0) ──────► (1) ──────► ((2))
​

• 状态 0 读 a,只能去 1;状态 1 读 b,只能去 2。
• 匹配时:从 0 出发,逐个读输入字符,每步走唯一确定的转移,读完后看在不接受状态。

DFA 的好处是匹配快:每读一个字符只做一次状态查表,O(n) 时间(n 是输入长度),与正则复杂度无关。坏处是构造可能爆炸:某些正则对应的 DFA 状态数会指数级膨胀。

NFA(非确定有限自动机)

NFA 放宽了两个限制:

1. 同一状态对同一输入可以有多条出边:状态 0 读 a,可以同时去状态 1 或状态 2。
2. ε 转移:不读任何输入也能跳到另一状态。

NFA 示例(识别 a|b):
        a
   ┌─────► (1) ──► ((2))
(0)
   └─────► (3) ──► ((4))
        b
​

状态 0 读 a 可去 1,读 b 可去 3。这种「非确定」怎么执行?两种思路:

• 并行:同时处于多个状态(状态集合),每读一个字符,把所有可能的下一状态算出来。
• 回溯:选一条路走,走不通退回来试另一条(这是多数正则引擎的实际做法,下一节详述)。

NFA 的好处是构造简单(Thompson 构造直接产出 NFA,下一节讲),坏处是匹配要处理非确定,最坏情况(回溯)会慢。

两者能力相同

定理:NFA 与 DFA 识别的语言完全相同——任何 NFA 都能转成等价的 DFA(子集构造法),反之亦然。差别只在「构造成本」与「匹配成本」的权衡:

三、上手第一步:画两种自动机对比

用 a|b(a 或 b)这个正则,画 DFA 和 NFA 各一个,对比:

• DFA 需要精心设计状态(状态 0 读 a 去 1,读 b 也去 1,因为 a 或 b 之后都「接受」了)。
• NFA 直接「分叉」(状态 0 读 a 走上支,读 b 走下支)。

你会直观感到「NFA 更好画」——这正是 Thompson 构造用 NFA 的原因。

本节要点回顾

1. DFA(确定):每状态每输入唯一转移,匹配快但构造可能爆炸。
2. NFA(非确定):同一输入可多出边、有 ε 转移,构造简单但匹配要处理非确定(并行或回溯)。
3. 能力等价:NFA 与 DFA 识别的语言相同,可互转(子集构造法);差别在构造与匹配成本的权衡。
4. 取舍:DFA 匹配快不支持反向引用(如 grep);NFA 回溯式支持反向引用但可能慢(如 Python re)。

推荐上手顺序

1. 画几个简单正则的 DFA 与 NFA 对比(如 ab、a*、a|b),体会构造难度差异。
2. 读下一节(03 Thompson 构造),看如何系统地把正则编译成 NFA。
3. 理解子集构造法(NFA→DFA)的思路(下一节简述)。
4. 在第 04 节(匹配策略)看清「DFA 式」与「回溯式」两条引擎路线的工程取舍。

下一节是全章最核心、最美的算法——Thompson 构造,把任意正则系统编译成 NFA。