吳成來(lái)

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

關(guān)鍵詞：有限自動(dòng)機(jī);矩陣模型;等價(jià)類(lèi);極小化

中圖分類(lèi)號(hào)：O224? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ? ? ? ?文章編號(hào)：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ā)展， 有限自動(dòng)機(jī)理論已逐步向不同領(lǐng)域滲透， 成為了許多學(xué)科的重要理論和應(yīng)用基礎(chǔ)。文獻(xiàn)[1]提出了有限自動(dòng)機(jī)M-的矩陣模型表示方法，在此基礎(chǔ)上，采用矩陣?yán)碚摵筒紶柎鷶?shù)為工具，可以把矩陣模型用來(lái)處理有限自動(dòng)機(jī)極小化問(wèn)題。

有限自動(dòng)機(jī)極小化問(wèn)題則在程序測(cè)試中有重要意義。下面介紹一些基本概念。

2 基本概念

3 有限自動(dòng)機(jī)的的極小化

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

4 結(jié)束語(yǔ)

把有限自動(dòng)機(jī)極小化可以簡(jiǎn)化自動(dòng)機(jī)的狀態(tài)集合，使得任意兩個(gè)狀態(tài)在同一個(gè)輸入下的輸出都不同，這樣可以應(yīng)用于程序測(cè)試中。基于矩陣模型的極小化方法，能方便的應(yīng)用于算法設(shè)計(jì)和有限自動(dòng)機(jī)的自動(dòng)處理，同時(shí)也是有限自動(dòng)機(jī)研究的一種新的思路，有助于有限自動(dòng)機(jī)應(yīng)用研究的發(fā)展。

參考文獻(xiàn)：

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

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

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

[4]馮文俊，易忠，鄧培民.輸入存儲(chǔ)線(xiàn)性有限自動(dòng)機(jī)的極小化[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2010，40（8）：87-97.