有限自动机 · DFA / NFA / regex 与它们之间的转换
一台 finite automaton 就是「一把 state + 一张 transition 表」的极简机器—— 读一个字符跳一次 state,读完看停在哪。先认识两种机器:DFA(deterministic,每步唯一去向) 与 NFA(nondeterministic,允许一个字符多个去向、还有不读字符的 ε-transition); 再看把它们串起来的三条经典「桥」:regex → NFA(Thompson construction)、 NFA → DFA(subset construction)、DFA → 最小 DFA(partition refinement)。
每页都能改输入 / regex、点单步,看纸带上的读取指针、状态机上高亮的 state 与边,以及一旁的集合 / 表 实时更新。连起来读就是一条完整链路:正则表达式 → NFA → DFA → 最小 DFA—— 这正是一个 regex 引擎在背后做的事。 前置知识只需基本的 regex 语法 (|、*、括号);若不熟悉,可先看 regex 系列。
DFA：每步只有一条路
deterministic finite automaton：在 start state 起步，读一个字符就沿唯一一条 transition 跳一次，读完落在 accept state 就 ACCEPT。用「二进制数能否被 3 整除」这台三态机器，单步看读取指针推进、当前 state 在图上高亮——确定性意味着任一时刻你只可能在一个state 上。
NFA：同时身处一群 state
nondeterministic finite automaton 放宽两条规则：一个字符可以有多个去向，还能走不读字符的 ε 边。运行方式是维护「此刻所有可能所处的 state 集合」，读一个字符就 move + 取 ε-closure。单步看这个集合在图上整片高亮、随每个字符扩张收缩——这就是 subset simulation。
Thompson construction：把 regex 编译成 NFA
正则表达式怎么变成一台机器？Thompson 给每种算子一块「积木」：字面字符、连接、| 或、* 闭包，各自是一小段带 ε 边的 NFA 片段，按 regex 结构拼起来。输入一个 regex，单步看它先转成 postfix，再逐个 token 把片段拼成完整 ε-NFA。
Subset construction：把「集合」固化成 DFA state
NFA 跑起来要时刻维护一个 state 集合——那就把每一种可能出现的集合直接当成一个 DFA state 预先算好。从 ε-closure(start) 出发，对每个字符算 move+closure，新集合就登记为新 state。左看 NFA、右看 DFA 逐个长出来，彻底消除非确定性。
DFA minimization：合并行为一样的 state
subset construction 造出的 DFA 常常有冗余：两个 state 对任何后续输入的接受/拒绝都一致，就该合并。先按「接受 / 不接受」分两组，再反复细分——同组里「对某字符转移去向不同组」的就拆开，直到稳定。每组合并成一个 state，得到唯一的最小 DFA。
反方向：把一台状态机变回正则表达式
前三条桥都是 regex → 机器；这条走反向：给一台 FA，用状态消去 / Brzozowski 代数法反推出等价 regex。给每个 state 列方程，挑一个变量先用 Arden 引理把自环解成 *、再代入消掉，直到只剩 start。左看图一个个删 state、右看方程同步解开——补完 regex ⇄ 有限自动机 的闭环（Kleene 定理）。预设含 qntm 那台 🌱 植物机器。
应用实例：熔断器 Circuit Breaker 状态机
DFA 不只识别字符串——微服务里的熔断器就是一台三 state 的 DFA:CLOSED（放行）/ OPEN（熔断，请求 fast-fail）/ HALF_OPEN（冷却后试探）。点按钮发「请求成功 / 失败 / 冷却到期」事件，看它在三态间跳转、失败计数累积到阈值跳闸——和「能被 3 整除」那台机器同一个 state + transition 骨架。
真实系统中的有限自动机
grep、各语言的 regex,底层都是 NFA/DFA;本系列的三条转换正是它们把 regex → NFA → DFA → 最小 DFA 的真实流水线。 编译器 / 解释器:词法分析器 lexer 把源码切成 token,flex 直接把正则规则编译成一张 DFA 转移表;语法高亮、JSON / 协议解析器同理。 入侵检测 / DPI:Snort、Suricata、Intel Hyperscan 用 NFA/DFA(+ Aho-Corasick)在网络流量里同时匹配成千上万条攻击特征。 协议与业务状态机:TCP 连接状态、订单 / 工单流转、限流熔断器(closed → open → half-open),本质都是一台 DFA —— state + transition 表。