几类格值自动机的关系及其语言的代数性质

论文摘要

取值于格半群的自动机比其它形式模糊自动机能接受更为广泛的形式语言与模糊语言。因此,对取值于格半群的自动机极及其语言性质的研究是格值自动机理论的一个重要课题,而对不同类型格值自动机之间的关系及其语言代数性质的研究更是其中一个重要方面。 本文的工作主要是在文献[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的乘法不满足交换律的时候,只给出了格值正则语言不封闭性的一个猜想。

论文目录

• 前言
• 第一章 预备知识
• §1.1 模糊集的基本性质及基本定理
• §1.2 格半群的定义及其性质
• §1.3 格半群意义下映射的模糊扩张
• 第二章 几类格值自动机的关系
• §2.1 几类格值自动机的定义及其所接受的语言
• §2.2 几类格值自动机的关系
• 第三章 格值正则语言的代数性质
• §3.1 格值正则运算及格值正则表达式
• §3.2 格值正则语言的代数定义
• §3.3 格值正则语言在某些代数运算下的性质
• §3.4 一些结论及问题
• 总结
• 参考文献
• 致谢
• 攻读硕士学位期间的研究成果