模糊自动机的强连通性及群自动机
2009-07-05柏明强莫智文
纯粹数学与应用数学 2009年3期
柏明强,莫智文
(四川师范大学数学与软件科学学院,四川成都 610068)
模糊自动机的强连通性及群自动机
柏明强,莫智文
(四川师范大学数学与软件科学学院,四川成都 610068)
为了更好地研究模糊自动机的结构和性质,采用代数的方法,在传统的模糊有限状态自动机的基础上,通过定义状态集合为代数群的自动机,讨论了这一类自动机的连通性和正则性,这丰富了模糊自动机理论.
模糊自动机;群;强连通
1 前言
自动机理论是经典语言理论的一个重要内容,虽然其理论较为完善,但是研究成果仍然不断涌现[12].自1965年Zadeh[3]提出了模糊集合的概念后,Wee[4]迅速将模糊集应用于自动机理论的研究,提出了模糊自动机.到现在为止,模糊自动机与模糊语言的研究成果也是十分丰富[59].强连通自动机是在自动机中的一种十分特殊的自动机,其不同于文[1-9]中的自动机,它要求状态转移必须是任意状态之间均可进行.群自动机[1013]是在经典自动机基础上扩展而成的.其将一般的状态集拓展到代数群上.本文将群自动机和模糊集理论结合,提出了模糊群自动机的概念,这是模糊自动机理论的自然推广.
设Σ是字母表,Σ∗是Σ上的字符串集合,是一个么半群.设x=a1a2…an是一个字符串, 称an…a2a1为x的逆像,记为xR.ε为空字符.
2 强连通模糊自动机
定义2.1[6]一个模糊有限自动机是一个五元组A=(Q,Σ,δ,I,F),其中Q是状态的非空有限集,Σ是非空有限字母表,δ:Q×Σ→Q×[0,1]为状态转移函数,I⊆Q是初始状态,F⊆Q是终止状态集.
为了运算的方便……
登录APP查看全文
