鄭兆岳

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

一類雙向模糊有窮自動(dòng)機(jī)

鄭兆岳1，2

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

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

雙向模糊有窮自動(dòng)機(jī)；即時(shí)描述；正則語言；等價(jià)

1 引言

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

2 雙向有窮自動(dòng)機(jī)

定義2.1 一個(gè)非確定雙向有窮自動(dòng)機(jī)（2NDFA）是一個(gè)五元組 M=（Q，Σ，δ，q0，F(xiàn)），其中 Q 是有限狀態(tài)集， Σ 是有限輸入字母表，δ：Q×（Σ∪{├， ┤}）→ 2Q×{L·S·R}是轉(zhuǎn)移函數(shù)，├， ┤不屬于 Σ，它們分別為最左和最右結(jié)束標(biāo)志符號(hào)。輸入串的存儲(chǔ)形式為├x┤，其中 x∈Σ，?（q，σ）∈Q×（Σ∪{├，┤}），δ（q，σ）={（p1，d1），（p2，d2），…，（pm，dm）}，表示 M 在狀態(tài)q讀入字符σ，可以選擇地將狀態(tài)變成p1，同時(shí)按d1實(shí)現(xiàn)讀頭的移動(dòng)；或著將狀態(tài)變成p2，同時(shí)按d2實(shí)現(xiàn)對(duì)讀頭的移動(dòng)；…，或者將狀態(tài)變成pm，同時(shí)按 dm實(shí)現(xiàn)對(duì)讀頭的移動(dòng)。 d1， d2， …，dm∈{L，S，R}，其中，L表示向左，S表示不動(dòng)，R表示向右移動(dòng)的方向。

一個(gè)確定雙向有窮自動(dòng)機(jī)（2DFA）是對(duì)所有q∈Q，σ∈Σ∪{├， ┤}，有|δ（q，σ）|≤1，詳細(xì)給出定義。

定義2.2一個(gè)2DFA是一個(gè)五元組M=（Q，Σ，δ，q0，F(xiàn) ）其中，Q，Σ，├， ┤和定義 2.1 中一樣，且├，┤不屬于Σ是最左和最右結(jié)束標(biāo)志符號(hào)，δ：Q×（Σ∪{├， ┤}）-→ Q×{L，R，S}。 q0∈Q 是初始狀態(tài)（起始態(tài)），t∈F（F 是接受狀態(tài)集），r∈Q 是拒絕態(tài)，且 r≠t。

對(duì)所有的狀態(tài) q∈Q 規(guī)定 δ（q，┤）=（u，R），δ（q，┤）=（v，L），其中 u，v∈Q，目的是保證讀頭不跑出串的所在區(qū)域。對(duì)所有的符號(hào)b∈Σ∪{┤}，有δ（t，b）=（t，R），δ（r，b）=（r，R），δ（t，┤）=（t，L），δ（r，┤）=（r，L）。保證機(jī)器一旦進(jìn)入了接受狀態(tài)，它將停留在此狀態(tài)中而讀頭指向任一方向。

例 1.設(shè) M=（Q，Σ，δ，q0，F(xiàn)） 為一 2DFA， 其中Q=（q0，q1，q2，p0，p1，t，r），t為接受狀態(tài)，r 為拒絕狀態(tài)，Σ=（0，1），其轉(zhuǎn)移表為

我們可以驗(yàn)證該2DFA，M可識(shí)別如下的串{x|x∈{0，1}*且在串x中，0的個(gè)數(shù)是3的倍數(shù)，1的個(gè)數(shù)是偶數(shù)}。

為了描述雙向有窮自動(dòng)機(jī)識(shí)別一個(gè)串的過程，我們來定義它的即時(shí)描述（ID）。

引入即時(shí)描述（ID）的概念，以代替δ這個(gè)概念描述輸入符串當(dāng)前狀態(tài)和讀頭現(xiàn)時(shí)的位置。若輸入字符串 x∈Σ*，x=a1a2…an，a0=├，an+1=┤，a0a1…an+1=├x┤，在某時(shí)刻，M處在狀態(tài)q讀頭注視第i個(gè)字符，則稱 2DFA 此時(shí)的即時(shí)描述 ID 為（q，i），機(jī)器的初始ID為（q0，0），即機(jī)器在初始狀態(tài)q0正在注視最左的結(jié)束標(biāo)志符├。

例2.用ID來描述例1中該2DFA M接受串的ID描述序列：

不接受串001010的ID描述序列：

我們來定義2DFA接受的語言。

定義2.3設(shè)M為一個(gè)雙向有窮自動(dòng)機(jī)，則它接受的語言

定義2.4兩個(gè)雙向有窮自動(dòng)機(jī)是等價(jià)的，如果它們接受的語言相同，即 L（M1）=L（M2）。

定理2.1[7]雙向有窮自動(dòng)機(jī)接受的語言是正則語言。

定理2.2[7]任意一個(gè)2DFA，存在一個(gè)DFA與之等價(jià)。

定理2.3[7]2NFA與FA等價(jià)。

定理 2.4[7]任給一個(gè) 2NFAM=（Q，Σ，δ，q0，F(xiàn)），存在一個(gè)與之等價(jià)的 2NFA M'=（Q，Σ，δ'，q0，F(xiàn)），使得對(duì)每個(gè)可接受的輸入串，至少存在一條能到達(dá)某終結(jié)狀態(tài)q（∈F）且此時(shí)它的讀頭正注視著最左結(jié)束標(biāo)志符├的可計(jì)算路徑。

3 雙向模糊有窮自動(dòng)機(jī)

定義3.1 一個(gè)2NFFA是一個(gè)五元組A=（Q，Σ，δ，q0，F(xiàn)），其中，Q，Σ，q0與定義 2.1 的一樣，δ 是Q×（Σ∪{├，┤}）×Q×{L，R}的一個(gè)模糊子集，即，δ:Q×（Σ∪{├， ┤}）×Q×{L，R}→[0，1]，F(xiàn) 是 Q 的一個(gè)模糊子集，它是模糊接受狀態(tài)。

直觀地，δ（q，x，q'，d）是表示當(dāng)前狀態(tài)為 q，讀頭正注視x，下一個(gè)狀態(tài)到達(dá)狀態(tài)q'，且讀頭將按方向d移動(dòng)的可能度 （d=L表示向左移動(dòng)一格，d=R表示向右移動(dòng)一格）。

定義3.2對(duì)某個(gè)2NFFA，如果模糊轉(zhuǎn)移函數(shù)δ是Q×Σ→Q×{L，R}的一個(gè)部分函數(shù)，且F是Q的模糊子集，則我們稱M為2DFFA。

我們用?M來定義從ID D1到ID D2，其中，├，┤不屬于Σ，w∈Σ，它是D×D上的一個(gè)模糊的二元關(guān)系 D=Σ*QΣ*。

則M′是只有一個(gè)分明終結(jié)狀態(tài)的2NFFA，易驗(yàn)證它們接受的語言是相等的，從而二者是等價(jià)的。

定理 3.2 fM1和 fM2分別為 M1=（Q1，Σ，δ1，q01，F(xiàn)1）和 M2=（Q2，Σ，δ2，q02，F(xiàn)2） 接受的語言， 則存在一個(gè)2NFFA接受它們語言的并 fM1∨fM2。

推論3.1設(shè)f為雙向模糊自動(dòng)機(jī)接受的語言，則 f的象集 Im（f）={f（w）|w∈Σ*}為有限集。

設(shè)X是一個(gè)經(jīng)典集合，f為X的模糊子集，即，f：X→[0，1]。

定義 3.5 R（f）={f（x）:x∈X，f（x）＞0}，?λ∈[0，1]，

X上的兩個(gè)子集 fλ，f[λ]定義為 fλ={x:x∈X，f （x）≥λ}，f[λ]={x:x∈X，f（x）=λ}。

由以上規(guī)定的定義，我們有以下的定理：

定理 3.3設(shè) f:Σ*→[0，1]為模糊語言，則下面的稱述是等價(jià)的：

（1）f能被某非確定性的雙向模糊有窮自動(dòng)機(jī)識(shí)別。

（2）R（f）是有限的，且 fλ是能被某雙向有窮自動(dòng)機(jī) Mλ識(shí)別的正則語言，λ∈R（f）。

3）R（f）是有限的，且 f[λ]是能被某雙向有窮自動(dòng)機(jī) M[λ]識(shí)別的正則語言，λ∈R（f）。

（4）f能被某確定性的雙向模糊有窮自動(dòng)機(jī)識(shí)別。

證明 （1）?（2）設(shè) f=fM，其中，M=（Q，Σ，δ，q0，F(xiàn)）是一個(gè)非確定性的雙向模糊有窮自動(dòng)機(jī)。?w∈Σ*，有 fM（w）=∨{?*（q0，w，wq）∧F（p）:q∈Q，w∈Σ*}，由?*（q0，w，wq）的定義以及[0，1]是一個(gè)線性序集，知 R（f）?{0，1}∪R（δ）∪R（F）是有限的，即 R（f）是有限的。而且，?λ∈R（f），w∈Σ*，w∈fλ?f（w）≥λ??p∈Q，?*（q0，w，wq）∧F（p）≥λ??p∈Q，?*（q0，w，wq）≥λ 且 F（p）≥λ?w∈L（Mλ），其中 Mλ=（Q，Σ，δλ，q0，F(xiàn)λ），因此，fλ能被 Mλ識(shí)別。

（2）?（4）?λ∈R（f），因?yàn)?fλ也能被確定性的雙向有窮自動(dòng)機(jī) M=（Q，Σ，δ，q0，F(xiàn)）所識(shí)別，則 λ∧fλ肯定能被某一個(gè) 2DFFA M'=（Q，Σ，δ，q0，λ∧F）所識(shí)別，其中，λ∧fλ是上 Σ*的一模糊子集，即，λ∧fλ:

由于R（f）是有限的，及模糊正則語言類關(guān)于模糊并是封閉的。知 f=∨λ∈R（f）（λ∧fλ）為模糊正則語言，它能被某確定性的雙向有窮自動(dòng)機(jī)識(shí)別。

（3）?（4）和（2）?（4）類似，由此 f=∨λ∈R（f）（λ∧f[λ]）。

（4）?（1）是顯然的，理由：確定性的雙向模糊有窮自動(dòng)機(jī)是非確定性的雙向模糊有窮自動(dòng)機(jī)的特殊情況。

（4）?（3）設(shè) f=fM，M=（Q，Σ，δ，q0，F(xiàn)）是一個(gè)確定性的雙向模糊有窮自動(dòng)機(jī)，其中F:Q→[0，1]，M接受的語言 fM（w）=V{F（p）:q0w?*wp，p∈Q，w∈Σ*}，由于 R（f）?R（F）∪{1}是有限的，?λ∈R（f），w∈f[λ]?f（w）=λ??p∈Q，q0w?*wq 且 F（p）=λ?w∈L（M[λ]），其中 M[λ]=（Q，Σ，δ，q0，F(xiàn)[λ]），f[λ]也能被某雙向有窮自動(dòng)機(jī)識(shí)別。

4 結(jié)束語

本文先從經(jīng)典的角度，介紹了雙向有窮自動(dòng)機(jī)與單向有窮自動(dòng)機(jī)所接受的語言是正則語言且等價(jià)，給出了由δ來定義的即時(shí)描述（ID），它和圖靈機(jī)的即時(shí)描述（ID）文獻(xiàn)[1]類似。也得到了結(jié)論：任給定一個(gè)非確定雙向有窮自動(dòng)機(jī)，存在一個(gè)至少有一條能到達(dá)終結(jié)狀態(tài)的可計(jì)算路徑的2NFA與之等價(jià)。最后，我們把討論轉(zhuǎn)到模糊上去，也同樣用δ定義了雙向模糊有窮自動(dòng)機(jī)的即時(shí)描述（ID）及其接受的語言。定理3.3詳細(xì)地給出語言象集R（f）是有限的，及2NFFA與2DFFA的等價(jià)性。

[1]Wee W G.On generalizations of adaptive algrithm and application of the fuzzy concept to pattern classification，Ph.D.Thesis，Purdue University， 1967：69-85

[2]John E.HopcroftRajeev MotwaniJeffrey D.Ullman，Introduction to Automata Theory Languages，and Computation [M].ISBN 7-111-14452-X.53-89

[3]Andris Ambuinis，John Watrous.Two-way finite automata with quantun and classical states[J].TheoreticalComputerScience，2002，287：299-311

[4]Viliam Geffert，Carlo Mereghetti，and Giovanni Pighizzini.Complementing Two -Way Finite Automata，DLT（2005），LNS3572：260-271

[5]Viliam Geffert，Carlo Mereghetti，andGiovanni Pighizzini.Converting two-way nondeterministic unary automata into simplerautomata[J].Theoretical computer Science，2003，295：189-203

[6]李永明.模糊系統(tǒng)分析[M].北京：科學(xué)出版社，2005：175-204

[7]蔣宗禮，姜守旭.形式語言與自動(dòng)機(jī)理論[M].北京：清華大學(xué)出版社，2003：122-125

A kind of two-way fuzzy finite automata

ZHENG Zhao-yue

In this paper，The ID and the accepted language by two-way finite automata and two-way fuzzy finite automata are introducted.We show that its accepted language is regular and the equivalent formulations of two-way nondeteministic finite automata and two-way deteministic finite automata，two-way nondeteministic fuzzy finite automata and two-way deteministicfuzzy finite automata.

two-way fuzzy finite automata;ID（instantaneous description）;regular language;equivalent

O153.1

A

1009-9530（2012）03-0008-04

2011-02-20

鄭兆岳（1967-），男，安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院碩士研究生，安徽工貿(mào)職業(yè)技術(shù)學(xué)院講師，主要研究方向：模糊集及泛函微分方程。