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

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

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

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

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

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

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

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

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