矩陣模型方法在有限自動機極小化的應(yīng)用

吳成來

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

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

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

隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展， 有限自動機理論已逐步向不同領(lǐng)域滲透， 成為了許多學(xué)科的重要理論和應(yīng)用基礎(chǔ)。文獻[1]提出了有限自動機M-的矩陣模型表示方法，在此基礎(chǔ)上，采用矩陣理論和布爾代數(shù)為工具，可以把矩陣模型用來處理有限自動機極小化問題。

有限自動機極小化問題則在程序測試中有重要意義。下面介紹一些基本概念。

2 基本概念

3 有限自動機的的極小化

由定義2可知，極小自動機的任意兩個不同的狀態(tài)都不等價，因此可以利用狀態(tài)間等價關(guān)系，通過對有限自動機的狀態(tài)集合進行劃分的方法，得到它的極小自動機。

4 結(jié)束語

把有限自動機極小化可以簡化自動機的狀態(tài)集合，使得任意兩個狀態(tài)在同一個輸入下的輸出都不同，這樣可以應(yīng)用于程序測試中?；诰仃嚹Ｐ偷臉O小化方法，能方便的應(yīng)用于算法設(shè)計和有限自動機的自動處理，同時也是有限自動機研究的一種新的思路，有助于有限自動機應(yīng)用研究的發(fā)展。

參考文獻：

[1]朱征宇，朱慶生.有限自動機研究的矩陣模型方法[J].計算機科學(xué)，2001（4）：46-48.

[2]陶仁驥.有限自動機的可逆性[M].北京：科學(xué)出版社，1979.

[3]朱征宇，王術(shù)，趙銀春.基于矩陣模型表示的有限自動機極小化方法[J].計算機工程與應(yīng)用，2004，39（35）：47-49.

[4]馮文俊，易忠，鄧培民.輸入存儲線性有限自動機的極小化[J].數(shù)學(xué)的實踐與認識，2010，40（8）：87-97.