数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究区分有限自动机和图灵机
在了解有限自动机 (FA) 和图灵机 (TM) 之间的区别之前，让我们先了解一下这些概念。
有限自动机
有限自动机是一种抽象的计算设备
它是一个系统的数学模型，具有离散的输入、输出、状态和状态之间的转换集，这些转换是在来自字母表 Σ 的输入符号上发生的。
有限自动机表示
在计算理论 (TOC) 中，FA 可以表示为以下形式：
图形 (状态转换图)
表格 (状态转换表)
数学 (状态转换函数)
有限自动机的形式化定义
有限自动机是一个五元组
M=(Q, Σ, δ,q0,F)
其中，
Q - 有限集称为状态
Σ - 有限集称为字母表
δ - Q × Σ → Q 是状态转换函数
q0 ε Q 是起始状态或初始状态
F - 结束状态或接受状态
图灵机
图灵机比有限自动机和下推自动机都强大。它们与我们构建的任何计算机一样强大。
图灵机的形式化定义
图灵机可以正式描述为七元组 (Q,X, Σ,δ,q0,B,F)
其中，
Q 是一个有限的状态集
X 是带字母表
Σ 是输入字母表
δ 是一个状态转换函数：δ:QxX→QxXx{左移，右移}
q0 是初始状态
B 是空白符号
F 是结束状态。
差异
有限自动机和图灵机之间的主要区别如下：
| 序号 | 有限状态机 | 图灵机 |
|---|---|---|
| 1 | 有限状态机描述正则语言类别。 | 图灵机描述更大类别的语言，即递归可枚举语言类别。 |
| 2 | 有限状态机描述一类较小的语言，其中不需要内存。 | 图灵机是计算机的数学描述，并且接受比 FSM 更多的语言类别。 |
| 3 | 有限状态机的计算能力低于图灵机。 | 图灵机的计算能力高于 FSM |
| 4 | 有限状态机只是一组状态和转换。它唯一的存储是它所处的状态。因此，内存状态的数量是……有限的。 | 图灵机是一个有限状态机加上一个磁带存储器。每次转换都可能伴随着对磁带的操作（移动、读取、写入）。无论程序的大小如何，它所有可能的配置都是任意大的；它扩展到无限大。 |
更新于：2021年6月15日
5K+ 浏览量
广告