论文部分内容阅读
作为自动机识别的语言,正则语言已应用于计算机程序语言编译的词法分析、开关电路设计等方面,并且在形式语言中有着重要的性质.从20世纪60年代以来,模糊自动机及其接受的语言得到了深入的研究.通常的模糊自动机,即取值在[0,1]单位区间的自动机,只能从层次结构的观点识别所接受的语言,为了克服这个问题,李永明将值域扩展到一般的格结构上,提出了格值自动机,因此有必要研究格值模糊正则语言的性质.对于取值在[0,1]区间上的模糊正则语言,确定的与非确定的是等价的,而对于格值正则语言,这个结论未必成立.Klimann [24]等人已经研究了不同种类加权自动机接受语言在tropical半环下的分级关系,在此我们讨论不同种格值模糊正则语言的分级及可判定性等问题.本文的主要工作如下:1.首先对格值模糊自动机分类,将其分为确定的、序列的、无歧义的、有限歧义的以及无限歧义的.其次,探讨了局部有限格序幺半群L对格值模糊正则语言等价性的影响,证明了L非局部有限时正则语言间存在真包含关系,并给出了几类格值模糊正则语言等价的充分条件.特别地,讨论了当L中的运算取阿基米德t-模时,格值模糊正则语言的性质.2.研究了格值模糊正则语言的可判定性问题.首先,给出了格值模糊正则语言相等(Eq)、不等(Ineq)、局部不等(LocalIneq)和局部相等(LocalEq)这几个待研究的可判定性问题.其次,证明了格值模糊正则语言的可判定性问题与格序幺半群的结构有关,即:若L局部有限,上述几类问题是可判定的,若L非局部有限,上述问题是不可判定的.最后探讨了有穷自动机的有穷分解,证明了任意的Boolen型矩阵都可以分解为余共合矩阵与共合矩阵的复合,并根据这一性质对共轭的自动机进行分解.