形式陈述

Kleene 定理断言，对字母表 $\Sigma$$\mathrm{\Sigma }$ 上的语言 $L$$L$，以下等价：

1. $L$$L$ 由某个正则表达式描述；
2. $L$$L$ 由某个 $\varepsilon$$\epsilon$-NFA 识别；
3. $L$$L$ 由某个 DFA 识别。

正则表达式到 $\varepsilon$$\epsilon$-NFA 可按语法树归纳构造；有限自动机到正则表达式可用状态消除、广义 NFA 或方程组消元完成。再结合子集构造得到三者等价。

直觉

正则表达式是代数式描述，自动机是逐字符运行的机器描述。定理说明二者只是同一有限记忆语言类的不同表示方式。

例子与边界

表达式 $(0\mid1)^*01$$(0\mid 1{)}^{\ast }01$ 可构造出识别“以 01 结尾”的 NFA。等价性只关乎能描述哪些语言，不保证表示大小接近：NFA 转 DFA 可能指数膨胀，自动机转正则表达式也可能产生很大的表达式。

推论与应用

定理给出“正则语言”的多种等价定义，使闭包证明、实现和不可正则性论证可以选择最合适表示。词法分析通常由正则表达式经 NFA、DFA 构造得到执行器。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 2–3。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§1.3。