有限状态自动机模型

刘 威

（大连海洋大学）

当我们用计算机进行问题的求解时，首先需要用适当的数据进行问题表示，然后再设计相应的算法对这些数据进行变换处理来获得问题的求解结果。因此，对问题进行建模和形式化表示，然后进行处理是进行计算机求解的基本途径。数理逻辑、自动机理论给出了如何描述一些基本问题以及如何建立问题的抽象表示，并通过对这些抽象化的表示的性质和它的变化方法进行研究。这些模型都是问题数学模型的典范，给计算机问题求解提供了坚实的理论基础，是计算机求解问题的重要方法和思想。

计算机科学与技术学科是以数学和电子学科为基础发展起来的，一方面研究计算机领域中的一些普遍规律，描述计算的基本概念与模型，其重点是描述现象、解释规律。另一方面是包括计算机硬件、软件的计算机系统设计和实现的工程技术，简单地说，计算机科学与技术学科通过在计算机上建立模型并模拟物理过程来进行科学调查和研究，它系统地研究信息描述和变换算法，主要包括信息描述和变换算法的理论、分析、效率、实现和应用。

所有问题的描述都要以计算机能识别的语言来实现，计算机语言的文法描述提供了生成语言的手段，但是，对于语言句子的识别来说，我们需要一些识别语言的模型，我们可以称这种模型为语言的识别模型。这种识别模型应该满足必要的约束条件，首先模型具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，模型可以在不同的状态下完成特定语言的识别。我们可以将输入数据中出现的符号组成一个字符的列表。模型将输入数据作为线性表来进行处理和变换。模型有一个初始的状态，它是系统的开始状态，系统在这个状态下开始进行问题的求解。模型中还有一些状态表示它到目前为止所读入的字符构成的字符串是模型从开始状态引导到这种状态的所有字符串构成的语言就是模型所能识别的输入。我们可以将此模型对应成有穷状态自动机的物理模型，在处理问题的时候，它可以接受一个关于问题的输入数据，数据以字符串的形式提供，我们把这些输入数据划分成一系列的小部分，每个部分由若干字符组成，为了不让输入数据量影响该模型对问题的处理，我们约定，输入数据从开始输入时的时间点开始处理，输入状态可以是无穷的，这就是说，从输入第一部分数据开始，输入端可以有任意长度的输入序列。而且，模型有一个有穷状态控制器，该控制器的状态只有有穷多个，并且规定，模型的每一个动作分为三步，读入待输入的字符，根据当前的状态和读入的字符改变有穷控制器的状态，读下一部分输入数据。计算机的各个组成部分，既包括硬件系统也包括软件系统，都可以对其进行形式化的定义，计算机的硬件系统包括中央处理器、存储器、外部设备，可以形式化地用一个三元组来描述，对计算机个各个硬件部分进行管理的软件的功能也可以用形式化的方法来描述，例如，操作系统的各个功能模块、处理器管理、线程调度、文件系统、设备驱动程序、网络通信管理、虚拟内存管理等都可以进行形式化的定义。有穷状态机就是进行这种形式化定义的模型，有穷状态机是一个五元组，分别是描述状态的有穷非空集合，它称为有穷状态机的一个状态，输入符号表，所有输入有穷状态机的关于问题的描述都是这个符号表中的符号组成的字符串。状态转换函数，表示有穷状态自动机在某一状态读入字符，将状态变成另外一种状态，有穷状态自动机一定有一个初始状态，接受输入后，从这个初始状态出发，进行一系列的状态转换，然后到达一个终止状态，即问题求解结束。对于每个问题的输入，有穷状态自动机都会进行一系列的状态转换，这个转换的过程，可以用一系列不同的状态来表述，这个过程就是有穷自动机的主体框架，如果某个先前引入的状态发现输入串肯定不是语言的句子，就进入此状态，完成对输入状态的剩余部分的输入，即进行相应的例外处理，状态机的状态具有一定的记忆功能，不同的状态对应不同的情况。由于有穷状态机只有有穷个状态，所以在识别一个输入的过程中，如果有无穷种情况需要记忆，我们肯定是无法构造出相应的有穷状态自动机的，对应输入的每一个变换步骤都有一个状态与之对应，有穷状态机在任意时刻可以处于有穷多个状态，有事状态是有穷的，我们可以认为这种有穷状态自动机的一个状态对应的是先前定义的有穷状态自动机的一个状态集合。实际上我们可以认为这种有穷状态自动机具有智能，在一个状态下，它可以根据当前从输入字符串读入的字符自动的在集合中选择一个进入正确的状态。在这种前提下，只要在有穷状态自动机中存在一条从开始状态出发，最终到达某一个终止状态的路径，那么，就认为它接受了串，否则认为它不接受串。前面定义的有穷状态自动机有一个很大的限制，对一个输入的字符串，它只是输出此串是合法串还是不合法串的结论。这在很多时候是不够的，因为我们有时不仅希望系统能得出一个输入串是否为要求串的结论，我们更希望系统在处理此串的过程中给出必要的处理步骤，因此，从抽象的角度考虑，已经没有必要再设置终止状态集。我们可以由此得出，有穷状态自动机具有有穷的存储功能，而且允许直接根据当前状态变换到新的状态。有穷状态自动机可以作为一种识别模型，分别按照对推导和规约的模拟。

计算机学科研究的是什么样的问题能够被有效的自动化，而实现问题有效自动化的基础首先是实现对问题的恰当的形式化描述。有穷状态自动机就是这样的一种形式化的描述模型。有穷状态自动机擅长语言的识别，使得人们更容易理解和使用它，而适应计算机的表示形式又使得我们能更容易使用计算机系统处理语言。

王茁.基于有限状态自动机的公共交到站时间预测模型［D］.哈尔滨工业大学，2012.