格值自動機的代數(shù)性質(zhì)與極小化算法.pdf

1、取值于格半群的自動機比其它形式的模糊自動機能接受更為廣泛的形式語言與模糊語言，將基于詞的計算模型建立在更廣泛的理論之上。因此，對取值于格半群的自動機代數(shù)性質(zhì)的研究和極小化問題的研究是格值自動機理論的兩個重要課題。 既然格值自動機具有如此強大的計算能力，有必要對其從代數(shù)角度出發(fā)較詳細(xì)地，較深入地研究此類自動機的變換半群，乘積和覆蓋關(guān)系，揭示此類自動機的代數(shù)性質(zhì)和格半群間的緊密聯(lián)系。對于一個給定的自動機，它的狀態(tài)中有一些根本沒有被訪

2、問過，有一些盡管被訪問過，但是本身是不可達(dá)的，有一些狀態(tài)盡管是可達(dá)的，但是在功能上卻與另一些狀態(tài)等價，這樣的自動機在設(shè)計和應(yīng)用中顯然很累贅，可以將一些無用的狀態(tài)刪掉，將另外一些等價狀態(tài)進行整合和約簡，使之狀態(tài)數(shù)達(dá)到極小。如果一個格值自動機本身可極小化，能否找到一個可在有限步實現(xiàn)的行之有效的算法? 本文主要是在文獻(xiàn)[3，5，8，13—14，29—30，39]基礎(chǔ)上研究格值自動機的代數(shù)性質(zhì)及極小化算法。 首先，提出了格值自動

3、機和變換半群的定義，研究了其具有的代數(shù)性質(zhì)，并給出了任意格值自動機可轉(zhuǎn)化為格值變換半群的充分必要條件。然后，給出了格值自動機和變換半群的覆蓋以及格值同態(tài)的定義，揭示了其具有的代數(shù)性質(zhì)。若格半群中的乘法是格值變換半群可誘導(dǎo)的，在格值強同態(tài)下證明了格值可誘導(dǎo)變。換半群和一般有效變換半群是等價的。最終，給出四類構(gòu)造格值自動機乘積和兩類構(gòu)造變換半群乘積的方法，研究了其具有的代數(shù)性質(zhì)，并研究了幾類格值自動機和變換半群乘積之間具有的覆蓋關(guān)系。

4、 其次，在更一般的框架一格半群意義下，提出具有輸入和輸出字符的自動機——格值Mealy自動機的概念，從代數(shù)角度出發(fā)較詳細(xì)地研究了此類自動機具有的性質(zhì)，同時研究了此類自動機的同余和同態(tài)，揭示了此類自動機的代數(shù)性質(zhì)和格半群的緊密聯(lián)系，最終研究了格值Mealy自動機的極小化問題，并給出了在有限步可實現(xiàn)此極小化的算法。 最后，作為應(yīng)用主要研究了第二類格值自動機，并在正則同余關(guān)系下給出了可在有限步實現(xiàn)具有模糊初始狀態(tài)和模糊終狀態(tài)的自動機