确定性有限自动机

---

有限自动机可以分为两种类型 -

• 确定性有限自动机 (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}，并且

转移函数 δ 如下表所示 -

其图形表示如下 -