Kleene 定理（Kleene's theorem）
/ KLAY-neez /
在這個領域中，你遇到好幾種看起來不同的描述語言的方式：確定型機器（DFA）、非確定型機器（NFA），以及現在的代數公式（正規表示式）。如果它們全都恰好捕捉同一組語言，不多也不少，那將相當了不起。Kleene 定理正是這麼說的：正規表示式與有限自動機的能力完全相等。
嚴謹地說，一個語言能被某個正規表示式標示，若且唯若它能被某台有限自動機識別。這個「若且唯若」有兩個方向，各自由一個明確的構造來證明。正向：由任何正規表示式，你都能建出一台等價的 ε-NFA，把每個運算子的小機器黏接起來（Thompson 構造法）。反向：由任何有限自動機，你都能抽出一個等價的正規表示式，做法是從一台廣義 NFA 反覆移除狀態（狀態消去法），或用 Arden 法則求解語言方程式。因為兩個構造都是演算法，這個等價不只是抽象的；你能機械地把一種表示法轉換成另一種。
這是正規性的第三張等價面孔，與「DFA 等於 NFA」的結果並列。正因如此，「正規語言」無論你選哪種形式體系都有單一而穩健的意義；它也是像詞法分析器產生器這類工具的理論基礎——這些工具讓你把詞符樣式寫成正規表示式，再編譯成快速的自動機。本定理以 Stephen Kleene 命名，他在 1951 年證明了它；星號所冠的也正是這位 Kleene 的名字。
取正規表示式 (a+b)*abb。Thompson 構造法把它變成一台 ε-NFA；子集構造法接著做出一台 DFA；而對該 DFA 做狀態消去法又還原出一個等價的正規表示式。這樣繞一圈顯示這三種視角可互換。
正規表示式與有限自動機描述的語言完全相同。
本定理等同的是表達能力，而非效率：把正規表示式轉成 DFA 可能讓狀態數呈指數爆炸，把 DFA 轉成正規表示式則可能讓表示式長度爆炸。語言相同，大小卻天差地別。