幺半環上模糊有限狀態機的一些性質

湯恒琦,鄧培民,易忠

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

幺半環上模糊有限狀態機的一些性質

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

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

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

幺半環；狀態機；交換性質；連通；分離；同態

1 引言

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

2 基本知識與記號

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

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

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

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

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

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

定義2幺半環R上的模糊有限狀態機(簡記為RFM)是一個三元組M=(Q,Σ,δ),其中非空有限集合Q,Σ分別稱為M的狀態集和輸入字母集,映射δ:Q×Σ×Q→R叫做M的模糊狀態轉移函數(即δ是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在同態下的性質

圖1 同態交換圖表

[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]鄧婷,易忠,鄧培民.狀態機的穩定狀態與穩定子集[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-),碩士,研究方向:代數及其應用,自動機理論.

2000M SC:68Q 70