确定性有限自动机

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

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

转移函数 δ 如下表 − 所示

其图形表示如下 −