3、有限自动机理论：DFA、NFA与正则表达式到NFA的转换
好，咱们今天聊聊有限自动机。说实话，这玩意儿刚接触时挺抽象的。我当年学编译原理，看到DFA、NFA这些概念，第一反应是——这跟写代码有什么关系？后来真正做词法分析器时才发现，不懂这个，你连一个简单的token识别都写不踏实。
有限自动机，说白了就是一台「状态切换机器」。它根据输入字符，在不同状态间跳来跳去。如果最终停在「接受状态」，就说明输入字符串被接受了。就这么简单。
3.1 确定性有限自动机（DFA）
DFA，全称Deterministic Finite Automaton。它的核心特点是——确定。什么意思？就是给定当前状态和输入字符，下一个状态是唯一确定的，没有二义性。
DFA的数学定义：一个五元组 (Q, Σ, δ, q0, F)
- Q：有限状态集合
- Σ：有限输入字母表
- δ：转移函数，δ(q, a) = p，表示从状态q读入字符a后到达状态p
- q0：初始状态，q0 ∈ Q
- F：接受状态集合，F ⊆ Q
举个例子。假设我们要识别所有以"ab"结尾的字符串。DFA长这样：
状态集合 Q = {q0, q1, q2}
输入字母表 Σ = {a, b}
初始状态 q0
接受状态 F = {q2}
转移函数 δ：
δ(q0, a) = q1
δ(q0, b) = q0
δ(q1, a) = q1
δ(q1, b) = q2
δ(q2, a) = q1
δ(q2, b) = q0你看，每个状态对每个输入字符，都只有一个转移目标。这就是「确定性」的含义。我在项目中用DFA做过一个简单的协议解析器，性能非常好，因为不需要回溯，时间复杂度就是O(n)。
个人经验：DFA的实现通常用二维数组或者哈希表。状态做行，字符做列，查表就行。我习惯用二维数组，因为内存连续，CPU缓存友好。
3.2 非确定性有限自动机（NFA）
NFA，Non-deterministic Finite Automaton。跟DFA最大的区别是——不确定。一个状态读入一个字符，可能跳到多个状态，也可能跳不到任何状态。甚至还有ε（空字符）转移，不读任何字符就能跳。
NFA的数学定义：同样是一个五元组 (Q, Σ, δ, q0, F)
- Q、Σ、q0、F 含义与DFA相同
- δ：转移函数，δ(q, a) 返回的是一个状态集合，而不是单个状态
- 允许ε转移：δ(q, ε) 表示不消耗字符就能跳转
还是那个例子——识别以"ab"结尾的字符串。用NFA实现：
状态集合 Q = {q0, q1, q2}
输入字母表 Σ = {a, b}
初始状态 q0
接受状态 F = {q2}
转移函数 δ：
δ(q0, a) = {q0, q1} // 注意！这里有两个可能
δ(q0, b) = {q0}
δ(q1, b) = {q2}
// 其他情况返回空集看到没？q0读入'a'，既可以留在q0，也可以跳到q1。这就是非确定性。NFA的「猜测」能力让它更容易描述模式，但执行时就需要回溯或者并行模拟。
我曾经踩过的坑：用NFA直接做词法分析，遇到复杂表达式时，回溯次数呈指数级增长。有一次解析一个200字符的输入，跑了3秒还没出结果。后来改成DFA，0.1毫秒就搞定了。所以实际工程中，我们通常会把NFA转成DFA再执行。
3.3 DFA与NFA的对比
| 特性 | DFA | NFA |
|---|---|---|
| 状态转移 | 唯一确定 | 可能有多个 |
| ε转移 | 不支持 | 支持 |
| 执行效率 | O(n)，线性 | 可能需要回溯 |
| 构造难度 | 较复杂 | 简单直观 |
| 状态数量 | 可能较多 | 通常较少 |
| 适用场景 | 实际执行 | 模式描述 |
你想想看，DFA就像一本精确的说明书，每一步都写得清清楚楚。NFA更像一个模糊的指南，告诉你「大概这么走」，具体怎么走需要你自己探索。两者各有优劣，实际中我们取长补短。
3.4 从正则表达式到NFA
好，重点来了。正则表达式怎么变成NFA？这里有个经典算法——Thompson构造法。我当年学这个算法时，觉得它特别巧妙。它把每个正则表达式的基本单元都映射成一个小的NFA片段，然后通过规则组合起来。
基本规则就5条：
- 空串ε：直接一个初始状态连到接受状态
- 单个字符a：初始状态读入a到接受状态
- 连接rs：把r的接受状态和s的初始状态合并
- 选择r|s：新增一个初始状态，通过ε分别连到r和s的初始状态；r和s的接受状态通过ε连到新的接受状态
- 闭包r*：新增初始和接受状态，通过ε形成循环
举个例子，正则表达式 a(b|c)* 的NFA构造过程：
1. 先构造 'a' 的NFA：q0 --a--> q1
2. 再构造 'b' 的NFA：q2 --b--> q3
3. 再构造 'c' 的NFA：q4 --c--> q5
4. 用选择规则合并 b|c：新增q6、q7，q6 --ε--> q2，q6 --ε--> q4，q3 --ε--> q7，q5 --ε--> q7
5. 用闭包规则处理 (b|c)*：新增q8、q9，q8 --ε--> q6，q7 --ε--> q9，q9 --ε--> q6，q8 --ε--> q9
6. 用连接规则合并 a 和 (b|c)*：q1 --ε--> q8最终得到的NFA有10个状态。嗯，这里要注意，Thompson构造法产生的NFA有个特点——每个状态最多有两个出边，而且ε转移很多。这为后续转DFA提供了便利。
我个人的实现习惯：用结构体表示NFA的每个状态，包含转移边列表。转移边用链表存储，方便动态添加。代码大概长这样：
struct NFAState {
int id;
struct Transition {
char input; // '\0' 表示 ε
NFAState* next;
};
vector<Transition> transitions;
bool isAccept;
};实际项目中，我见过很多人直接手写正则引擎。说实话，如果不是特别需要，不建议这么做。因为边界情况太多了。比如 a* 和 a*a 这种看似简单的表达式，构造NFA时稍不注意就会多出冗余状态。
3.5 知识体系总览
下面这张图，我把本章的核心逻辑梳理了一下。你看一遍，应该能对有限自动机有个整体把握。
从这张图你能看到，整个流程是串起来的。正则表达式是人的视角，NFA是中间表示，DFA是机器执行视角。每一步都有成熟的算法支撑。
说实话，我刚开始做词法分析器时，直接手写DFA，结果改一个正则就要重新画状态图，痛苦不堪。后来老老实实走「正则→NFA→DFA」这条路，才发现这才是正道。你想想看，正则表达式改一行，代码自动生成新的DFA，多省事。
总结一下本章重点：
- DFA是确定性的，每个输入只有一个去向，执行效率高
- NFA是非确定性的，支持ε转移，描述能力强但执行慢
- Thompson构造法能把任何正则表达式转换成等价的NFA
- 实际工程中，NFA用于描述，DFA用于执行
嗯，有限自动机这块内容就这些。下一节我们会讲怎么把NFA转成DFA，也就是子集构造法。那个算法我第一次看的时候觉得挺绕，但理解了之后会发现，它其实就是用「状态集合」来模拟NFA的所有可能路径。
公众号:蓝海资料掘金营，微信deep3321