什么是有限自动机？

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

有限自动机表示

有限自动机可以用三种方式表示，如下所示 -

• 图形（转换图）
• 表格（转换表）
• 数学（过渡函数）

有限自动机的形式定义

有限自动机定义为 5 元组

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

• 问：有限集称为状态。
• Σ：称为字母表的有限集合。
• δ: Q × Σ → Q 是过渡函数。
• q0 ∈ Q 是开始或初始状态。
• F：最终或接受状态。

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

• 转变图
• 转换表
• 过渡函数

转变图

它是与对应于有限自动机状态的图的顶点相关联的有向图。

下面给出了转换图的示例 -

这里，

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

转换表

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

δ : Q × Σ → Q

在转换表中，考虑以下因素 -

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

转换表的示例如下 -

转换表如下 -

过渡函数

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

• 当前状态
• 输入符号

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

δ (当前状态, 当前输入符号) = 下一个状态

例如，δ(q0,a)=q1