克莱尼定理——正则表达式与有限自动机等价

上级：regular-equivalences

Kleene（1951）

一个语言能被某个正则表达式表示，当且仅当它能被某个有限自动机识别。

两个方向都是构造性的：

正则表达式 → 自动机：Thompson 构造法

按运算符归纳，逐个搭出小的 ε-NFA：

• 符号 a：两个状态，一条 a-边；
• 并 R|S：新建一个起点，用 ε-边分别接入 R 与 S 的子自动机；
• 连接 RS：从 R 的接受态到 S 的起点连一条 ε-边；
• 星号 R*：加 ε-边实现回绕循环，再加一条跳过的 ε-边。 状态数与正则表达式的规模成线性关系。

自动机 → 自动机：子集构造法

把一个 NFA 转成等价的 DFA，DFA 的状态是 NFA 状态的集合（最多 2ⁿ 个）。这使"有限自动机"这个说法不再含糊——确定化只付出规模上的代价。

自动机 → 正则表达式：状态消去法（Arden 法则）

逐个拆掉状态，把每条留下的边重新标注为一个正则表达式；自环 X = A X | B 用 Arden 法则 X = A*B 求解。这个解是一个最小不动点——克莱尼星号本身就是不动点算子，所以克莱尼定理悄悄用到了克莱尼不动点。

与文法的关系

A → aB 就是一条转移 A --a--> B，只含终结符的规则对应接受态（regular-grammar）——第三种形式化方式因此免费并入。