在了解有限自动机(FA)和图灵机(TM)之间的区别之前，让我们先了解一下这些概念。
有限自动机是一种抽象的计算设备
它是一个系统的数学模型，它具有离散的输入、输出、状态和一组从状态到状态的转换，这些转换发生在来自字母表 Σ 的输入符号上
FA 可以在计算理论(TOC)中表示如下 -
图形（过渡图）
表格（转换表）
数学（转换函数）
有限自动机是一个五元组
M=(Q, Σ, δ,q0,F)
在哪里，
Q - 称为状态的有限集
Σ - 称为字母表的有限集
δ − Q × Σ → Q 是转移函数
q0 ε Q 是开始或初始状态
F - 最终或接受状态
图灵机比有限自动机和下推自动机都更强大。它们与我们建造的任何计算机一样强大。
图灵机可以正式描述为七个元组（Q，X，Σ，δ，q0，B，F）
在哪里，
Q 是有限状态集
X 是磁带字母表
Σ 是输入字母表
δ为转移函数：δ:QxX→QxXx{左移，右移}
q0 是初始状态
B是空白符号
F是最终状态。
有限自动机和图灵机之间的主要区别如下 -
| 先生没有。 | 有限状态机 | 图灵机 |
|---|---|---|
| 1 | 有限状态机描述了常规语言的类别。 | Turing Machines describe a much larger class of languages, the class of recursively enumerable languages. |
| 2 | 有限状态机描述了一小类不需要内存的语言。 | Turing Machines are the mathematical description of a computer and accept a much larger class of languages than FSMs do. |
| 3 | 有限状态机的计算能力低于图灵机。 | Turing Machines have has more computational power than FSM |
| 4 | 有限状态机只是一组状态和转换。它拥有的唯一内存是它所处的状态。因此，内存状态的数量是……有限的。 | 图灵机是一个有限状态机加上一个磁带存储器。每个转换都可能伴随对磁带的操作（移动、读取、写入）。它的总可能配置是任意大的，与程序的大小无关；它向无穷大扩展。 |