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

吴成来

摘  要：文章主要讨论了矩阵模型方法在有限自动机极小化方面的应用。希望通过文章的研究，可以为相关人士提供一定的参考和借鉴。

关键词：有限自动机;矩阵模型;等价类;极小化

中图分类号：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-的矩阵模型表示方法，在此基础上，采用矩阵理论和布尔代数为工具，可以把矩阵模型用来处理有限自动机极小化问题。

有限自动机极小化问题则在程序测试中有重要意义。下面介绍一些基本概念。

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.