有限自动机论

有多种类型的有限状态自动机：接受器判断是否接受输入；转换器对给定输入产生一个输出。常见的转换器有 Moore 机 与 Mealy 机。Moore 机对每一个状态都附加有输出动作，Mealy 机对每一个转移都附加有输出动作。

有限状态自动机还可以分成确定与非确定两种。非确定有限状态自动机可以转化为确定有限状态自动机。

有限状态自动机识别的语言是正规语言。

有限状态自动机除了它在理论上的价值，还在数字电路设计、词法分析、文本编辑器程序等领域得到了应用。

自动机接受的所有字串构成了自动机识别的语言 L(M)。

非确定有限状态自动机

一个非确定有限状态自动机（NFA "Non-deterministic finite automaton"）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F)

有穷状态集合 Q ；

有穷输入字母表 Σ；

转移函数 δ: Q × Σ -> 2Q；

初始状态 q0；

终结状态集合 F，F 包含于 Q 。

自动机从初始状态 q0 起，逐一读入输入串（由输入字母表 Σ 的字母构成）的每一个字母，根据当前状态、输入字母和转移函数 δ 决定自动机的下一步状态；如果输入串结束时，自动机处于终结状态集合 F 的某一个状态，这表示自动机接受该字串；否则自动机不接受该字串。

非确定有限状态自动机与确定有限状态自动机的唯一区别是它们的转移函数不同。确定有限状态自动机对每一个可能的输入只有一个状态的转移。非确定有限状态自动机对每一个可能的输入可以有多个状态转移，接受到输入时从这多个状态转移中非确定地选择一个。

自动机接受的所有字串构成了自动机识别的语言 L(M)。

上述自动机接受的语言家族被称为正规语言(Regular Expression)。更强力的自动机可以接受更复杂的语言。比如:

自动机PDA

PDA(下推自动机)这种机器等同于 DFA (或 NFA)，除了它们额外的装备了栈形式的内存。转移函数 δ 也依赖于在栈顶的符号，并在每次转移时指定如何变更栈。非确定 PDA 接受上下文无关语言。

自动机LBA

LBA （线性有界自动机）是有限制的 图灵机；不使用无限磁带，它的磁带有同输入字元串成正比的空间。LBA 接受上下文有关语言。

自动机图灵机

它们是最强力的电脑器。它们拥有磁带形式的无限内存，和可以读取和变更磁带的磁头，它可在磁带上向任何方向移动。图灵机等价于演算法，是现代电脑的理论基础。图灵机判定递归语言并识别递归可枚举语言。

下面是三类有限自动机

确定有限自动机(DFA)

自动机的每个状态都有对字母表中所有符号的转移。

非确定有限自动机(NFA)

自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个状态的路径。如果一个转移是「未定义」的，自动机因此不知道如何继续读取输入，则拒绝这个字。

有ε转移的非确定有限自动机(FND-ε或ε-NFA)

除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外，它们可以做根本不关于符号的跳转。就是说，如果一个状态有标记著 ε 的转移，则 NFA 可以处在 ε-转移可到达的任何状态中，直接或通过其他有 ε-转移的状态。从一个状态 q 通过这种方法可到达的状态的集合叫做 q 的 ε-闭包。

尽管可以证明所有这些自动机都「可以接受同样的语言」。你总是可以构造接受与给定的 NFA M 同样语言的某个 DFA M。