有限自动机（DFA / NFA）

正则表达式怎么在计算机里跑？

正则表达式 [a-z]+ 描述了一类字符串——但计算机怎么”执行”这个模式？答案是把正则表达式编译成有限自动机（Finite Automaton）。

🏫 类比：地铁线路图 每条地铁线路就是一个自动机——你在哪个站（状态），坐哪条线（输入字符），到哪个站（下一个状态），都是确定的。如果某站当前没车（无效输入），你就卡住了。

确定有限自动机（DFA）

DFA（Deterministic Finite Automaton） 对每个输入字符，最多只有一个后继状态。

DFA 识别整数 [0-9]+ 的模式：

        数字
    ┌──────────┐
    ▼          │
  ┌────┐ 数字  ┌────┐
  │ S0 │────→  │ S1 │
  └────┘       └────┘
    │            │
    │ 非数字      │ 非数字
    ▼            ▼
  ┌────┐       ┌────┐
  │ 拒绝│       │ 接受│
  └────┘       └────┘

DFA 的特点：

• 每个状态 + 每个输入 → 最多一个后继
• 匹配速度极快（O(n)，n 为输入长度）
• 但可能状态数较多

非确定有限自动机（NFA）

NFA（Nondeterministic Finite Automaton）——同一个输入可能有多个后继，还能”空跳”（ε 转移，不消耗输入字符就改变状态）。

NFA 识别 [0-9]+ 的模式：

  ┌───────────┐
  │   数字      │
  ▼           │
┌────┐ ε  ┌──────┐ 数字  ┌──────┐
│ S0 │──→ │  S1  │─────→ │  S1  │
└────┘    └──────┘       └──────┘
                      ε    │
                          ▼
                        ┌────┐
                        │ 接受│
                        └────┘

NFA 的特点：

• 同一输入可能有多个分支
• 可以”猜”哪个分支是对的
• 模拟 NFA 需要回溯或并行跟踪多个状态

NFA vs DFA

对比	NFA	DFA
每个输入的状态转移	可能多个	唯一
ε 空转移	✅	❌
状态数量	少	可能指数级更多
执行速度	慢（需回溯）	快（O(n)）
自动生成	容易	需要子集构造法

从正则到自动机

Thompson 构造法

把正则表达式递归地转换成 NFA：

正则      NFA 结构
a         ┌─ a ─┐
          → S0 → S1 →

a|b       ┌─ a ─┐
        → S0 ────→ S2
          └─ b ─┘

ab        ┌─ a ─┐  ┌─ b ─┐
          → S0 →→→ S1 →→→ S2

a*        ┌───────────┐
          │           │
          ▼  a        │
        → S0 ──→ S1 ──┘
          │
          └──→ 接受态

子集构造法（NFA → DFA）

把 NFA 并行跟踪的状态集合变成 DFA 的一个状态：

NFA 状态集           DFA 状态
{S0}         ──→   q0
{S0, S1}     ──→   q1
{S1, S2}     ──→   q2
...

自动机的最小化

生成的 DFA 可能有冗余状态——可以通过最小化算法合并等价状态：

最小化前：                    最小化后：
┌──────┐    a    ┌──────┐    ┌──────┐    a    ┌──────┐
│  q0  │───→    │  q1  │    │  q0  │───→    │ q1+q2│
└──────┘       └──────┘    └──────┘       └──────┘
                  │
                  │ a                        (合并 q1 和 q2)
                  ▼
               ┌──────┐
               │  q2  │
               └──────┘

💡 Lex/Flex 生成词法分析器的完整流程：正则 → NFA（Thompson 构造） → DFA（子集构造） → 最小化 DFA → C 代码。

小结

概念	要点
DFA	确定有限自动机，每个输入唯一转移
NFA	非确定有限自动机，有 ε 转移和分支
Thompson 构造	正则 → NFA 的标准算法
子集构造	NFA → DFA 的转换算法
DFA 最小化	合并等价状态，减少状态数
词法分析器生成	Lex：正则 → NFA → DFA → C

为什么先学这个？ 自动机不仅是词法分析的基础，也是语法分析的前置知识。下一节看看语法分析与上下文无关文法——如何描述比正则表达式更复杂的语言结构。