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

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

Thompson、subset construction 与 minimization 走的是 regex 到 NFA 再到 DFA 的方向。这一页走反向：给一台 FA，反推出一条等价的 regex。这总能做到，因为有限自动机与（严格意义的）正则表达式表达能力相同，即 Kleene 定理，本页是它的另一半。手法称为状态消去（state elimination），也就是 Brzozowski 代数法。

1 · 一步消一个变量

给每个状态 ii 写一个方程

Xi=⨁jaij⋅Xj  ⊕  [ i 是终态 ] εX_i = \bigoplus_j a_{ij} \cdot X_j \;\oplus\; [\,i \text{ 是终态}\,] \, \varepsilon

其中 aija_{ij} 是从 ii 到 jj 的边上符号，⊕\oplus 即 regex 的 |。挑一个非 start 的变量 XqX_q：它若有自环 α\alpha，先用 Arden 引理把自环解成闭包，再把 XqX_q 代入所有引用它的方程，这一步在图上就是把「经过 qq 的路径」重写成一条直达边。删到只剩 start，解它的方程即得答案。

定理 1.1（Arden 引理） 设 α\alpha、β\beta 是语言。方程 X=αX∣βX = \alpha X \mid \beta 恒有解 X=α∗βX = \alpha^{*}\beta；当 ε∉α\varepsilon \notin \alpha 时该解唯一。

警示 · ε∉α\varepsilon \notin \alpha 这个前提不能省。若 ε∈α\varepsilon \in \alpha，α∗β\alpha^{*}\beta 仍是解，却不再是唯一解，此时消元得到的 regex 未必与原机器等价。状态消去中的自环 α\alpha 由该状态上的真实转移标签构成，天然不含 ε\varepsilon，前提自动满足；但把同一套代数法搬到允许 ε 自环的图上时，要先消去 ε 自环再套用引理。

图 1-1 · 左侧逐个删去状态、右侧同步解开方程组。可单步执行，观察每消去一个变量时图上新增的直达边与方程里被代入的项如何对应。

正向与反向合起来，就是 regex 与有限自动机的完整闭环。regex 系列另有一个从正则到状态机的可视化可对照。

2 · 参考文献

  1. Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. In C. E. Shannon & J. McCarthy (Eds.), Automata Studies (pp. 3–41). Princeton University Press.
  2. Brzozowski, J. A. (1964). Derivatives of regular expressions. Journal of the ACM, 11(4), 481–494.
  3. qntm. Turning finite-state machines into regular expressions. 本页的植物机器示例与灵感来源，也讲清了严格正则与反向引用、lookaround 的区别。https://qntm.org/plants
  4. qntm. greenery. 上述消元过程的 Python 实现，可做 FSM 与 regex 互转、求正则的交与补、判定等价。https://github.com/qntm/greenery