幾類格值自動機的最小化算法研究.pdf

1、格值自動機作為經(jīng)典數(shù)學模型有限狀態(tài)自動機的拓展，是將模糊數(shù)學、格半群和和自動機理論相結合，通過改變狀態(tài)轉移函數(shù)和輸入輸出函數(shù)來實現(xiàn)的。其類型的豐富性和模型的復雜性決定了其應用的廣泛性。狀態(tài)的最小化自從有限自動機被引入以來就一直是值得關注的課題，格值自動機的狀態(tài)最小化需要根據(jù)具體的模型進行相應的算法研究。對模型的最小化實現(xiàn)，能使格值自動機在應用上更加靈活方便。前人在這個問題上已經(jīng)提出了Mealy型和Mizumoto型格值有限自動機，格值字

2、符串自動機以及非確定型格值有限自動機等的最小化算法或理論，然而還有更多模型和算法需要我們去研究。本文主要工作有如下三個方面：
　　 ⑴格值Moore機的最小化：首先提出格值Moore機的概念，然后從代數(shù)角度出發(fā)詳細研究此類自動機的性質，同時研究此類自動機的同余和同態(tài)，揭示此類自動機的代數(shù)性質和取值格半群的緊密聯(lián)系。最后研究格值Moore機的極小化，給出可在有限步實現(xiàn)極小化的算法，并從理論上證明了得到的最小化格值Moore機與原格

3、值Moore機等價。
　　 ⑵確定型格值有限自動機的最小化：首先給出了確定型格值有限自動機的定義，并同時給出了有效終止狀態(tài)和可達到狀態(tài)的定義。然后以可到達狀態(tài)為基礎引入了一種新的等價關系，通過等價關系對等價類的劃分，給出了僅利用集合運算便能計算相應等價類的算法。最后給出了確定型格值有限自動機最小化算法的一個容易實現(xiàn)的構造型描述和相應示例。
　　 ⑶等輸入輸出長度格值自動機的最小化：首先提出等輸入輸出長度格值自動機的定義，