確定性有限自動機

有限自動機可以分為兩種型別：

• 確定性有限自動機 (DFA)
• 非確定性有限自動機 (NDFA / NFA)

確定性有限自動機 (DFA)

在 DFA 中，對於每個輸入符號，都可以確定機器將轉移到的狀態。因此，它被稱為確定性自動機。由於它具有有限數量的狀態，因此該機器被稱為確定性有限機或確定性有限自動機。

DFA 的形式化定義

DFA 可以用一個 5 元組 (Q, ∑, δ, q₀, F) 表示，其中：

• Q 是一個有限的狀態集。

• ∑ 是一個有限的符號集，稱為字母表。

• δ 是轉移函式，其中 δ: Q × ∑ → Q

• q₀ 是初始狀態，從該狀態開始處理任何輸入 (q₀ ∈ Q)。

• F 是 Q 的一個或多個最終狀態集 (F ⊆ Q)。

DFA 的圖形表示

DFA 由稱為狀態圖的有向圖表示。

• 頂點表示狀態。
• 用輸入字母標記的弧表示轉移。
• 初始狀態用一個空入弧表示。
• 最終狀態用雙圓圈表示。

示例

令一個確定性有限自動機為：

• Q = {a, b, c},
• ∑ = {0, 1},
• q₀ = {a},
• F = {c}, 以及

轉移函式 δ 如下表所示：

其圖形表示如下：