[科普中国]-自动机理论

简介

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

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

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

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

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

术语自动机有如下基本概念：

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

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

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

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

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

详细内容常见自动机有以下几种：以电话交换机为主要实例的有限自动机，是自动机理论的基础，被应用到自动控制，生物系统中；由下推表组成的单项非确定程序的下推自动机；线性有界自动机；用来描述通用计算机计算能力的图灵机模型；进行与转移函数，转移状态有关输出的时序机；由一些基本语句构成程序框图的波斯特机；随即存储机；堆栈自动机；不受有限自动机做控制器和存储限制的无限自动机；统计自动机某一条件概率分布的概率自动机和细胞自动机。

数理语言学中研究抽象自动机的理论。抽象自动机是一种能够识别语言的抽象的装置，它不是具有物理实体的机器，而是表示计算机运算方式的抽象的逻辑关系系统，这样的抽象自动机可以用来检验输入的符号串是不是语言中合格的句子，如果是合格的句子，自动机就接收它，如果不是，就不接收它。如图所示：

自动机可分为有限自动机、后进先出自动机、线性有界自动机、图灵机等几种。它们对语言的识别能力各不相同。

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

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

该自动机识别的语言是否为空集；

该自动机识别的语言是否为有限集；

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

理论发展美国语言学家N.乔姆斯基等人建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能用 O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。

这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。这是语言学对于现代自然科学发生影响的一个明证。