您好, 访客   登录/注册

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

来源:用户上传      作者:

  摘  要:文章主要讨论了矩阵模型方法在有限自动机极小化方面的应用。希望通过文章的研究,可以为相关人士提供一定的参考和借鉴。
  关键词:有限自动机;矩阵模型;等价类;极小化
  中图分类号: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