重叠字及与重叠字有关的析取语言.pdf

《重叠字及与重叠字有关的析取语言.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级公幵编号碛士研究嗲位伦夂题目重叠字及■与重叠字有关的析取语言学院（所、中心）数学与统计学院专业名称应用数学研究生姓名倪光吕学号导师姓名曹春华职称副教授年月论文独创性声明及使用授权本论文是作者在导师指导下取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不存在剽窃或抄袭行为。与作者一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。现就论文的使用对云南大学授权如下：学校有权保留并向国家有关部门或机构送交学位论文和论文电子版；允许论文被查阅或借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制

2、手段保存论文；学校有权公布论文的全部或部分内容，可以将论文用于查阅或借阅服务；学校有权向有关机构送交学位论文用于学术规范审查、社会监督或评奖；学校有权将学位论文的全部或部分内容录入有数据库用于检索服务。保密的论文在解密后应遵循此规定）研究生签名浼另导师签名日期到摘要在本文中，我们构造了一类本原字以及证明了本原字的充要条件年，台湾学者人对重叠字和本原字的性质做了比较系统的研宄，并得到了：本原字中长度是奇数的所有字的集合是析取语言以及本原字中长度是偶数的所有字的集合是析取语言在他们另一个结论中，重叠字个数是的所有字的集合是析取语言在本文中，我们证明出重叠个数是的字的长度被除了之后余数是的所

3、有字的集合也是析取语言关键词：重叠字本原字前缀后缀析取AbstractInthispaper,weconstructsomekindsofrf——，—目录第一章预备知识半群和半群自由幺半群与语言幺半群第二章本原字的构造重要的定义及已有的相关引理主要研究结论第三章与⑴有关的析取语言重要的定义主要研宄结论总结与展望猶>t——月■』形式语言是研宄自然语言和人工语言的学科，在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研宄计算机的体系结构逻辑操作、程序设计乃至计算复杂性理论在语言学中则把自动机作为识别语言的工具，用来研究各种形式语言，人们普遍认为它是理论计算机科学的核心自动机论与

4、形式语言理论密切相关一方面自动机作为形式语言的一种主要描述方法，另一方面形式文法也可作为自动机识别集的一种描述途径，许多国内外学者致力于它的研究，得出较多重要的结论，见文献【】在年和提出了有限自动机的概念并对其进行了初步的研宄见文献【】此后，也开始着手于有限自动机理论的研究，提出一些新的概念，并得到了所有的本原字组成的语言是析取语言及相关的结论，见文献【，，】此后，人们即发现范式极其类似于形式语言理论中的上下文无关文法，从而开创了形式语言广泛应用于程序设计语言的发展的新篇章，并促进了形式语言理论的研究年，经过努力研宄，得出了正则语言不是析取语言的重要结论，此后又发表了有关析取和析取的重

5、要结论，见文献【】这些研究对我们更好地研究析取语言提供理论基础关于重叠字，文献【】中对它的性质进行了比较系统的研究，得出了判断是重叠字的方法并把重叠字进行按照重叠数目进行分类，此外，该文献中也构造出了一些与重叠字和本原字、重叠字和平衡字有关的语言，并对它们的析取性进行证明，例如⑷都是析取语言等本文在该篇文献的基础上，继续构造出了一些新的析取语言并发现⑷在求模运算下与本原字的交集、并集是析取语言，从而使我们对重叠字有了更深层次的理解在文献【】中，作者在整个自由么半群中取元素证明析取性而在本文中我们证明语言的析取性时，利用析取语言的一个等价命题，即在自由么半群中取元素时，只需取长度相等的元

6、素进行讨论，这样以来就可以简化证明过程在文献【，】中本原字是形式语言中的一个概念并给出了本原字和⑷语言的定义及其性质在此基础上，本文主要对本原字的构造进行研究，并得到了几种构造本原字的方法，而且给出了两个判断是本原字的充要条件第一章预备知识本章介绍论文中用到的记号、基本概念和性质第一节介绍半群及么半群背景知识；第二节介绍自由么半群及语言么半群等一些定义§半群和么半群如果非空集合带有二元运算并且这个二元运算满足结合律，那么我们就称为半群一般称半群的二元运算为乘法如果半群的非空子集对于中的乘法封闭，那么称为的子半群如果在半群中存在元素使得对任意的那么我们称是的单位这时称为么半群或带单位的半

7、群一个么半群是自由的当且仅当存在一个基，使得此时称为自由么半群令是半群§的子集，我们记儿则对任意的这样本如⋯就意义了同时我们将简写成其中有关半群的性质可参考文献【】令是一个非空集合，的子集称为上的二元关系我们通常把：写成如果满足下面的条件：对任意的对任意的；对任意的：￡那么我们就称是上的等价关系非空集合上的二元关系”“称为偏序，如果”“满足下面的条件：对任意的有；对任意的工，若工贝(3)对任意的，若贝！如果偏序再满足下面的第四个条件，则称为全序