一類雙向模糊有窮自動機

鄭兆岳

（1.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230039；2.安徽工貿(mào)職業(yè)技術(shù)學(xué)院，安徽 淮南 232007）

一類雙向模糊有窮自動機

鄭兆岳1，2

（1.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230039；2.安徽工貿(mào)職業(yè)技術(shù)學(xué)院，安徽 淮南 232007）

給出經(jīng)典雙向有窮自動機的即時描述，接受（識別）的語言及雙向有窮自動機和有窮自動機是等價的，證明它接受的語言是正則語言。由此，把它推廣到模糊上去，相應(yīng)地給出了雙向模糊有窮自動機的定義，即時描述及其接受的語言，進一步證明非確定性雙向模糊有窮自動機與確定雙向模糊有窮自動機接受的語言是等價的。

雙向模糊有窮自動機；即時描述；正則語言；等價

1 引言

有窮自動機（FA）是許多重要類型的硬件和軟件的有用模型，作為計算理論，它是最簡單的數(shù)學(xué)模型，它的應(yīng)用已涉及到數(shù)字電路的設(shè)計，性能檢測軟件，通信協(xié)議和安全交換信息的協(xié)議的驗證，神經(jīng)網(wǎng)絡(luò)等許多方面。自從Zadeh L A 1965年提出Fuzzy集合理論后，1969年，Wee W G利用模糊的方法研究了自動機理論[1]。模糊自動機（FFA）為計算理論提供了一種研究和處理包含模糊性自然語言的有利工具。在文獻[2]中主要介紹經(jīng)典的有窮自動機，而雙向的有窮自動機（2FA）在文獻[2]，[3]，[4]，[5]中相應(yīng)地給出過其定義，文獻[4]介紹了2FA接受的補語言，文獻[5]介紹了非確定性雙向一元自動機向單向自動機的變換，文獻[6]更詳細地介紹了模糊自動機定義及代數(shù)性質(zhì)。本文從確定性雙向有窮自動機 （2DFA）接受的語言是正則語言，給出接受的模糊語言的定義，由經(jīng)典雙向有窮自動機與單向有窮自動機的等價性，從模糊化的程度上討論了非確定雙向模糊有窮自動機（2NFFA）和確定雙向模糊有窮自動機（2DFFA）接受的語言也是等價的。……