自动机：自动机是有限状态机(FSM)的数学模型。
状态机：我们现在所说的状态机一般是有限状态机（FSM）的简称。
有限自动机： 有限自动机（Finite Automata Machine）是计算机科学的重要基石，它在软件开发领域内通常被称作有 限状态机（Finite State Machine），是一种应用非常广泛的软件设计模式（Design Pattern）。
有限状态机：
对有限状态机的定义：有限状态机是具有一个基本内部记忆的抽象机器模型，定义如下：
元组
1、可识别的定义：
存在图灵机，对语言中每个字符串，该图灵机均接受。对语言外的每个字符串，该图灵机拒绝或不停机。
2、可判定的定义：
存在图灵机，对语言中每个字符串，该图灵机均接受。对语言外的每个字符串，该图灵机拒绝。
显然判定一个语言的图灵机也是识别该语言的图灵机。也就是说可判定推出可识别。
换句话说，可判定的条件比可识别的要强。实际上，一个语言可判定当且仅当它和它的补都是可识别的。
注意:
图灵可识别语言和图灵可判定语言的区别：
若S是图灵可识别语言，则只需存在一台图灵机M，当M的输入时，M一定会停机并进入接受状态；当M的输入时，M可能停机并进入拒绝状态，或者永不停机。
而若S是图灵可判定语言，则必须存在图灵机M，使得对于任意输入串，M总能停机，并根据Ω属于或不属于S分别进入接受或拒绝状态。并不是所有的语言都是图灵可识别的，可以证明存在图灵不可识别语言。