自动机（automata ）
自动机 automaton 原来是模仿人和动物的行动而做成的机器人的意思。但是现在已被抽象化为如下的机器。时间是离散的（t=0，1，2……），在每一个时刻它处于所存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个时刻的内部状态就由现在的输入和现在的内部状态所决定。每个时刻的输出只由那个时刻的内部状态所决定。作为自动机的例子可以举出由McCulloch-pitts的神经模型组合所得到的神经网络模型、数字计算机等。
形式描述对信号序列进行逻 辑 处理的装 置。在自动控制领域内，是指离散数字系统的动态数学模型，可定义为一种逻辑结构，一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中，分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。在语言学中则把自动机作为语言识别器，用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型，用来研究神经生理活动和思维规律，探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型，研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数，研究各种算法。现代自动机的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。自动机可按其变量集和函数的特性分类，也可按其抽象结构和联结方式分类。主要有：有限自动机和无限自动机、线性自动机和非线性自动机、确定型自动机和不确定型自动机、同步自动机和异步自动机、级联自动机和细胞自动机等。
有限自动机的分类下面是三类有限自动机
确定有限自动机(DFA)
自动机的每个状态都有对字母表中所有符号的转移。
非确定有限自动机(NFA)
自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个状态的路径。如果一个转移是「未定义」的，自动机因此不知道如何继续读取输入，则拒绝这个字。
有ε转移的非确定有限自动机(FND-ε或ε-NFA)
除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外，它们可以做根本不关于符号的跳转。就是说，如果一个状态有标记著 ε 的转移，则 NFA 可以处在 ε-转移可到达的任何状态中，直接或通过其他有 ε-转移的状态。从一个状态 q 通过这种方法可到达的状态的集合叫做 q 的 ε-闭包。
尽管可以证明所有这些自动机都「可以接受同样的语言」。你总是可以构造接受与给定的 NFA M 同样语言的某个 DFA M。
有限自动机的扩展上述自动机接受的语言家族被称为正则语言家族。更强力的自动机可以接受更复杂的语言。比如:
下推自动机(PDA)
这种机器等同于 DFA (或 NFA)，除了它们额外的装备了栈形式的内存。转移函数 δ 也依赖于在栈顶的符号，并在每次转移时指定如何变更栈。非确定 PDA 接受上下文无关语言。
线性有界自动机(LBA)
LBA 是有限制的图灵机；不使用无限磁带，它的磁带有同输入字元串成正比的空间。LBA 接受上下文有关语言。
图灵机
它们是最强力的电脑器。它们拥有磁带形式的无限内存，和可以读取和变更磁带的磁头，它可在磁带上向任何方向移动。图灵机等价于演算法，是现代电脑的理论基础。图灵机判定递归语言并识别递归可枚举语言。
有限状态自动机的最小化根据 Myhill-Nerode定理，在同构意义下接受一个正则语言的最少状态的确定有限状态自动机是唯一的。同时我们还存在有效的演算法（时间开销是O(n2)的）构造出与给定确定有限状态自动机等价的最小化的确定有限状态自动机。
计算能力与判定问题确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质，许多为其他自动机（下推自动机或图灵机）不能判定的问题，在有限状态自动机的情形下，都可以得到判定，并且存在有效的演算法。
对一个确定有限状态自动机，下述判定问题都可以判定，并且存在有效的演算法。
该自动机识别的语言是否为空集。
该自动机识别的语言是否为有限集。
该自动机是否与另一个确定有限状态自动机识别同一个的语言。