矩陣模型方法在有限自動機極小化的應用

吳成來

摘? 要：文章主要討論了矩陣模型方法在有限自動機極小化方面的應用。希望通過文章的研究，可以為相關人士提供一定的參考和借鑒。

關鍵詞：有限自動機;矩陣模型;等價類;極小化

中圖分類號：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.