有限状态自动机模型

《有限状态自动机模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、些普遍规律，描述计算的基本概念与模型，其重点是描述现象、解释规律。另一方面是包括计算机硬件、软件的计算机系统设计和实现的工程技术，简单地说，计算机科学与技术学科通过在计算机上建立模型并模拟物理过程来进行科学调查和研究，它系统地研究信息描述和变换算法，主要包括信息描述和变换算法的理论、分析、效率、实现和应用。　　4有限状态自动机模型　　当我们用计算机进行问题的求解时，首先需要用适当的数据进行问题表示，然后再设计相应的算法对这些数据进行变换处理来获得问题的求解结果。因此，对问题进行建模和形式化表示，然后进行处理是进行计算机求解的基本途径。数理

3、逻辑、自动机理论给出了如何描述一些基本问题以及如何建立问题的抽象表示，并通过对这些抽象化的表示的性质和它的变化方法进行研究。这些模型都是问题数学模型的典范，给计算机问题求解提供了坚实的理论基础，是计算机求解问题的重要方法和思想。　　计算机科学与技术学科是以数学和电子学科为基础发展起来的，一方面研究计算机领域中的一些普遍规律，描述计算的基本概念与模型，其重点是描述现象、解释规律。另一方面是包括计算机硬件、软件的计算机系统设计和实现的工程技术，简单地说，计算机科学与技术学科通过在计算机上建立模型并模拟物理过程来进行科学调查和研究，它系统地研究

4、信息描述和变换算法，主要包括信息描述和变换算法的理论、分析、效率、实现和应用。　　4所有问题的描述都要以计算机能识别的语言来实现，计算机语言的文法描述提供了生成语言的手段，但是，对于语言句子的识别来说，我们需要一些识别语言的模型，我们可以称这种模型为语言的识别模型。这种识别模型应该满足必要的约束条件，首先模型具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，模型可以在不同的状态下完成特定语言的识别。我们可以将输入数据中出现的符号组成一个字符的列表。模型将输入数据作为线性表来进行处理和变换。模型有一个初始的状态，它是系统的开始状态，

5、系统在这个状态下开始进行问题的求解。模型中还有一些状态表示它到目前为止所读入的字符构成的字符串是模型从开始状态引导到这种状态的所有字符串构成的语言就是模型所能识别的输入。我们可以将此模型对应成有穷状态自动机的物理模型，在处理问题的时候，它可以接受一个关于问题的输入数据，数据以字符串的形式提供，我们把这些输入数据划分成一系列的小部分，每个部分由若干字符组成，为了不让输入数据量影响该模型对问题的处理，我们约定，输入数据从开始输入时的时间点开始处理，输入状态可以是无穷的，这就是说，从输入第一部分数据开始，输入端可以有任意长度的输入序列。而且，模

6、型有一个有穷状态控制器，该控制器的状态只有有穷多个，并且规定，模型的每一个动作分为三步，读入待输入的字符，根据当前的状态和读入的字符改变有穷控制器的状态，读下一部分输入数据。计算机的各个组成部分，既包括硬件系统也包括软件系统，都可以对其进行形式化的定义，计算机的硬件系统包括中央处理器、存储器、外部设备，可以形式化地用一个三元组来描述，对计算机个各个硬件部分进行管理的软件的功能也可以用形式化的方法来描述，例如，操作系统的各个功能模块、处理器管理、线程调度、文件系统、设备驱动程序、网络通信管理、虚拟内存管理等都可以进行形式化的定义。有穷状态机

7、就是进行这种形式化定义的模型，有穷状态机是一个五元组，分别是描述状态的有穷非空集合，它称为有穷状态机的一个状态，输入符号表，所有输入有4穷状态机的关于问题的描述都是这个符号表中的符号组成的字符串。状态转换函数，表示有穷状态自动机在某一状态读入字符，将状态变成另外一种状态，有穷状态自动机一定有一个初始状态，接受输入后，从这个初始状态出发，进行一系列的状态转换，然后到达一个终止状态，即问题求解结束。对于每个问题的输入，有穷状态自动机都会进行一系列的状态转换，这个转换的过程，可以用一系列不同的状态来表述，这个过程就是有穷自动机的主体框架，如果某

8、个先前引入的状态发现输入串肯定不是语言的句子，就进入此状态，完成对输入状态的剩余部分的输入，即进行相应的例外处理，状态机的状态具有一定的记忆功能，不同的状态对应不同的情况。由于有穷状态机只有有