正则引擎中的有限自动机 ② 有限自动机

1. 有限自动机 (Finite Automata) 的本质

有限自动机（Finite Automata, FA）是正则表达式背后的底层物理引擎与执行机制。在工程界，它通常被称为有限状态机（Finite State Machine, FSM）。

在数据结构与算法视角下，状态机本质上是一个**带权/带标签的有向图 (Directed Graph)**：

• **节点 (Nodes)：代表系统的状态 (States)**。
• **边 (Edges)：代表状态之间的转移 (Transitions)**，每条边上标记了发生该转移所必须消耗的输入符号。

---

2. 正则文法与有限自动机的一一映射 (One-to-One Mapping)

正则文法的产生式规则与状态机的图结构存在严格的一对一对应关系：

      正则文法 (BNF 产生式)                       有限自动机 (有向图)
┌────────────────────────────────┐         ┌────────────────────────────────┐
│ 起始符号 S                      │  <===>  │ 起始状态 (带有来自外部的指示箭头)│
│ 产生式左侧非终结符 (当前变量)    │  <===>  │ 当前源状态 (Source State)       │
│ 产生式前缀终结符 (消耗字符)      │  <===>  │ 边上的转移字符 (Transition Label)│
│ 产生式右侧非终结符 (目标变量)    │  <===>  │ 转移目标状态 (Destination State) │
│ 空串推导规则 (A -> ε)           │  <===>  │ 接受状态 (双同心圆标记状态)     │
└────────────────────────────────┘         └────────────────────────────────┘

2.1 状态转移机制

以产生式 $S \to bA$ 为例：

1. 源状态：处于状态 $S$。
2. 字符消耗：当从输入字符串中读取（Consume）字符 'b' 时。
3. 目标状态：系统状态跳转至状态 $A$。

2.2 接受状态 (Accepting / Final States)

• 图形表示：在自动机图纸中，接受状态使用双同心圆（Double-circled）表示。
• 判决准则：当遍历有向图消耗完字符串的所有字符后，如果停留在某个接受状态，则判定该字符串被当前自动机所接受（Accepted）。
• 文法对应：在形式文法中，产生式 $A \to \epsilon$ 对应接受状态。因为 $\epsilon$ 代表空字符串，表示无需再转移，匹配在此圆满终止。

---

3. 有限自动机的分类谱系

在广义计算理论中，有限自动机划分为两大阵营：

                  有限自动机 (Finite Automata)
                             │
     ┌───────────────────────┴───────────────────────┐
有输出状态机 (With Output)                      无输出状态机 (Without Output)
(用于硬件控制与序列生成)                        (用于语言识别与正则表达式引擎)
     ├── Moore 机器 (输出取决于状态)                  ├── DFA (确定性有限自动机)
     └── Mealy 机器 (输出取决于状态+输入)             ├── NFA (非确定性有限自动机)
                                                      └── ε-NFA (带空转移的NFA)

在正则表达式引擎的设计与实现中，我们重点研究无输出的三种机器：**$\epsilon$-NFA、NFA** 和 DFA。

---

4. 三大正则自动机深度剖析：DFA, NFA 与 $\epsilon$-NFA

4.1 NFA (非确定性有限自动机)

• 非确定性（Non-determinism）的核心定义：允许在同一个输入符号下，从当前状态跳转到多个不同的目标状态。
• 执行行为：如果在状态 1 遇到字符 'a'，存在通向状态 2 和状态 3 的两条边，NFA 在概念上会“同时分裂并走入这两条路径”，以并行探索所有可能的接受路径。

4.2 $\epsilon$-NFA (带 $\epsilon$-空转移的非确定性有限自动机)

• 能力扩展：具备 NFA 的一切特性，并额外支持 $\epsilon$-转移（Epsilon-transitions）。
• $\epsilon$-转移的含义：允许系统在不消耗输入字符串中任何字符的情况下，自发地从一个状态跃迁到另一个状态（例如纯粹为了连接两个独立的自动机子模块）。
• 约束程度：限制最少，最适合作为人类构建正则模块的基本积木。

4.3 DFA (确定性有限自动机)

• 确定性（Determinism）的核心约束：
  1. 禁止多分支转移：给定当前状态和特定输入字符，其后继目标状态必须唯一且确定。
  2. 绝对禁止 $\epsilon$-转移：每一次状态转移都必须且只能消耗输入串中的一个确切字符。
• 执行优势：运行毫无歧义，没有分支试探，运行时只需要查表即可线性前进。

---

5. 核心架构设计：为什么需要三种自动机？

既然 DFA 性能最高且没有二义性，为什么不直接从正则表达式生成 DFA？

5.1 正则引擎编译管道 (Compilation Pipeline)

因为从人类编写的高阶正则表达式直接构造 DFA 极其复杂，工业界通用的标准流水线如下：

[正则表达式 (RegExp)]
        │
        ▼ (通过汤普森构造法，直观模块化拼装)
   [ε-NFA]
        │
        ▼ (消除 ε 转移与多分支)
    [NFA]
        │
        ▼ (通过子集构造法 Subset Construction 进行确定化)
    [DFA]
        │
        ▼ (通过 Hopcroft 等算法进行状态最小化)
[高效状态转移表 (Transition Table)]

• 构造期（Construction Time）：利用 $\epsilon$-NFA 的灵活性，能够像搭积木一样为各种正则操作符（拼接、选择、闭包）快速组装子图。
• 运行期（Runtime）：最终将机器转化为 DFA 状态表执行，获得严格的 $O(N)$ 线性时间复杂度保障，消除回溯性能陷阱。

---

6. 有限自动机（NFA）的形式化数学定义 (5-Tuple)

在理论计算机科学中，一个有限自动机由一个五元组严格定义：
$$M = (Q, \Sigma, \Delta, q_0, F)$$

元组分量	符号全称	数学定义与物理意义
$Q$	States Set	自动机中所有可能状态的有限非空集合。
$\Sigma$	Alphabet	输入字符构成的有限字母表。
$\Delta$	Transition Function	状态转移函数。对于 NFA，定义为映射：$Q \times \Sigma \to 2^Q$。 含义：给定当前状态 $q \in Q$ 和输入符号 $a \in \Sigma$，返回的是所有可能目标状态构成的幂集子集（即可以转移到 $2^{
$q_0$	Start State	唯一的初始起始状态（$q_0 \in Q$）。
$F$	Accepting States	终止接受状态集合（$F \subseteq Q$），系统落入其中任一状态即代表匹配成功。

---

7. 状态机对象设计

                ε                     A                     ε
      ┌───────────────────> ( 状态 1 ) ──────────> ( 状态 2 ) ──────────────────┐
      │                                                                         │
      │                                                                         ▼
( 起始状态 )                                                               (( 接受状态 ))
  (最左侧)                                                                     (双圈终点)
      │                                                                         ▲
      │         ε                     B                     ε                   │
      └───────────────────> ( 状态 3 ) ──────────> ( 状态 4 ) ──────────────────┘

这是汤普森构造法中用来实现正则表达式“或运算”（$A \mid B$）的标准状态机图。

2. 执行链路推导（以匹配字符 'A' 为例）：

1. 起始状态遇到 $\epsilon$（空转移）：
   • $\epsilon$ 代表“免费传送门”：无需消耗输入字符串中的任何字符，机器自发瞬移到了状态 1（同时也会瞬移到状态 3）。
2. 状态 1 遇到字符 'A'：
   • 消耗输入串中的字符 'A'，沿着有向边前进到状态 2。
3. 状态 2 再次遇到 $\epsilon$：
   • 不消耗字符，自动滑入最右侧的接受状态（双圈）。
4. 此时字符串读取完毕，机器停在接受状态，判定：匹配成功！

class State {
    accepting: boolean;
    transitions: Map<string, State[]>;
    constructor({ accepting = false }) {
        this.accepting = accepting;
        this.transitions = new Map();
    }
    addTransitionForSymbol(symbol: string, state: State): void {
        const transitionsForSymbol = this.transitions.get(symbol);
        if (transitionsForSymbol) {
            transitionsForSymbol.push(state);
        } else {
            this.transitions.set(symbol, [state]);
        }
    }
    getTransitionForSymbol(symbol: string): State[] {
        return this.transitions.get(symbol) || [];
    }
}

const s1 = new State({ accepting: false })
const s2 = new State({ accepting: true })

s1.addTransitionForSymbol('a', s2)
console.log(s1.getTransitionForSymbol('a'))

打赏