幺半環(huán)上模糊有限狀態(tài)機(jī)的一些性質(zhì)

湯恒琦,鄧培民,易忠

(1.廣西師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,廣西桂林 541004;2.浙江省金華第一中學(xué)數(shù)學(xué)教研組,浙江金華 321015)

幺半環(huán)上模糊有限狀態(tài)機(jī)的一些性質(zhì)

湯恒琦1,2,鄧培民1,易忠1

(1.廣西師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,廣西桂林 541004;2.浙江省金華第一中學(xué)數(shù)學(xué)教研組,浙江金華 321015)

狀態(tài)機(jī)的很多性質(zhì)在計(jì)算機(jī)等方面有著廣泛的應(yīng)用,因此對(duì)狀態(tài)機(jī)的研究具有重要的意義.本文給出了幺半環(huán)上模糊有限狀態(tài)機(jī)的概念,對(duì)狀態(tài)之間的等價(jià)進(jìn)行了定義,引入了同態(tài)的概念,得到同態(tài)定理和滿同態(tài)分解定理,討論了幺半環(huán)上模糊有限狀態(tài)機(jī)在同態(tài)下的交換性質(zhì)和連通性以及子狀態(tài)機(jī)的可分離性.

幺半環(huán)；狀態(tài)機(jī)；交換性質(zhì)；連通；分離；同態(tài)

1 引言

20世紀(jì)60年代以來(lái),(模糊)狀態(tài)機(jī)的理論得到迅猛發(fā)展,它不僅在計(jì)算機(jī)科學(xué)及其相關(guān)語(yǔ)言、軟件等方面有著重要應(yīng)用,而且對(duì)于物理、生物、生物化學(xué)等領(lǐng)域有著重大影響.有很多文獻(xiàn)利用代數(shù)的方法對(duì)(模糊)狀態(tài)機(jī)的基本性質(zhì)和數(shù)學(xué)結(jié)構(gòu)進(jìn)行了研究[17]).文[1]介紹了有限狀態(tài)機(jī)的同態(tài)的概念,并詳細(xì)地討論了有限狀態(tài)機(jī)的分解問(wèn)題.文[3]給出了模糊有限狀態(tài)機(jī)的子狀態(tài)機(jī)和可回復(fù)的、可分離的以及連通的模糊有限狀態(tài)機(jī)的概念,討論了它們的基本性質(zhì),給出了模糊有限狀態(tài)機(jī)的分解定理.作為模糊有限狀態(tài)機(jī)的推廣,本文給出了幺半環(huán)上模糊有限狀態(tài)機(jī)的定義,引入了同態(tài)的概念.對(duì)于幺半環(huán)上的兩個(gè)模糊有限狀態(tài)自動(dòng)機(jī)M和M'來(lái)說(shuō),若存在從M到M'的一個(gè)滿同態(tài),則M滿足交換性質(zhì)當(dāng)且僅當(dāng)滿足M'交換性質(zhì);并且當(dāng)M'的狀態(tài)個(gè)數(shù)多于一個(gè)時(shí),M是強(qiáng)連通的當(dāng)且僅當(dāng)M'是強(qiáng)連通的;對(duì)于連通的情形就不一樣了,由M連通可以推出M'連通,反過(guò)來(lái)則不成立.在同態(tài)作用下,子狀態(tài)機(jī)的同態(tài)逆象仍然是子狀態(tài)機(jī);如果可分離的子狀態(tài)機(jī)的狀態(tài)集的逆象非空,則可分離的子狀態(tài)機(jī)的同態(tài)逆象依然是可分離的子狀態(tài)機(jī).在滿同態(tài)作用下,(可分離的)子狀態(tài)機(jī)的同態(tài)像仍然是(可分離的)子狀態(tài)機(jī).

2 基本知識(shí)與記號(hào)

定義1[4]一個(gè)幺半環(huán)R=(R,+,…,0,1)是具有兩個(gè)二元運(yùn)算“+”和“…”,并且滿足下列四個(gè)條件的一個(gè)代數(shù)系統(tǒng):

(a)(R,+,0)是一個(gè)交換幺半群;

(b)(R,…,1)是一個(gè)幺半群;

(c)乘法對(duì)加法滿足分配律,即?a,b,c∈R

如果幺半群(R,…,1)是交換的,則稱R為交換幺半環(huán);如果幺半群(R,+,0)和(R,…,1)都滿足消去律,則稱R為可消幺半環(huán).若R對(duì)乘法滿足消去律,則R中無(wú)非零零因子.在半群(R,+,0)中,若?a,b∈R,a+b=0當(dāng)且僅當(dāng)a=0且b=0,則稱R中無(wú)負(fù)元.

注下文假設(shè)R是一個(gè)對(duì)乘法滿足消去律且無(wú)負(fù)元的幺半環(huán).

定義2幺半環(huán)R上的模糊有限狀態(tài)機(jī)(簡(jiǎn)記為RFM)是一個(gè)三元組M=(Q,Σ,δ),其中非空有限集合Q,Σ分別稱為M的狀態(tài)集和輸入字母集,映射δ:Q×Σ×Q→R叫做M的模糊狀態(tài)轉(zhuǎn)移函數(shù)(即δ是Q×Σ×Q的一個(gè)R值模糊子集).

證明對(duì)y的長(zhǎng)度用歸納法可得證.

說(shuō)明：定義3-定義8中的概念與記號(hào)類似于文[3]的有關(guān)定義,命題2-命題4的結(jié)論與文[3]的中的相關(guān)結(jié)論相同,證明類似,本文不再證明.

定義3設(shè)M=(Q,Σ,δ)是一個(gè)RFM,p,q∈Q,如果?a∈Σ,使得δ(q,a,p)/=0,就稱p 是q的直接后繼,如果?x∈Σ?,使得δ?(q,x,p)/=0,就稱p是q的后繼;q的所有后繼構(gòu)成的集合用S(q)表示,設(shè)T?Q,T的所有后繼構(gòu)成的集合用SQ(T)表示,且有在不引起混淆的情況下,記S(T)代替SQ(T).

命題2設(shè)M=(Q,Σ,δ)是一個(gè)RFM,p,q,t∈Q,則有

(a)q是q的后繼;

(b)如果p是q的后繼,且t是p的后繼,則t是q的后繼.

命題3設(shè)M=(Q,Σ,δ)是一個(gè)RFM,A,B?Q,有下列式子成立:

(a)若A?B,則S(A)?S(B);

(b)A?S(A);

(c)S(S(A))=S(A);

(d)S(A∪B)=S(A)∪S(B);

(e)S(A∩B)=S(A)∩S(B).

3 RFM在同態(tài)下的性質(zhì)

圖1 同態(tài)交換圖表

[1]HoLcombe W M L.A lgebraic Autom ata Theory[M].Cambridge:Cambridge University Press,1982.

[2]Peeva K.Equivalence,reduction and minim ization of finite autom ata over sem irings[J].TheoreticalCom puter

Science,1991,88:269-285.

[3]Malik D S,Mordeson J N,Men M K.Submachines of fuzzy finite state machines[J].Journal of Fuzzy Mathem atics,1994,2:781-792.

[4]Malik D S,Mordeson JN,Men M K.Productsof fuzzy statemachines[J].Fuzzy Setsand System s,1997,92:95-102.

[5]Mordeson JN,Nair P S.Successor and source of(fuzzy)finite statemachines and(fuzzy)directed graphs[J]. In form ation Sciences,1996,95:113-124.

[6]Kumbhojkar H V,Chaudhair SR.On covering of productsof fuzzy statemachines[J].Fuzzy Setsand System s, 2002,125:215-222.

[7]鄧婷,易忠,鄧培民.狀態(tài)機(jī)的穩(wěn)定狀態(tài)與穩(wěn)定子集[J].廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2005,23(2):29-32.

[8]Tatjana Petkovi.Congruencesand hom om orphism sof fuzzy autom ata[J].Fuzzy Setsand System s,2006,157:444-458.

some properties of fuzzy finite state mach ines over unitary semirings

TANG Heng-qi1,2,DENG Pei-min1,YIZhong1

(1.College of Mathematics Science,Guangxi Normal University,Guilin 541004,China; 2.Mathem atics Research G roup,Jinhua No.1 High School,Jinhua 321015,China)

M any properties of statem achines have a w ide range of app lication in the areas such as com puter etc.,so the study to statem achines is very significant.In this paper,the notion of fuzzy finite statem achines over unitary sem irings is given,the equivalence between states of fuzzy finite state machines over unitary sem irings is defined,and the notion of hom om orphism between twofuzzy finite state m achines over unitary sem irings is introduced.Homomorphism Theorem and Epimorphism Decom position Theorem are obtained,and the exchange property,connectivity and separability of subm achines of fuzzy finite statem achines over unitary sem irings under hom om orphism are discussed.

unitary sem irings,statemachines,exchange property,connectivity,separability,homomorphism

O153.3,TP301.1

A

1008-5513(2009)02-0363-09

2007-11-05.

國(guó)家自然科學(xué)基金(60473005),廣西自然科學(xué)基金(0832103,0640061).

湯恒琦(1976-),碩士,研究方向:代數(shù)及其應(yīng)用,自動(dòng)機(jī)理論.

2000M SC:68Q 70