自动机理论

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

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

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

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

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

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

自动机有如下基本概念：

自动机可以表示为5-元组 ${\displaystyle ⟨<!--\; ⟨\; -->Q,\mathrm{\Sigma <!--\; \Sigma \; -->},\mathrm{\delta <!--\; \delta \; -->},q_0,F⟩<!--\; ⟩\; -->}$ 的集合，当给定为自动机的输入的时候，将导致它停止于 ${\displaystyle F}$ 是有限的时候，自动机被称为有限状态自动机，而所有可识别的语言是正则语言。事实上，有一个强等价: 对于所有正则语言，都有一个有限状态自动机，反之亦然。

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

下面是三类有限自动机

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

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

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

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

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