矩阵模型在有限自动机上的应用

摘要

自动机理论是研究离散数字系统的功能、结构及两者关系的数学理论，随着数字计算机、数字通信及自动化等新技术的出现和发展，自动机理论已成为许多学科的重要理论和应用基础。。本文在文献[4]，[5]，[6]的基础上，继续采用矩阵理论和布尔代数为工具，对有限自动机的另外一些性质做了进一步的讨论，所得的结果不仅有利于有限自动机的理论在计算机中的应用,也表明了矩阵模型方法在有限自动机应用研究中有着重要的作用。主要结论有: 1.在有限自动机的矩阵模型方法表示的基础上, 对有限自动机的弱可逆性进行讨论，然后给出了判断有限自动机和线性有限自动机是否具有弱可逆性的算法. 2.在运用矩阵模型方法研究试验序列的基础上，构造出了求一个极小线性有限自动机的最短初态试验序列的算法，一个输入序列是（线性）有限自动机的同步序列的充要条件，并且构造出了判断一个线性有限自动机是否有同步序列的算法. 3.利用矩阵模型方法对两个有限自动机的限制直积进行讨论，在此基础上构造了限制直积的状态映射矩阵和输出映射矩阵，并进行了研究，得出了它们的一些性质: 关于状态转移函数运算的两个结果和输出函数的两个结果. 4.利用矩阵模型对两个有限自动机的级联积进行了讨论，在此基础上构造了级联积的状态映射矩阵和输出映射矩阵，并进行了研究，得出了它们的一些性质: 级联积的映射矩阵的一些性质, 级联积的状态转移函数运算的两个结果, 级联积的输出函数的一些性质及其运算的两个结果。 全文共分为五章: 第一章介绍了自动机理论的背景以及用矩阵模型方法研究自动机的现状,同时给出了有限自动机以及矩阵模型的一些基本概念和记号。 第二章应用矩阵模型方法在有限自动机弱可逆上,所得的结果可以判断有限自动机和线性有限自动机是否具有弱可逆性,若具有弱可逆性,延迟几步弱可逆。 第三章应用矩阵模型方法在试验序列上, 所得的结果可以求一个极小线性有限自动机的最短初态试验序列，并且判断一个输入序列是否是（线性）有限自动机的同步序列，若一个线性有限自动机有同步序列,利用所得的结果可以求出最短同步序列。 第四章应用矩阵模型方法在限制直积上, 构造出了限制直积的状态映射矩阵和输出映射矩阵, 并对它们的一些性质进行了研究, 给出所获得结果。。 第五章应用矩阵模型方法在有限自动机的级联积上,构造出了级联积的状态映射矩阵和输出映射矩阵，并对它们进行了研究, 给出所获得结果。