柏明強(qiáng),莫智文

(四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院,四川成都 610068)

模糊自動(dòng)機(jī)的強(qiáng)連通性及群自動(dòng)機(jī)

柏明強(qiáng),莫智文

(四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院,四川成都 610068)

為了更好地研究模糊自動(dòng)機(jī)的結(jié)構(gòu)和性質(zhì),采用代數(shù)的方法,在傳統(tǒng)的模糊有限狀態(tài)自動(dòng)機(jī)的基礎(chǔ)上,通過定義狀態(tài)集合為代數(shù)群的自動(dòng)機(jī),討論了這一類自動(dòng)機(jī)的連通性和正則性,這豐富了模糊自動(dòng)機(jī)理論.

模糊自動(dòng)機(jī);群;強(qiáng)連通

1 前言

自動(dòng)機(jī)理論是經(jīng)典語言理論的一個(gè)重要內(nèi)容,雖然其理論較為完善,但是研究成果仍然不斷涌現(xiàn)[12].自1965年Zadeh[3]提出了模糊集合的概念后,Wee[4]迅速將模糊集應(yīng)用于自動(dòng)機(jī)理論的研究,提出了模糊自動(dòng)機(jī).到現(xiàn)在為止,模糊自動(dòng)機(jī)與模糊語言的研究成果也是十分豐富[59].強(qiáng)連通自動(dòng)機(jī)是在自動(dòng)機(jī)中的一種十分特殊的自動(dòng)機(jī),其不同于文[1-9]中的自動(dòng)機(jī),它要求狀態(tài)轉(zhuǎn)移必須是任意狀態(tài)之間均可進(jìn)行.群自動(dòng)機(jī)[1013]是在經(jīng)典自動(dòng)機(jī)基礎(chǔ)上擴(kuò)展而成的.其將一般的狀態(tài)集拓展到代數(shù)群上.本文將群自動(dòng)機(jī)和模糊集理論結(jié)合,提出了模糊群自動(dòng)機(jī)的概念,這是模糊自動(dòng)機(jī)理論的自然推廣.

設(shè)Σ是字母表,Σ?是Σ上的字符串集合,是一個(gè)么半群.設(shè)x=a1a2…an是一個(gè)字符串, 稱an…a2a1為x的逆像,記為xR.ε為空字符.

2 強(qiáng)連通模糊自動(dòng)機(jī)

定義2.1[6]一個(gè)模糊有限自動(dòng)機(jī)是一個(gè)五元組A=(Q,Σ,δ,I,F),其中Q是狀態(tài)的非空有限集,Σ是非空有限字母表,δ:Q×Σ→Q×[0,1]為狀態(tài)轉(zhuǎn)移函數(shù),I?Q是初始狀態(tài),F?Q是終止?fàn)顟B(tài)集.

為了運(yùn)算的方便,定義映射δ0為δ0(q,x)=p,當(dāng)且僅當(dāng)δ(q,x)=(p,μ),從而狀態(tài)轉(zhuǎn)移函數(shù)δ?可以擴(kuò)展為從Q×Σ?到Q×[0,1]的映射,滿足:(1)?q∈Q,δ?(q,ε)=(q,1);(2)?q∈Q,x∈Σ,y∈Σ?,δ?(q,xy)=δ?(δ?(q,x),y),其中δ(q,xy)=(p,μ),δ(q,x)=(p1,μ1),δ(p1,y)= (p,μ2),μ=min{μ1,μ2}.

定義2.2設(shè)A=(Q,Σ,δ,I,F)是模糊有限自動(dòng)機(jī).如果?q,p∈Q,均存在x∈Σ?,使得δ(q,x)=(p,μ)且δ(p,xR)=(q,μ0),則稱A是模糊強(qiáng)連通自動(dòng)機(jī).

對(duì)于強(qiáng)連通自動(dòng)機(jī)來說,其狀態(tài)轉(zhuǎn)移圖是連通圖,而且是完全圖.

定義2.3設(shè)A1=(Q1,Σ,δ1,I1,F1)和A2=(Q2,Σ,δ2,I2,F2)是模糊有限自動(dòng)機(jī),?是從Q1到Q2的映射.

(2)如果?是從Q1到Q2的同態(tài)映射,且?是雙射,則稱?是從A1到A2的同構(gòu)映射.

(3)如果A1和A2之間存在同構(gòu)映射,則稱A1與A2相互同構(gòu),記為A1～=A2.

如果A1=A2,則稱A1與A2之間的同態(tài)和同構(gòu)分別稱為自同態(tài)和自同構(gòu).記E(A)和G(A)分別為A上所有自同態(tài)和自同構(gòu)構(gòu)成的集合.顯然E(A)和G(A)分別為么半群和群.

性質(zhì)2.1設(shè)A=(Q,Σ,δ,I,F)是一個(gè)強(qiáng)連通自動(dòng)機(jī).如果?,ζ∈G(A),且存在q0∈Q使得?(q0)=ζ(q0),則?q∈Q,均有?(q)=ζ(q).即如果?,ζ只要在某點(diǎn)的像相同,則?=ζ.

證明由于A是強(qiáng)連通的,?q∈Q,必存在x∈Σ?,使得δ(q0,x)=(q,μ),從而δ0(q0,x)=q,所以?(q)=?(δ0(q0,x))=δ0(?(q0),x)=δ0(ζ(q0),x)=ζ(δ0(q0,x))=ζ(q).

性質(zhì)2.2設(shè)A=(Q,Σ,δ,I,F)是一個(gè)強(qiáng)連通自動(dòng)機(jī).則|G(A)|整除|Q|.

證明?p,q∈Q,如果存在?∈G(A),使得?(q)=p,則記p～q.顯然“～”是Q上的一個(gè)同余關(guān)系.記[q]={?(q)|?∈G(A)}.顯然[q]是含q且與q同余的一個(gè)類,稱為同余類.

定義2.4[9]設(shè)A=(Q,Σ,δ,I,F)是模糊有限自動(dòng)機(jī).如果?q∈Q,?x,y∈Σ?,均有δ(q,xy)= δ(q,yx),則稱A是可交換的.

交換性是代數(shù)中的一個(gè)重要性質(zhì),在自動(dòng)機(jī)理論有很重要的地位.

如果一個(gè)交換的模糊有限自動(dòng)機(jī)是強(qiáng)連通的,則稱其是完美自動(dòng)機(jī).

定理2.1設(shè)A=(Q,Σ,δ,I,F)是一個(gè)模糊有限自動(dòng)機(jī)，則A是完美的充分必要條件是A是強(qiáng)連通的,|G(A)|=|Q|,且G(A)是可交換的.

從而?ζ=ζ?,即G(A)是可交換的.

4)由于A是完美的,所以A必是強(qiáng)連通的.

(充分性)欲證A是完美的,根據(jù)條件知,只需要證明A是可交換的即可.

?q∈Q,x∈Σ?,由?x(q)=δ0(q,x)定義的映射?x必是A上的自同構(gòu)映射.

3 群矩陣型模糊自動(dòng)機(jī)

定義3.1[13]設(shè)G是一個(gè)有限群.設(shè)G0=G∪{0},其上定義了兩個(gè)代數(shù)運(yùn)算乘法“·”和加法“+”:

圖3 .1 A的狀態(tài)轉(zhuǎn)移圖

4 結(jié)論

自動(dòng)機(jī)的強(qiáng)連通性是自動(dòng)機(jī)理論中的一個(gè)重要研究內(nèi)容.其良好的狀態(tài)轉(zhuǎn)移導(dǎo)致了研究工具的多樣化.在本文,將模糊自動(dòng)機(jī)理論中的狀態(tài)集推廣到一般的代數(shù)群中.利用自動(dòng)機(jī)的連通性和代數(shù)群理論,討論了群自動(dòng)機(jī)的正則性.

[1]Hopcroft J E,Ullman J D.Introduction to Automata Theory,Languages and Computation[M].New York: Addison-Wesley,1979.

[2]Eilenberg S.Automata,Languages and Machines[M].Burlington:Academic Press,1976.

[3]Zadeh L A.Fuzzy sets[J].Information and Control,1965,8:338-353.

[4]Wee W G.On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification[D].West Lafayette:Purdue University,June 1967.

[5]柏明強(qiáng).模糊正則表達(dá)式與模糊有限態(tài)自動(dòng)機(jī)的關(guān)系[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2000,16(4):1-6.

[6]Su Lan,Mo Zhiwen.Closure of the fuzzy finite state languages[J].Fuzzy Sets and Systems,1995,75:393-397.

[7]Lee E T,Zadeh L A.Note on fuzzy languages[J].Information Science,1969,1:421-434.

[8]Zoltan Esik,Guangwu Liu.Fuzzy tree automata[J].Fuzzy Sets and Systems,2007(1):1450-1460.

[9]柏明強(qiáng).Fuzzy交換正則語言注記[J].四川師范大學(xué)學(xué)報(bào):自然科學(xué)版,2005,28(4):391-393.

[10]Ito M.A representation of strongly connected automata and its applications[J].J.Comput System Sci., 1978,17:65-80.

[11]Sengupta A.On a group-matrix type automaton with output[J].Acta Math.Hung.1986,48(3-4):347-352.

[12]Barnes B I-I.Groups of automorphisms and sets of equivalence classes of input for automata[J].J.ACM, 1965,12:561-565.

[13]Feichtinger G.Some results on the relation between automata and their automorphism groups[J].Computing, 1966,1:327-340.

Connectedness of fuzzy automata and group automata

BAI Ming-qiang,MO Zhi-wen
(Colledge of Mathematics and Software Science,Sichuan Normal University,Chengdu610068,China)

In order to study the structure and properties of fuzzy automata,based on theory of general fuzzy finite state automata,a kind of fuzzy automata is introduced with its states set made up of algebra group matrix by algebra methods.The connectedness of fuzzy automata is discussed,then the regularity too.This is a foundation for further researches on fuzzy automata.

fuzzy automata,group,strongly connected

O235

A

1008-5513(2009)03-0454-05

2008-11-10.

國家自然科學(xué)基金(10671030),四川省青年科技基金項(xiàng)目(07ZQ026-114).

柏明強(qiáng)(1976-),講師,主要研究方向：形式語言與自動(dòng)機(jī).

2000MSC:03D12,68Q68