论文摘要：格值代数系统

    从20世纪60年代以来, 上下文无关文法一直在编译技术中扮演着重要角色. 近几年, 上下文无关文法也被用于描述文档格式. 20世纪80年代, 为了从代数的角度研究上下文无关文法,I. Petre、A. Salomaa 和W. Kuich 在形式幂级数的基础上提出了代数系统的概念[1?3], 研究其解的判别条件及其与上下文无关文法、下推自动机之间的关系, 并证明了代数系统、上下文无关文法、下推自动机三者之间是相互等价的. 由于格值上下文无关文法与格值上下文无关语言的理论已经得到了较为完善的研究, 因此有必要建立格值代数系统的概念, 研究其与格值上下文无关文法、格值上下文无关语言的关系.      本文的主要工作如下:      1. 介绍了格值形式幂级数的相关理论. 首先, 给出了格值形式幂级数的概念, 定义了格值形式幂级数的和、Cauchy积、Hadamard积、Scalar积及Kleene闭包运算, 研究了它们的运算性质. 其次, 定义了自由循环格值形式幂级数, 研究了其关于乘法运算的封闭性. 最后, 定义了格值方程式, 并研究其解的存在条件.      2. 介绍了格值代数系统的相关理论. 首先, 在代数系统的基础上引入了格值代数系统的概念, 利用格值形式幂级数的性质, 研究了格值代数系统强解存在的条件. 其次, 给出了格值代数系统与格值上下文无关文法的转换法则, 证明了格值代数系统与格值上下文无关文法的等价性. 最后, 研究了格值代数系统与格值上下文无关语言的关系, 证明了格值代数系统的强解的某个分量就是与该格值代数系统等价的格值上下文无关文法生成的格值上下文无关语言.      关键词： 形式幂级数, 代数系统, 格值上下文无关文法, 格值上下文无关语言

来源：半壳优胜鲸鱼幸运星转载请保留出处和链接！

本文链接：http://87cpy.com/220433.html