格值文法及其语言

论文摘要

本文研究的主要内容是格值文法及其语言。李永明教授在文[19]中建立了一个新的模糊自动机模型,即格值自动机,在一个比以往研究的模糊自动机更广的框架—格半群意义下,来研究自动机理论.文[19]中已经证明对于格值语言,不确定型格值自动机(LA)比确定型格值自动机(DLA)识别语言的能力更强,并且从层次结构上来讲,格值自动机比一般模糊自动机能识别更广泛的模糊语言。而在经典自动机与一般模糊自动机理论中,有一个重要的结论就是文法生成的语言与自动机识别的语言等价。既然在格半群意义下DLA与LA不等价,我们自然关心的问题就是DLA与LA识别的语言分别可以用怎样的文法来刻画。从这个问题出发,本文主要探讨了格值正则文法的结构,格值自动机与格值正则文法的等价关系,格值正则语言的性质,格值上下文无关文法及其语言的性质等问题。 本文共分四章,第一章主要回顾了经典自动机与形式语言的相关知识,包括经典有限自动机的定义,文法的定义与分类以及经典自动机理论中几个重要结论。 第二章:在自动机理论中,基于格半群,引入格值自动机及其识别的语言的定义,格值正则文法及其产生的语言的定义,给出格值正则文法的分类,找出了用格值正则文法刻画确定型格值自动机的形式.主要得出如下结论: (1)格值正则文法与格值自动机等价; (2)确定格值正则文法与确定型格值自动机等价。 第三章:在格值文法的框架下重新给出了格值正则语言的各种运算对应的文法的构造,从文法的角度来研究语言的性质,讨论了格值正则语言关于正则运算的封闭性及其条件。主要得出如下结论: (1)格值正则语言在并,连接,Kleene闭包和数乘运算下封闭; (2)格值正则语言关于广义交运算,反转运算封闭的充要条件是·运算满足交换律。 (3)确定格值正则语言在并,交,广义交,连接,反转及数乘运算下封闭。 (4)确定格值正则文法与格值正则文法等价的充要条件是由格L的任意有限子集L’生成的(L,·,V)的子代数是有限的。 第四章:继续在格半群意义下,介绍格值上下文无关文法,给出了将格值上

论文目录

• 前言
• 第一章 经典自动机与形式语言知识回顾
• §1.1 引言
• §1.2 预备知识
• §1.3 经典自动机介绍
• §1.4 形式语言和文法
• 第二章 格值自动机和格值正则文法
• §2.1 引言
• §2.2 基本概念
• §2.3 格值正则文法和格值自动机
• §2.4 用格值正则文法刻画确定型格值自动机
• 第三章 格值正则语言及其性质
• §3.1 引言
• §3.2 格值语言运算的定义
• §3.3 格值正则语言关于正则运算的封闭性
• §3.4 确定格值正则语言关于正则运算的封闭性
• §3.5 确定格值正则文法与格值正则文法等价的条件
• 第四章 格值上下文无关文法与格值下推自动机
• §4.1 引言
• §4.2 最左（右）派生
• §4.3 格值上下文无关文法的两种范式
• §4.4 格值上下文无关语言的性质
• 总结
• 参考文献
• 致谢
• 攻读硕士学位期间的研究成果