Automata Theory 简明教程

Deterministic Finite Automaton

有限自动机可分为两类：

  1. Deterministic Finite Automaton (DFA)

  2. 非确定有限自动机（NDFA/NFA）

Deterministic Finite Automaton (DFA)

在 DFA 中，对于每个输入符号，都可以确定机器将移动到的状态。因此，它被称为 Deterministic Automaton 。由于它具有有限数量的状态，因此机器被称为 Deterministic Finite Machine 或 Deterministic Finite Automaton. 。

Formal Definition of a DFA

DFA 可以表示为 5 元组 (Q, ∑, δ, q0, F)，其中 −

  1. Q 是一个有限的状态集。

  2. ∑ 是称为字母表的有限符号集。

  3. δ 是转换函数，其中 δ: Q × ∑ → Q

  4. q0 是处理任何输入的初始状态 (q0 ∈ Q)。

  5. F 是 Q 的一组终态/状态 (F ⊆ Q)。

Graphical Representation of a DFA

DFA 由称为 state diagram 的有向图表示。

  1. 顶点表示状态。

  2. 带有输入字母标签的弧线表示转换。

  3. 初始状态由一条空传入弧线表示。

  4. 终态由双圆圈表示。

Example

让确定性有限自动机为→

  1. Q = {a, b, c}，

  2. ∑ = {0, 1},

  3. q0 = {a},

  4. F = {c}, and

过渡函数 δ 如下表所示−

Present State

输入 0 时的下一状态

输入 1 时的下一状态

a

a

b

b

c

a

c

b

c

它的图形表示如下−

dfa graphical representation