什么是有限自动机(a finite automata)？

有限自动机（FA）是识别模式的最简单机器。有限自动机或有限状态机是具有五个元素或元组的抽象机器。它有一组用于从一个状态移动到另一个状态的状态和规则，但取决于应用的输入符号。基本上，它是数字计算机的抽象模型。

有限自动机由以下部分组成：

Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.

你需要知道的是有限自动机

• 有限状态机描述了一类正则语言。
• 有限状态机的计算能力低于图灵机。
• 它由有限个状态、有限组输入符号、自动机的初始状态和有限组从一个状态转移到另一个状态的转移规则组成。
• 输入带从左侧和右侧的长度都是有限的。
• 它识别一种称为常规语言的语言。
• 有限自动机中的转移函数可以表示为：δ：Q∑*→ Q
• 设计有限自动机更容易。
• 磁头只能从磁带上读取符号，但不能在磁带上写入符号。
• 头部只能沿正确方向移动。在双向自动机中，头部能够在两个方向上移动。
• 有限状态机只是一组状态和转换。它唯一的记忆是它处于什么状态。因此，内存状态的数量是有限的。

什么是图灵机(a turing machine)？

图灵机（TM）是一种数学模型，它由一条无限长的带组成，带被划分为输入给定的单元。它由读取输入磁带的磁头组成。状态寄存器存储图灵机的状态。读取输入符号后，将其替换为另一个符号，其内部状态发生变化，并从一个单元格向右或向左移动。如果TM达到最终状态，输入字符串将被接受，否则将被拒绝。

TM可以正式描述为7元组（Q，∑, δ、 q0，B，F）其中−

• Q是一组有限的状态
• X是磁带字母表
• ∑是输入字母表
• δ是过渡函数；δ：Q×X→ Q×X×{Left_shift，Right_shiff}。
• q0是初始状态
• B是空白符号
• F是最终状态的集合

关于图灵机你需要知道什么

• 图灵机描述了一类更大的语言，递归可枚举语言。
• 图灵机比有限状态机具有更强的计算能力。
• 除了有限数量的状态、有限数量的输入符号、自动机的初始状态和有限数量的从一种状态移动到另一种状态的转换规则之外，它还包含有限数量的磁带符号和磁带上的空白符号。
• 输入磁带从左起长度有限，但从右起长度无限。
• 它不仅可以识别常规语言，还可以识别上下文无关语言、上下文敏感语言和递归可枚举语言。
• 图灵机中的转移函数可以表示为：δ：Q×T→ Q×T×{L，R}，其中L和R表示磁带头的左右移动。
• 设计图灵机既困难又复杂。
• 磁头能够读写磁带上的符号。
• 头部可以双向移动。
• 图灵机是有限状态机加上磁带存储器。每次转换都可能伴随着磁带上的操作（移动、读取、写入）。其总的可能配置是任意大的，而不管程序的大小；它向无限扩展。

有限自动机(finite automata)和表格形式的图灵机(turing machine in tabular form)的区别