什么是有限自动机？

有限自动机是一种抽象的计算设备。它是一个数学模型，具有离散的输入、输出、状态和一组状态转换，这些转换发生在来自字母表Σ的输入符号上。

有限自动机的表示

有限自动机可以用以下三种方式表示：

• 图形化（状态转换图）
• 表格化（状态转换表）
• 数学化（状态转换函数）

有限自动机的形式定义

有限自动机定义为一个五元组

M=(Q, Σ, δ,q0,F)

其中，

• Q：称为状态的有限集合。
• Σ：称为字母表的有限集合。
• δ：Q × Σ → Q 是状态转换函数。
• q0 ∈ Q 是起始状态或初始状态。
• F：终止状态或接受状态。

有限自动机可以表示如下：

• 状态转换图
• 状态转换表
• 状态转换函数

状态转换图

它是一个有向图，图的顶点对应于有限自动机的状态。

下面是一个状态转换图的示例：

这里，

• {0,1}：输入
• q1：初始状态
• q2：中间状态
• qf：终止状态

状态转换表

它基本上是状态转换函数的表格表示，该函数接受两个参数（一个状态和一个符号）并返回一个值（“下一个状态”）。

δ : Q × Σ → Q

在状态转换表中，考虑以下因素：

• 行对应于状态。
• 列对应于输入符号。
• 条目对应于下一个状态。
• 起始状态用 -> 标记。
• 接受状态用 * 标记。

状态转换表示例如下：

状态转换表如下：

状态转换函数

状态转换函数用 δ 表示。下面提到的两个参数是传递给此状态转换函数的参数。

• 当前状态
• 输入符号

状态转换函数返回一个状态，可以称为下一个状态。

δ (current_state, current_input_symbol) = next_state

例如，δ(q0,a)=q1

Bhanu Priya

更新于：2021年6月11日

15K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始学习