編譯器設計 - 有限自動機

有限自動機是一種狀態機，它以符號串作為輸入並相應地改變其狀態。有限自動機是正則表示式的識別器。當將正則表示式字串輸入到有限自動機時，它會為每個字元改變其狀態。如果輸入字串成功處理並且自動機達到其最終狀態，則表示它被接受，即剛剛輸入的字串被認為是正在使用的語言的有效標記。

有限自動機的數學模型包括

• 有限狀態集 (Q)
• 有限輸入符號集 (Σ)
• 一個起始狀態 (q0)
• 最終狀態集 (qf)
• 轉移函式 (δ)

轉移函式 (δ) 將有限狀態集 (Q) 對映到有限輸入符號集 (Σ)，Q × Σ ➔ Q

有限自動機構造

令 L(r) 為某個有限自動機 (FA) 識別的正則語言。

• 狀態：FA 的狀態用圓圈表示。狀態名稱寫在圓圈內。

• 起始狀態：自動機開始執行的狀態稱為起始狀態。起始狀態有一個指向它的箭頭。

• 中間狀態：所有中間狀態至少有兩個箭頭；一個指向它們，另一個從它們指向。

• 最終狀態：如果輸入字串成功解析，則預期自動機處於此狀態。最終狀態用雙圓圈表示。它可能指向它有任意奇數個箭頭，並指向它有偶數個箭頭。奇數箭頭的數量比偶數箭頭多一個，即奇數 = 偶數 + 1。

• 轉移：當在輸入中找到所需的符號時，從一個狀態到另一個狀態的轉移就會發生。在轉移時，自動機可以移動到下一個狀態或停留在同一狀態。從一個狀態到另一個狀態的移動顯示為一個指向目標狀態的有向箭頭。如果自動機停留在同一狀態，則繪製一個從狀態指向自身的箭頭。

示例：我們假設 FA 接受以數字 1 結尾的任何三位二進位制值。FA = {Q(q₀, q_f), Σ(0,1), q₀, q_f, δ}