有限自动机和图灵机的区别
在了解有限自动机(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是最终状态。
差异
有限自动机和图灵机之间的主要区别如下-