← 有限自动机 · DFA / NFA / regex 与它们之间的转换 / 反方向：把一台状态机变回正则表达式 待审核 6 / 7
state elimination · Brzozowski · FA → regex

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

Thompson、subset construction 与 minimization 走的是 regex→NFA→DFAregex \to NFA \to DFA。这页走反方向：给一台 FA，反推出一条等价的 regex。这总能做到——有限自动机与（严格）正则表达式完全等价（Kleene 定理），本页正是它的「另一半」。手法叫状态消去 (state elimination)，也就是 Brzozowski 代数法：左边看图一个个删 state，右边看方程被逐步解开——它俩是同一件事的两个视角。

一步消一个变量：给每个 state 写一个方程 Xi=⊕jaij⋅Xj⊕(ε若终态)X_i = \oplus _j a_ij\cdot X_j \oplus (\varepsilon 若终态)（a_ij = 从 i 到 j 的边上符号，⊕\oplus 是 |）。挑一个非 start 变量 X_q：若它有自环 α\alpha，先用 Arden 引理 X=αX∣β⇒X=α∗βX = \alpha X | \beta \Rightarrow X = \alpha *\beta 把自环解成 Kleene star；再把 X_q 代入所有引用它的方程（= 图上把「过 q 的路径」重写成一条直达边）。删到只剩 start，它的方程一解就是答案。

和正向那条链对照着看：Thompson construction 把 regex 编译成 NFA、subset construction 再定成 DFA;regex 系列还有一个反过来的 「正则 → 状态机」可视化。正向与反向合起来，就是 regex ⇄ 有限自动机 的完整闭环。

1 · 🔗 相关链接

  • Turning finite-state machines into regular expressions · qntm.org——本页灵感来源：用 plants emoji 的 FSM 逐步演示 Brzozowski 代数法（就是上面那台 🌱 机器）。讲清了「严格正则」与反向引用 / lookaround 的区别。
  • greenery · github.com——qntm 写的 Python 库，能自动做 FSM ⇄ regex 互转、求正则的交 / 补 / 等价判定——本页这套消元的工程实现。