克萊尼定理：正規表示式等同自動機

同一個想法的兩種語言

在本階梯前兩篇，你學會了用三個運算——聯集、串接與克萊尼星號——寫出一個正規表示式，再讀出它所指稱的那一組字串。這給了你一種代數式、一行就打得出來的方式來指定模式，例如用 (a|b)*abb 表示「{a, b} 上任何以 abb 結尾的字串」。而在更早的階梯，你有一種截然不同的指定方式：畫一台有限自動機——一台像旋轉閘門的機器，只記得目前狀態，並依每個符號沿箭頭移動。

這兩種描述感覺天差地遠。一個是你打出來的符號串；另一個是你畫出來的泡泡與箭頭圖。於是自然會擔心：也許正規表示式能表達某些自動機無法識別的模式，或者自動機能識別某些表示式無法捕捉的模式。克萊尼定理乾淨俐落地化解了這個擔憂，而答案是再漂亮不過的：兩者在觸及範圍上完全等價。

定理到底主張了什麼

克萊尼定理說：一個語言能被某個正規表示式描述，若且唯若它能被某台有限自動機識別。再結合你早已信賴的結論——DFA、NFA 與 ε-NFA 識別的恰好是同一類，也就是正規語言——你現在得到一類語言，配上三個可互換的名字：「可用正規表示式描述的」、「可被有限自動機識別的」、以及「正規的」。它們是望進同一個房間的三扇窗。

「若且唯若」其實是必須雙雙證明的兩個主張，而每個方向都是一個你可以親手執行的具體構造。正向：給定任何正規表示式，建一台能識別其語言的機器——這就是 Thompson 構造法，它組裝出一台小型的 ε-NFA。反向：給定任何有限自動機，抽出一個指稱其語言的正規表示式——這就是狀態消去法，由一條叫做 Arden 規則的代數恆等式驅動。下一篇會配完整範例慢慢走過兩個流程；這裡我們希望你真正理解每一步為什麼成立，以及它換來了什麼。

正向：從表示式建出機器

正向是靠結構歸納法運作的——正是更早階梯教你的那種證明形狀。一個正規表示式是由微小的基本情形（空語言符號、epsilon 的符號，以及字母表 Sigma 中的單一字母）用三個運算黏接而成。Thompson 構造法為每個基本情形給出一台對應的機器，並為每個運算給出把兩台子機器接線在一起的方法。只要這些都辦得到，那麼依歸納法，每一個正規表示式都有對應的機器。

讓接線變得乾淨到不可思議的魔法成分，就是你早一篇遇過的、不消耗任何輸入的免費 ε-轉移。每一台 Thompson 子機器都遵守嚴格的紀律：恰好一個起始狀態、恰好一個接受狀態，且沒有任何雜散箭頭射進起始狀態或射出接受狀態。正是這種一致的形狀，讓你能像疊樂高積木一樣用 ε-箭頭把零件黏在一起，而接縫不會漏出不想要的字串。

基本情形：對單一字母 a，建 start --a--> accept。對 epsilon，建 start --epsilon--> accept。對空語言，建一個 start 與一個分開的 accept，中間沒有任何箭頭（什麼都不接受）。
聯集 (R|S)：加一個新的 start，用 ε-箭頭射進 R 與 S 兩台機器的起始狀態，再加一個新的 accept，用 ε-箭頭從兩者的接受狀態射過來——讓你分身進入任一分支。
串接 (RS)：把它們首尾相黏——從 R 的接受狀態拉一條 ε-箭頭到 S 的起始狀態，於是字串必須先跑過 R 再跑過 S。
星號 (R*)：加一個同時也是接受狀態的新 start（以容許零份拷貝＝epsilon），用 ε-箭頭射進 R 的起始狀態，並從 R 的接受狀態拉 ε-箭頭回到 R 的起始狀態（以重複）以及向前接到新的接受狀態。

反向：從機器讀出表示式

另一個方向第一次看到時更令人驚訝。拿任何一台自動機，連同它纏成一團的狀態與箭頭，把它一個狀態一個狀態地壓縮——直到只剩一個 start 與單一個 accept，中間一條箭頭標著答案那個正規表示式。這就是狀態消去法。為了讓壓縮過程中標籤乖乖聽話，我們先把機器升格為廣義 NFA：箭頭上可以標的不只是單一符號，而是一整個正規表示式。

當你刪掉一個中間狀態 q 時，必須保留所有曾經取道 q 的路徑。若有一條箭頭進入 q 標著 X，q 有一條自迴圈標著 Y，且有一條箭頭離開 q 標著 Z，那麼刪掉 q 就把它們換成一條直接的箭頭，標著 X Y* Z——「走進去、在 q 上迴圈任意多次、走出來」。那個 Y* 正是克萊尼星號發揮作用之處：自迴圈可以走零次或多次，這正是星號的意思。你對 q 的每一對鄰居都重複這件事，並與原本已連接它們的任何箭頭取聯集。

Eliminating state q  (X = arrow in, Y = self-loop, Z = arrow out):

        X            Z
   p ------>  ( q )  ------> r        Y is q's self-loop
                ^_____|
                  Y

   after deleting q, the path p -> r is labelled:

        p --[ X Y* Z ]--> r        (union this with any old p->r label)

Why Y* ?  the loop on q may be used 0, 1, 2, ... times,
and "0 or more repetitions" is exactly the Kleene star.

狀態消去法的唯一規則：取道 q 的路徑變成 X Y* Z。自迴圈化為星號，正是全部的訣竅。

這幅圖背後是一個乾淨的代數事實——Arden 規則：若一組字串 X 滿足方程式 X = A X | B（其中 A 不含 epsilon），則唯一解為 X = A* B。你可以把一台有限自動機讀成這樣的一組方程式——每個狀態一個未知數，代表「從這裡通往接受的那些字串」——而 Arden 規則讓你解出有迴圈狀態的遞迴方程式：把迴圈變成星號，與 X Y* Z 那一步完全對應。

為什麼這座橋很重要

因為轉換是雙向的，你可以挑比較容易的那種語言來設計，需要時再翻譯。要證明某語言是正規的？只要為它寫一個正規表示式——克萊尼定理立刻保證機器存在，連圖都不必畫。想證明正規語言的某個封閉性質，或在編譯器裡真的去掃描文字？把正規表示式變成自動機跑起來就行。這座雙向橋正是真實工具底下的引擎：文字編輯器裡的正規表示式引擎，或編譯器詞法分析器所用的掃描器，通常會把你的模式編譯成一台有限自動機，然後讓單一指標在你的輸入上飛奔而過。

但這裡有一個你後半輩子當程式設計師都必須帶著走的誠實警告。許多程式語言裡的「正規表示式」並不是克萊尼定理所談的那個數學物件。它們外掛了額外功能——最重要的是反向參照（比對先前看過的同一段文字，例如 (.+)\1）以及前瞻／後顧。一個反向參照能描述可被證明不正規的語言，因此沒有任何有限自動機能識別它們；那份等價對這些功能根本不適用。