幺半环上模糊有限状态机的一些性质

汤恒琦,邓培民,易忠

(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