论文部分内容阅读
取值于格半群的自动机比其它形式模糊自动机能接受更为广泛的形式语言与模糊语言。因此,对取值于格半群的自动机极及其语言性质的研究是格值自动机理论的一个重要课题,而对不同类型格值自动机之间的关系及其语言代数性质的研究更是其中一个重要方面。 本文的工作主要是在文献[1,2,3,4]的基础上来研究几类常见的取值于格半群上的自动机之间的关系及格值正则语言的代数性质。 取值于格半群的自动机A=(Q,Σ,δ,σ0,σ1)按其转移函数δ是否为确定的可分为两大类:确定型格值自动机(简记为DLA)和非确定型格值自动机(即格值自动机,简记为LA)。再根据初始状态σ0和接受状态σ1是否为模糊的,确定型格值自动机可分为三类:DLA1,DLA2,DLA3;格值自动机可分为四类:LA1,LA2,LA3,LA4。文献[1]中已经证明了三类确定型格值自动机是等价的;确定型格值自动机和非确定型格值自动机是不等价的,并给出了二者等价的充分必要条件。本文则完全确定了四类非确定型格值自动机之间的关系:LA1,LA2,LA3是等价的,LA4与前三类格值自动机不等价。 格值自动机所接受的语言叫格值正则语言,确定型格值自动机所接受的语言叫确定型格值正则语言。在讨论清楚各类格值自动机之间的关系之后,本文的下一个重要内容就是要讨论格值正则语言的代数性质。常见的给出语言的方式有三种: (1) 通过自动机给出, (2) 通过正则表达式给出, (3) 通过文法给出。 本文首先给出了确定型格值正则语言和格值正则语言的代数定义,并证明了其代数定义与其各自以传统方式给出的定义是等价的。在此基础上,讨论了格值正则语言及确定型格值正则语言在一些重要的代数运算下的封闭性与不封闭性问题。这些代数运算包括格值正则代换,确定型格值正则代换,单位格值正则代换,格值模糊同态及格值模糊逆同态,同态及逆同态。对于确定型格值正则语言,我们得到了一些很好的代数性质;而对于格值正则语言,当其真值集L的乘法满足交换律的时候,我们也得到了一些很好的代数性质,但当L的乘法不满足交换律的时候,只给出了格值正则语言不封闭性的一个猜想。