确定性有限自动机

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

• 确定性有限自动机 (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}, 以及

转移函数 δ 如下表所示：

其图形表示如下：