论文部分内容阅读
自动机和形式语言理论是计算机科学的理论基础.它在信息科学,生物学,管理学等众多学科领域中应用广泛.本文基于半群代数理论,围绕自动机的表示及分类,形式语言的代数刻画,权重自动机的极小化等问题进行了研究.本文的主要工作如下：(1)解决了标准Sl-自动机和标准C-自动机的分类问题.首先,研究了循环幺半群-矩阵型自动机和正则幺半群-矩阵型自动机的结构.然后,提供了一种关于标准Sl-自动机和标准C-自动机的分类方法.给定一个有最大元的下半格Y(或Clifford幺半群C),可以确定自同态幺半群与Y(或C)同构的所有标准自动机的结构.在此基础上,论文研究了幺半群-矩阵型自动机的特征幺半群和商自动机,讨论了特征幺半群和自同态幺半群之间的关系,同时利用半群同态给出了商自动机的一个刻画.(2)提出并研究了广义正规自动机和广义标准自动机,揭示了它们与本原自动机之间的关系.首先,利用极小生成元集,介绍了广义正规自动机和广义标准自动机的概念.接着,研究了广义正规自动机与其本原自动机之间的关系.最后,讨论了广义标准自动机的商自动机.(3)解决了几类与二元关系有关的形式语言的代数结构及确定性问题.首先,介绍了嵌入序的三个子集<Oi,<Li,<Ri.相应的独立集分别记为Oi(Σ),Li (Σ),Ri(Σ)接着,研究了这三类形式语言的组合性质和代数结构.证明了在某两个二元运算下,它们分别是三个半格序半群子簇的自由对象.同时解决了子簇的字问题.最后,指出这三类语言的确定性问题是P-问题.(4)给出了强双幺半群上权重自动机的同态定理和同构定理,构造了识别形式幂级数的极小自动机,并证明了在同构意义下是唯一的.