正規表示式與 Kleene 定理
廣義 NFA（generalized NFA）
普通的 NFA 把每條轉移標上單一符號或 ε。廣義 NFA 放鬆了這點：每條轉移都可以標上一整個正規表示式。它是狀態消去法的工作檯面，是一種鷹架，讓你把一台複雜的自動機塌縮成一個正規表示式，而過程中不會弄丟語言。
具體來說，GNFA 每走一條轉移就讀入一段輸入：一條標著表示式 E 的箭頭，可以藉由消耗 L(E) 中的任何字串來通過。為了讓狀態消去法乾淨利落，GNFA 通常維持一種正規形式：恰好一個起始狀態且無入箭頭、恰好一個與起始相異的接受狀態且無出箭頭，而每一對其他有序的狀態之間恰有一條箭頭（可能標著 ∅ 表示「無轉移」）。在這種形式下，一次移除一個內部狀態並合併它的繞道路徑，會讓 GNFA 維持良好形式，直到只剩起始到接受的那條箭頭為止。
GNFA 是一個概念工具，而非你會為其自身能力而研究的模型；它識別的恰好就是正規語言，與普通 NFA 相同，因為每個正規表示式標籤原則上都能展開回狀態與單符號轉移。它的價值純粹在於作為記帳裝置，讓 Kleene 定理「有限自動機到正規表示式」的方向變得整潔且可證明地正確。
從一台 3 狀態的 DFA 出發，加一個全新起始與一個全新接受（用 ε 箭頭），再重新標記成 GNFA 正規形式。接著逐一消去原本的三個狀態；最終停在起始到接受箭頭上的標籤，就是你想要的正規表示式。
GNFA 讓轉移得以承載整個正規表示式。
GNFA 的能力不超過普通 NFA；它仍只識別正規語言。它存在的唯一目的是讓狀態消去法井然有序，而非擴展自動機所能做的事。
又稱
另見