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