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

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

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

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

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