湯恒琦,鄧培民,易忠

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

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

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

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

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

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

1 引言

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

2 基本知識與記號

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

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

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

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

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

注下文假設R是一個對乘法滿足消去律且無負元的幺半環(huán).

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

證明對y的長度用歸納法可得證.

說明：定義3-定義8中的概念與記號類似于文[3]的有關定義,命題2-命題4的結論與文[3]的中的相關結論相同,證明類似,本文不再證明.

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

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

(a)q是q的后繼;

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

命題3設M=(Q,Σ,δ)是一個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)下的性質

圖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)機的穩(wěn)定狀態(tài)與穩(wěn)定子集[J].廣西師范大學學報:自然科學版,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.

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

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

2000M SC:68Q 70