有限自动机 · DFA / NFA / regex 与它们之间的转换

一台 finite automaton 由一组状态与一张转移表给定：读一个字符跳一次状态，读完看停在哪。本系列先给出两种机器 —— DFA (deterministic，每步唯一去向) 与 NFA (nondeterministic，一个字符可以有多个去向，另有不读字符的 ε-transition) —— 再给出把它们串起来的三条转换：regex 到 NFA 的 Thompson construction、NFA 到 DFA 的 subset construction、DFA 到最小 DFA 的 partition refinement，以及反方向的状态消去。

每页都可改输入或 regex 并单步执行，观察读取指针、机器上高亮的状态与边，以及一旁的集合或表同步更新。连起来读是一条完整链路，也正是一个 regex 引擎在背后所做的事。前置知识只需基本的 regex 语法 (|、*、括号)；不熟悉可先看 regex 系列。

两种机器：一个串怎么被读完 DFA · 确定性 · 单条路径

DFA：每步只有一条路

deterministic finite automaton 由五元组给定，转移函数对每个「状态 + 字符」只给一个去向。以「二进制数能否被 3 整除」的三态机器为例，逐字符观察当前状态的推进。

NFA · 非确定 · ε-transition · 集合模拟

NFA：同时身处一群 state

nondeterministic finite automaton 放宽两条规则：一个字符可以有多个去向，还能走不读字符的 ε 边。运行方式是维护当前可能所处的状态集合，读一个字符做一次 move 与 ε-closure。

机器与正则之间的转换 Thompson · regex → NFA

Thompson construction：把 regex 编译成 NFA

给每种 regex 算子配一块带 ε 边、单入口单出口的 NFA 片段，按 regex 结构拼接。输入一个 regex，可观察它先转成 postfix，再逐个 token 拼成完整的 ε-NFA。

subset construction · NFA → DFA

Subset construction：把「集合」固化成 DFA state

NFA 运行时维护的状态集合，每一种都对应一种确定的处境。把这些集合预先算出来各作一个 DFA 状态，非确定性在构造阶段即被消除。

minimization · partition refinement

DFA minimization：合并行为一样的 state

两个状态若对任何后续输入的接受与拒绝都一致即等价，可以合并。划分细化从「接受 / 不接受」两组起反复拆分，稳定时每组捏成一个状态，得到同构意义下唯一的最小 DFA。

state elimination · Brzozowski · FA → regex

反方向：把一台状态机变回正则表达式

给一台 FA 反推出等价 regex。给每个状态列方程，用 Arden 引理把自环解成闭包再代入消元，直到只剩 start，补完 regex 与有限自动机的等价闭环。

生产代码里的状态机 applications · 真实应用

应用实例：熔断器状态机

熔断器是一台三状态的有限状态机，CLOSED 放行、OPEN 快速失败、HALF_OPEN 试探恢复。它与识别字符串的机器共用同一套「状态加转移表」骨架。

真实系统中的有限自动机

正则引擎：Google RE2 (Cloudflare 在 2019 年那次回溯失控导致的全站故障后转用它)、grep 与各语言的 regex，底层都是 NFA 或 DFA；本系列的三条转换正是这条流水线。编译器与解释器：词法分析器把源码切成 token，flex 直接把正则规则编译成一张 DFA 转移表；语法高亮与 JSON、协议解析器同理。入侵检测与 DPI：Snort、Suricata 与 Intel Hyperscan 用 NFA、DFA 加 Aho–Corasick，在网络流量上同时匹配成千上万条攻击特征。协议与业务状态机：TCP 连接状态、订单与工单流转、限流熔断器 (closed → open → half-open)，本质都是一台有限状态机。