模糊自動(dòng)機(jī)及其語言的代數(shù)性質(zhì)與應(yīng)用研究.pdf

1、自動(dòng)機(jī)與形式語言理論對于計(jì)算機(jī)系統(tǒng)及其語言、軟件的發(fā)展具有重要的影響，它還廣泛的用于生命科學(xué)，生物化學(xué)，心理學(xué)，語言學(xué)等學(xué)科。由于現(xiàn)實(shí)的復(fù)雜系統(tǒng)往往含有不確定性，研究不確定環(huán)境下的計(jì)算理論成為20世紀(jì)60年代以來的熱點(diǎn)課題，對形式語言的刻畫與分類一直是其中的一個(gè)重要的研究方向。為了縮短形式語言與自然語言之間的差距，模糊自動(dòng)機(jī)的理論與應(yīng)用研究迅速展開。李永明教授分別于2005年和2011年提出的基于格半群和格值的模糊自動(dòng)機(jī)理論成為目前模糊

2、自動(dòng)機(jī)研究的主要方向。本文在此基礎(chǔ)上先從代數(shù)角度研究基于序半群的模糊自動(dòng)機(jī)及其代數(shù)性質(zhì)，進(jìn)一步，對于一般的格結(jié)構(gòu)，從寬度優(yōu)先和深度優(yōu)先兩種語義角度出發(fā)，研究了基于格的模糊正則文法理論。另外，在直覺模糊集及偽半環(huán)背景框架下進(jìn)一步對下推自動(dòng)機(jī)和上下文無關(guān)語言進(jìn)行詳細(xì)研究，為自然語言建立了適應(yīng)的計(jì)算理論數(shù)學(xué)模型。本文的主要工作具體有以下幾個(gè)方面:
　　 (1)基于序半群的自動(dòng)機(jī)的代數(shù)性質(zhì)。
　　 提出取值于序半群的模糊自動(dòng)機(jī)，

3、證明(強(qiáng))后繼算子和前驅(qū)算子，模糊后繼和模糊前驅(qū)算子在某些條件下為閉包算子。引進(jìn)弱主子機(jī)器，給出格半群上的自動(dòng)機(jī)的一種唯一分解方法。以quantale為真值結(jié)構(gòu)，證明這種模糊自動(dòng)機(jī)的模糊子機(jī)器與模糊子系統(tǒng)一致。最后詳細(xì)探討了序半群上的自動(dòng)機(jī)的某些算子的性質(zhì)與真值結(jié)構(gòu)的代數(shù)性質(zhì)的內(nèi)在聯(lián)系。特別地，模糊后繼和前驅(qū)算子的保并性質(zhì)可分別由序半群的右和左分配律刻畫，且當(dāng)真值結(jié)構(gòu)為格半群時(shí)，后繼算子的冪等性可由格半群的無零因子性等價(jià)刻畫。
　

4、　 (2)基于格的模糊文法理論。
　　 基于寬度優(yōu)先和深度優(yōu)先語義方式，建立取值于格的模糊文法理論，這將為模糊自動(dòng)機(jī)的分析提供一種必要的工具。研究取值于格的有窮自動(dòng)機(jī)(簡記為l-VFAs)、格值正則文法(1-RGs)及格值確定型正則文法(1-DRGs)之間的關(guān)系。結(jié)果發(fā)現(xiàn)，基于每一種語義方式，1-VFAs與1-RGs在接受相同的模糊語言類的定義下是等價(jià)的。進(jìn)一步，證明格值確定型自動(dòng)機(jī)、1-VFAs、1-RGs及1-DRGs在深

5、度優(yōu)先語義方式下是相互等價(jià)的。對任意1-RG，以寬度優(yōu)先方式識別的語言與以深度優(yōu)先方式識別的語言一致當(dāng)且僅當(dāng)真值論域l是分配格。
　　 (3)直覺模糊上下文無關(guān)語言。
　　 以直覺模糊集為真值結(jié)構(gòu)，我們提出直覺模糊上下文無關(guān)文法(IFCFGs)及具有終狀態(tài)的直覺模糊下推自動(dòng)機(jī)(IFPDAs)。然后研究直覺模糊可識別語言的代數(shù)刻畫包括分解形式和表現(xiàn)定理。通過引進(jìn)一般化的子集構(gòu)造方法，我們證明IFPDAs與它的簡單形式即直覺

6、模糊簡單型下推自動(dòng)機(jī)(IFSPDAs)等價(jià)，并且證明所有的直覺模糊可識別步驟函數(shù)類與所有由IFPDAs接受的語言類是一致的。進(jìn)一步，得到以終狀態(tài)方式接受語言的直覺模糊下推自動(dòng)機(jī)和以空棧方式接受語言的直覺模糊下推自動(dòng)機(jī)是等價(jià)的。另外，我們基于直覺模糊集提出喬姆斯基范式文法(IFCNF)和Greibach范式文法(IFGNF)。研究結(jié)果表明，由IFCFGs生成的直覺模糊上下文無關(guān)語言集分別與由IFCNFs生成的語言集和由IFGNFs生成的語

7、言集相等，而且他們都等同于直覺模糊可識別步驟函數(shù)集。接下來我們研究了直覺模糊上下文無關(guān)語言的代數(shù)運(yùn)算性質(zhì)。最后，給出判定直覺模糊上下文無關(guān)語言的Pump引理及其實(shí)例分析。
　　 (4)偽半環(huán)上的加權(quán)下推自動(dòng)機(jī)與上下文無關(guān)文法。
　　 基于轉(zhuǎn)移語義和寬度優(yōu)先代數(shù)語義，我們研究取值于偽半環(huán)的加權(quán)下推自動(dòng)機(jī)和加權(quán)上下文無關(guān)文法(WCFG)。證明偽半環(huán)上的加權(quán)下推自動(dòng)機(jī)比加權(quán)有窮自動(dòng)機(jī)的計(jì)算能力更強(qiáng)。在轉(zhuǎn)移語義方式下，以終狀態(tài)方

8、式接受形式冪級數(shù)的加權(quán)下推自動(dòng)機(jī)(WPDAs)與以空棧方式接受形式冪級數(shù)的加權(quán)下推自動(dòng)機(jī)(WPDAsθ)等價(jià)。對任意加權(quán)下推自動(dòng)機(jī)，研究以轉(zhuǎn)移語義和寬度優(yōu)先代數(shù)語義識別的形式冪級數(shù)相同時(shí)的等價(jià)刻畫。對任意WPDA，識別的形式冪級數(shù)的象集是有限的當(dāng)且僅當(dāng)偽半環(huán)是雙局部有限生成的。進(jìn)一步，證明若偽半環(huán)滿足乘法局部有限生成的條件，則對任意WPDA，且基于轉(zhuǎn)移語義方式，存在一個(gè)分明簡單型加權(quán)下推自動(dòng)機(jī)與之等價(jià)。最后給出證明，基于以上兩種語義方式