狀態消去法（state elimination）

Thompson 構造法從表示式走向機器；狀態消去法則走相反方向，從有限自動機回到正規表示式。它的畫面是小心翼翼的拆除：你一次敲掉自動機的一個狀態，每敲掉一個就修補存活下來的箭頭，使語言保持完全不變，直到只剩下一個起始與一個接受，之間僅有一條以答案為標籤的箭頭。

它作用在廣義 NFA 上——這種自動機的轉移不是以單一符號為標籤，而是以整個正規表示式為標籤。要移除一個內部狀態 q，你檢視每一對「有箭頭進入 q 的狀態 p」與「有箭頭離開 q 的狀態 r」，並加上一條從 p 到 r 的直接箭頭，其標籤要捕捉所有經過 p 到 q 到 r 的路徑。若舊標籤是 A（p 到 q）、B（q 到 q，一個自迴圈）與 C（q 到 r），則新的 p 到 r 標籤增添 A B* C；若 p 到 r 本來已有標籤 D，就把它聯集進去得到 D + A B* C。q 消失後，你對下一個狀態重複此步驟。當只剩起始與單一接受時，剩下那條箭頭上的標籤就是整個語言的一個正規表示式。

狀態消去法證明了 Kleene 定理的反向方向，也是用紙筆執行它最具體的方式。先給一個實用提示：加一個全新的單一起始狀態（用 ε 進入舊起始），以及一個全新的單一接受狀態（用 ε 從每個舊接受出發），並讓機器沒有其他接受狀態，這樣帳目處理才一致。誠實的提醒是：消去狀態的順序不會改變語言，卻可能大幅改變最終表示式的大小，最壞情況會爆炸，所以挑選一個好的消去順序確實是門技藝。