关于语言的可交换性质的研究

来源 :湖南科技大学 | 被引量 : 0次 | 上传用户:flish_mh
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设A是一个字母表。如果语言X,Y(C)A*满足XY=YX,则称X,Y是可交换的。如果语言X,Y(C)A*满足XY(C)YX或YX(C)XY,则称X,Y是部分可交换的。目前已知:在自由半群A*上,若x,y∈A+,xy=yx,则存在t∈A+,m,n>0,使得x=tm,y=tn。但上面的x,y换成可交换或部分可交换的语言(即A*的子集)时,情况就非常不同了。  本文首先对码在可交换和部分可交换下的性质进行了系统的研究。在码的可交换性质和非模糊集的关系方面,证明了:对于任意一个码,若它与一个语言可交换,则它们的积是非模糊的。在码的可交换性质和极大码的关系方面,证明了:与A*可部分交换的码是极大码。并且证明了:若X(C)A+是码,则X与A*可交换当且仅当存在正整数n,使得X=An。对于B.Ratoandromanana在上个世纪80年代末提出的猜想“任意一个码都存在唯一的本原根”,本文运用码的可交换性质给出了一个等价刻划,为解决该猜想提供了新的途径。  本文还对一般语言的可交换性质进行了研究,着重分析和讨论了与一个语言可交换的不包含空字的最大语言(即该语言的中心化子)的性质。证明了中心化子为有限生成的界限确实存在,即存在一个正整数n,使得:基数不超过n的语言的中心化子都是有限生成的,而对于任何大于n的正整数m,总存在中心化子不是有限生成的m元语言。为了进一步讨论中心化子为有限生成的界限问题,本文提出了二元奇异语言的概念,并且运用二元奇异语言的相关性质给出了关于四元语言中心化子的若干结论,证明了在大多数情况下四元语言的中心化子确实是有限生成的。
其他文献
加权概念格是针对属性的重要程度,通过引入内涵权值而形成的一种格结构,并通过引入虚结点概念,保证了格结构的完备性。本文,对加权概念格的渐进式构造以及分类规则提取进行了
现有的计算智能算法主要模拟了物理化学规律及动物的社会行为,对于植物的生长模式尚未给予足够重视。由于植物对环境的适应能力较强,生长速度较慢,因此,模拟植物的生长过程为