自动机理论

在理论电脑科学中，自动机理论是对抽象机和它们能解决的问题的研究。自动机理论密切关联于形式语言理论，因为自动机经常按它们所能识别的形式语言类来分类。

基本描述

自动机是有限状态机（FSM）的数学模型。FSM是给定符号输入，依据（可表达为一个表格的）转移函数“跳转”过一系列状态的一种机器。在常见的FSM的“米利型有限状态机”（Mealy）变体中，这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。

逐个读取输入中的符号，直到被完全耗尽(把它当作有一个字写在其上的磁带，通过自动机的读磁头来读取它；磁头在磁带上前行移动，一次读一个符号)。一旦输入被耗尽，自动机被称为“停止”了。

依赖自动机停止时的状态，称呼这个自动机要么是“接受”要么“拒绝”这个输入。如果停止于“接受状态”，则自动机“接受”了这个字。在另一方面，如果它停止于“拒绝状态”，则这个字被“拒绝”。自动机接受的所有字的集合被称为“这个自动机接受的语言”。

但要注意，自动机一般不必须有有限数目甚至可数个状态。比如，量子有限自动机有不可数无限个状态，因为所有可能状态的集合是在复投影空间中所有点的集合。所以，量子有限自动机和有限状态机一样，都是更一般想法拓扑自动机的特殊情况，它的状态的集合是拓扑空间，而状态转移函数取自在这个空间上的所有可能函数。拓扑自动机经常叫做 M-自动机，简单是半自动机加上接受状态集合的补充，这里的集合交集确定初始状态是被接受还是被拒绝。

一般地说，自动机不需要严格的接受或拒绝一个输入；它可以按某个在零和一之间的概率接受它。还是用量子有限自动机作为展示例子，它只按某个概率接受输入。这个想法也是更一般情况几何自动机或度量自动机的特殊情况，它的状态的集合是度量空间，一个语言被这个自动机接受如果在初始点和接受状态的集合之间的距离关于这个度量是足够的小。

术语

自动机有如下基本概念：

符号

有某种意义或在这个机器上有效的任意数据(datum)。符号有时就叫做“字母”。

字

通过一些符号串接而形成的有限字符串。

字母表

符号的有限集合。字母表经常指示为 $\Sigma$，它是在字母表中所有字母的集合。

语言

字的集合，由给定字母表中的符号形成。可以是也可以不是无限的。

Kleene闭包

一个语言可以被认为是所有可能字的子集。所有可能字的集合可以被认为是所有可能的字符串串接的集合。形式上说，所有可能字符串的集合叫做自由幺半群。它被指示为 $\Sigma ^{*}$，上标 * 被称为 Kleene星号。

形式描述

自动机可以表示为5-元组 $\langle Q,\Sigma ,\delta ,q_{0},F\rangle$，这里的:

• Q 是状态的集合。
• ∑ 是符号的有限集合，我们称为这个自动机接受的语言的字母表。
• δ 是转移函数，就是

$\delta :Q\times \Sigma \rightarrow Q$。

(对于非确定自动机，空串是允许的输入)。

• q₀ 是开始状态，就是说自动机在还未处理输入的时候的状态(明显的 q₀∈ Q)。
• F 是叫做终止状态的 Q 中的状态的集合(就是 F⊆Q)。

给定一个输入字母 $a\in \Sigma$，可以使用简单的 currying 技巧写转移函数为 $\delta _{a}:Q\rightarrow Q$，就是说，写 $\delta (q,a)=\delta _{a}(q)$ 对于所有$q\in Q$。这种方式下转移可以被更简单的看待: 它就是“动作”于 Q 中一个状态上的生成另一个状态的某种东西。你可以接着考虑重复的应用函数复合于各种函数 $\delta _{a}$, $\delta _{b}$ 等等的结果。重复的函数复合形成一个幺半群。对于转移函数，这个幺半群叫做转移幺半群，有时也叫做“变换半群”。

给定一对字母 $a,b\in \Sigma$，可以通过坚持 ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ 定义一个新函数 ${\widehat {\delta }}$，这里的 $\circ$ 指示函数复合。明显的，可以递归的继续这个过程，这样就有了为所有字 $w\in \Sigma ^{*}$ 定义的函数 ${\widehat {\delta }}_{w}$ 的递归定义，因此有了映射

${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q.$

这个构造也可以反过来: 给定 ${\widehat {\delta }}$，可以重新构造一个 $\delta$，因此两个描述是等价的。

三元组 $\langle Q,\Sigma ,\delta \rangle$ 被称为半自动机。半自动机位于自动机底下，它们就是忽略了开始状态和接受状态的自动机。开始状态和接受状态的补充概念允许自动机做半自动机不能做的事情: 它们可以识别形式语言。确定有限自动机 $\langle Q,\Sigma ,\delta ,q_{0},F\rangle$ 接受的语言 $L$ 是:

$L=\{w\in \Sigma ^{\star }\,|\;{\widehat {\delta }}(q_{0},w)\in F\}$

就是说，一个自动机所接受的语言是在字母表 $\Sigma$ 之上所有字 w 的集合，当给定为自动机的输入的时候，将导致它停止于 $F$ 中的某个状态。被自动机接受的语言叫做可识别语言。

当状态集合 Q 是有限的时候，自动机被称为有限状态自动机，而所有可识别的语言是正则语言。事实上，有一个强等价: 对于所有正则语言，都有一个有限状态自动机，反之亦然。

如上所述，集合 Q 不必须是有限或可数的；它可以采用一般的拓扑空间；这就得到了一般的拓扑自动机。另一种可能的推广是度量自动机或“几何自动机”。在这种情况下，改变了对语言的接受: 替代在 ${\widehat {\delta }}(q_{0},w)\in F$ 中的最终状态的集合包含，以在最终状态 ${\widehat {\delta }}(q_{0},w)$ 和集合 $F$ 之间的度量距离的方式给出。特定类型的概率自动机是度量自动机，其度量空间是在概率空间上的测量。

有限自动机的分类

下面是三类有限自动机

确定有限自动机(DFA)

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

DFA

非确定有限自动机(NFA)

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

等价于前面例子 DFA 的 NFA

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

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

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

有限自动机的扩展

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

下推自动机(PDA)

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

线性有界自动机(LBA)

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

图灵机

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

有限状态自动机的最小化

主条目：确定有限状态自动机最小化

根据 Myhill-Nerode定理，在同构意义下接受一个正则语言的最少状态的确定有限状态自动机是唯一的。同时我们还存在有效的算法（时间开销是O(n²)的）构造出与给定确定有限状态自动机等价的最小化的确定有限状态自动机。

计算能力与判定问题

确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质，许多为其他自动机（下推自动机或图灵机）不能判定的问题，在有限状态自动机的情形下，都可以得到判定，并且存在有效的算法。

对一个确定有限状态自动机，下述判定问题都可以判定，并且存在有效的算法。

• 该自动机识别的语言是否为空集。
• 该自动机识别的语言是否为有限集。
• 该自动机是否与另一个确定有限状态自动机识别同一个的语言。

外部链接

• Visual Automata Simulator （页面存档备份，存于互联网档案馆）
• JFLAP （页面存档备份，存于互联网档案馆）
• Proyecto SEPa (in Spanish) （页面存档备份，存于互联网档案馆）
• Exorciser (in German) （页面存档备份，存于互联网档案馆）

引用

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (2nd Edition)
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X.  Part One: Automata and Languages, chapters 1–2, pp.29–122. Section 4.1: Decidable Languages, pp.152–159. Section 5.1: Undecidable Problems from Language Theory, pp.172–183.