有限自动机的不同类型有哪些？

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

有限自动机的形式化定义

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

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

其中：

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

类型

有限自动机的不同类型如下：

• 无输出的有限自动机
  • 确定性有限自动机 (DFA)。
  • 非确定性有限自动机 (NFA 或 NDFA)。
  • 具有ε-转移的非确定性有限自动机 (ε-NFA 或 ε-NDFA)。
• 有输出的有限自动机
  • Moore 机。
  • Mealy 机。

不同自动机（DFA）的定义

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

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

其中：

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

非确定性有限自动机 (NFA)

NFA 也具有与 DFA 相同的五个状态，但状态转移函数不同，如下所示：

δ: Q × Σ → 2^Q

非确定性有限自动机定义为一个五元组：

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

其中：

• Q：状态的有限集合
• Σ：输入符号的有限集合
• q0：初始状态
• F：最终状态
• δ：状态转移函数：Q × Σ → 2^Q

Mealy 机

Mealy 机由六元组 (Q, q0, Σ, O, δ, λ') 描述

其中：

• Q：状态的有限集合
• q0：机器的初始状态
• Σ：输入字母表的有限集合
• O：输出字母表
• δ：状态转移函数，其中 Q × Σ → Q
• λ'：输出函数，其中 Q × Σ → O

Moore 机

Moore 机由六元组 (Q, q0, Σ, O, δ, λ) 描述

其中：

• Q：状态的有限集合
• q0：机器的初始状态
• Σ：输入符号的有限集合
• O：输出字母表
• δ：状态转移函数，其中 Q × Σ → Q
• λ：输出函数，其中 Q → O

Bhanu Priya

更新于：2021年6月11日

13K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习