矩阵模型方法在有限自动机极小化的应用

来源:用户上传      作者:

　　摘  要：文章主要讨论了矩阵模型方法在有限自动机极小化方面的应用。希望通过文章的研究，可以为相关人士提供一定的参考和借鉴。
　　关键词：有限自动机;矩阵模型;等价类;极小化
　　中图分类号：O224          文献标志码：A           文章编号：2095-2945（2019）08-0162-03
　　Abstract： This paper mainly discusses the application of matrix model method in the minimization of finite automata. It is hoped that through the study of the article， it can provide a certain reference for the relevant people.
　　Keywords： finite automata; matrix model; equivalence class; minimization
　　1 概述
　　随着现代科学技术的发展， 有限自动机理论已逐步向不同领域渗透， 成为了许多学科的重要理论和应用基础。文献[1]提出了有限自动机M-<I，O，S，？啄，？姿>的矩阵模型表示方法，在此基础上，采用矩阵理论和布尔代数为工具，可以把矩阵模型用来处理有限自动机极小化问题。
　　有限自动机极小化问题则在程序测试中有重要意义。下面介绍一些基本概念。
　　2 基本概念
　　3 有限自动机的的极小化
　　 由定义2可知，极小自动机的任意两个不同的状态都不等价，因此可以利用状态间等价关系，通过对有限自动机的状态集合进行划分的方法，得到它的极小自动机。
　　4 结束语
　　把有限自动机极小化可以简化自动机的状态集合，使得任意两个状态在同一个输入下的输出都不同，这样可以应用于程序测试中。基于矩阵模型的极小化方法，能方便的应用于算法设计和有限自动机的自动处理，同时也是有限自动机研究的一種新的思路，有助于有限自动机应用研究的发展。
　　参考文献：
　　[1]朱征宇，朱庆生.有限自动机研究的矩阵模型方法[J].计算机科学，2001（4）：46-48.
　　[2]陶仁骥.有限自动机的可逆性[M].北京：科学出版社，1979.
　　[3]朱征宇，王术，赵银春.基于矩阵模型表示的有限自动机极小化方法[J].计算机工程与应用，2004，39（35）：47-49.
　　[4]冯文俊，易忠，邓培民.输入存储线性有限自动机的极小化[J].数学的实践与认识，2010，40（8）：87-97.
转载注明来源:https://www.xzbu.com/1/view-14868758.htm