兩個方向，一條定理
在上一篇導覽裡，Kleene 定理以「事實」的身分告訴你：正規表示式與有限自動機所描述的，恰好是同一族語言。一條你無法拿來計算的事實只算用了一半，所以這篇導覽要把定理變成兩套具體的、搖一搖把手就能跑的程序。一個方向拿一個樣式，造出一台「恰好」接受該樣式所表示之字串的機器；另一個方向拿一台機器，擠出一個「恰好」描述它所接受之字串的樣式。
為何兩個方向都要管？因為每個方向都是不同實務任務的主力。從樣式到機器，正是搜尋工具或詞法分析器在你遞給它一個 regex 時所做的事：它把樣式編譯成某種能跑得很快的東西。從機器到樣式，則是你拿來「證明事情」的辦法——一旦某個語言擁有任何一台有限自動機，你就有了「它存在一個正規表示式」的保證，而這套程序甚至會幫你把那個表示式寫出來。兩者合起來，就是「正規表示式等於自動機」這句口號底下的機房。
樣式轉機器：Thompson 建構法
從樣式走到機器的訣竅，是「拒絕耍小聰明」。回想本階稍早所學：每個正規表示式都是由基本情形（單一符號、epsilon、或空語言）出發，靠著恰好三個運算——聯集、串接、以及 Kleene 星號——黏合而成。所以我們就照著樣式被建起來的方式去建機器：每一塊零件配一個小巧的裝置，再用你上一階見過的免費移動把它們咬合起來。結果是一台 epsilon-NFA，而這份食譜就叫 Thompson 建構法。
每個小裝置都信守一條嚴格的承諾：恰好一個起始狀態、恰好一個接受狀態，且接受狀態沒有任何箭射出、起始狀態也沒有任何外來的箭射入。正是這份紀律，讓零件能像凸點位置固定的樂高積木一樣盲接在一起。單一符號 'a' 就是兩個狀態，中間一支 a 箭。A 與 B 的串接，就是從 A 的接受拉一支 epsilon 箭到 B 的起始。A 與 B 的聯集，加上一個新起始（用 epsilon 箭分別射入兩者），再加一個新接受（讓兩個舊接受各用 epsilon 箭抵達）。星號則把一台機器裹進一對新的起始／接受裡，配上 epsilon 箭，讓你可以整個跳過它、或繞回去重複它。
Thompson gadgets (S = start, A = accept):
symbol a : S --a--> A
epsilon : S --eps--> A
concat M.N : S_M ...(M)... A_M --eps--> S_N ...(N)... A_N
union M|N : eps eps
S ---------> S_M ...A_M ------\
| > A
\---------> S_N ...A_N --------/
eps eps
star M* : ___________eps__________
/ v
S --eps--> S_M ...(M)... A_M --eps--> A
^___________eps___/
(S --eps--> A also, to allow zero copies)機器轉樣式：狀態消去法
走另一個方向感覺更難——你要怎麼從一團糾纏的狀態與箭裡，讀出一個整齊的表示式？關鍵想法是：讓箭去攜帶正規表示式，而不只是單一符號。一台箭以整個樣式為標籤的機器，就是一台廣義 NFA（GNFA）。一台普通的自動機本來就已經是它了：只是每支箭剛好以「單一符號的樣式」為標籤罷了。現在我們一次刪一個狀態，而每當一個狀態離場，我們就修補它周圍的箭，好讓語言保持不變——存活下來的箭上的樣式會脹大，把原本要穿過被刪狀態的那些路徑全吸收進去。
- 先整理乾淨。加一個全新的起始狀態，用一支 epsilon 箭射進舊的起始；再加一個全新的、唯一的接受狀態，從每個舊接受狀態各拉一支 epsilon 箭進來。這保證了單一入口與單一出口，而且沒有別的箭來搶它們。
- 挑任一個既非新起始、也非新接受的狀態，準備把它撕掉。
- 對那個注定要被刪的狀態 q，檢視每一對「射入的狀態 p」與「射出的狀態 r」。舊的路徑 p -> q -> r 讀作：p->q 上的標籤，接著（q 的自迴圈標籤加上星號，以允許繞圈任意多次），再接著 q->r 上的標籤。
- 把那個合併後的樣式，用聯集（一個 OR）加到既有的 p->r 箭上。具體說，新的 p->r 標籤變成 (舊的 p->r) | (p->q)(q->q)*(q->r)。然後刪掉 q 與它所有的箭。
- 重複到只剩起始與接受兩個狀態為止。它們之間僅存的那一支箭上的標籤，就是整台機器之語言的正規表示式。
第 4 步的那條公式就是全部的祕密，所以慢慢讀。要抹掉 q，你必須把「穿過它」的每一種方式都算進去：從 p->q 進來，視需要在 q 的自迴圈上繞任意多次（那就是星號），再從 q->r 離開。任何原本就從 p 直通 r 的東西仍然有效，所以你把兩者用 OR 接起來。又因為刪除狀態的「順序」永遠不會改變語言——只會改變最終表示式的「長相」——你大可採用任何能讓記帳負擔最小的順序去刪。
和代數同一個想法：Arden 規則
還有第二種、等價的取樣式方法，感覺就像在解聯立方程式，而它仰賴一條俐落的恆等式，叫做 Arden 規則。每個狀態寫一條方程式，其中的未知數是「能把機器從這個狀態驅動到接受的那組字串」（或從起始驅動到此處——兩種版本都有人用）。每條方程式都說：我的語言，是「對我射出的每一支箭，取一個符號接上下一個狀態的語言」的聯集，若我是接受狀態再加上 epsilon。然後你把這個系統解出來。
Arden 規則正是破解自我參照的工具。若一個變數 X 滿足 X = A X | B——意思是「X 是若干個 A 再接更多的 X，否則就是 B」——那麼唯一的最小解是 X = A* B，前提是 A 不含 epsilon。把它唸出來：要抵達一個 B，就在 A 上想繞幾圈就繞幾圈（那就是星號），最後以 B 收尾。它是你在狀態消去法裡用過的那個星號自迴圈的代數雙胞胎；這兩套程序其實是同一個想法換了身衣裳，而且答案永遠一致（頂多差在用第 2 篇導覽的代數恆等式把表示式改寫一下）。
這趟來回究竟證明了什麼
把兩個方向背靠背擺好，你就有了一個貨真價實的證明，而不只是一句口號。Thompson 建構法表明：每個正規表示式都有一台有限自動機；狀態消去法（或 Arden 規則）則表明：每台有限自動機都有一個正規表示式。兩個方向都不會丟掉或多出任何一個字串。這個雙向等價，恰恰就是Kleene 定理，如今還配上了撐起它的機械。又因為我們知道有限自動機的各種口味——DFA、NFA、epsilon-NFA——都接受同一個類，你大可從最方便的那個出發，在這四種表示法之間自由地來回轉換。
兩個誠實的提醒。其一，這一切完全活在正規語言之內：來回轉換永遠不會把一個語言變大，所以像 a* 這樣的樣式始終是正規的、也始終是無窮的——記住，正規並不等於有限。其二，由 Thompson 造出的自動機是一台 epsilon-NFA，所以它的精簡是向非確定性「借」來的，而非確定性是一種設計上的方便，不是免費的硬體；把它確定化的子集合建構法，在最壞情況下能把 n 個狀態變成 2^n 個。轉換永遠是「可能」的；卻不見得永遠是「小」的。
最後，搭一座通往下一篇的橋。現實世界的 regex 引擎倚靠的正是這條管線——樣式、然後 NFA、再來確定化的模擬——這也是為什麼一個寫得好的樣式，能在「與輸入長度成線性」的時間內搜尋文字。但工程上的 regex 又外掛了像反向參照與前瞻這類沒有任何有限自動機能表達的功能，而那些功能可能讓比對膨脹到指數時間。第 5 篇導覽會認真看待這個警告；你在這裡建起的，正是引擎在偏離地圖之前所從之出發的那個乾淨的數學核心。