（基础数学专业论文）关于若干广义析取语言和广义正则语言的研究.pdf

塑室奎兰堡兰兰堡鎏圣 ；一；一；一； ；垫茎 关于若干广义析取语言和广义正则语言的研究 基础数学专业硕士研究生黄磊 指导老师郭聿琦教授 摘要 本文主要利用句法同余和句法幺半群对若干广义析取语言和广义正则语言进 行研究首先，结合码的理论，我们详细讨论了由前缀( 后缀，双缀，内缀，外缀) 码 所定义的广义析取语青的性质，并给出了这些语言类之间的析取层次关系其次， 为回答刘云在其博上学位论文中提出的问题( 是否所有相对正则语言都可以分解 成正则语言和非稠密语言的并? ) ，我们讨论了稠密相对正则语言的若干性质，并 给出了该问题的一个等价刻划 关键词：语言句法幺半群广义析取语言相对正则语言码 堑里奎兰堡兰兰丝丝圣 垒呈量堡垒丝 s t u d i e so ns o m eg e n e r a l i z e dd i s j u n c t i v e l a n g u a g e sa n dg e n e r a l i z e dr e g u l a rl a n g u a g e s m a j o r ：a l g e b r a i ct h e o r yo fs e m i g r o u p s n a m e ：h u a n gl e i s u p e r d s o r ：p r o f e s s o rg u oy u q i a b s t r a c t i nt h i st h e s i s w em em o s t l ys y n t a c t i cc o n g r u e n c e sa n ds y n t a c t i cm o n o i d st o s t u d ys o i t i eg e n e r a l i z e dd i s j u n c t i v el a n g u a g e sa n dg e n e r a l i z e dr e g u l a rl a n g u a g e s f i r s t ，b yt h et h e o r yo f c o d e s ，w ed i s c u s st h eg e n e r a l i z e dd i s j u n c t i v el a n g u a g e sd e f i n e d b yp r e f i x ( s u 伍2 x ，b i f i x ，i n f i x ，o u t f i x ) c o d e s ，a n dw eg i v et h ed i s j u n c t i v eh i e r a r c h yo f t h ec l a s so ft h e s el a n g u a g e s s e c o n d ，t oa n s w e rt h eq u e s t i o n ( i se v e r yr e l a t i v e l y r e g u l a rl a n g u a g ec a nb ed e c o m p o s e da 8au n i o no far e g u l a rl a n g u a g ea n dat h i n l a n g u a g e ? ) p r o p o s e db yl i uy u ni nh i sd r t h e s i s ，w ed i s c u s 88 0 m ep r o p e r t i e s a b o u tt h ed e n s er e l a t i v e l yr e g u l a rl a n g u a g e s ，a n d 舀、，eae q u i v a l e n td e s c r i p t i o no f t h eq u e s t i o n k e y w o r d s ：l a n g u a g e s ，s y n t a c t i cm o n o i d s ，g e n e r a l i z e dd 蠲u n c t i v el a n g u a g e s ， r e l a t i v e l yr e g u l a rl a n g u a g e s ，c o d e s u 独创性声昵 学位论文题目：差王羞王亡墓盘垦透宣狸亡墓垂型适宣的盈究 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西南大学或其他教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者：易弘 签字日期：伊7 年f 月纱日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作 签字日期： 学位论文作 工作单位： 通讯地址： ：j 麓谂1 吒：奠口。牌j ( 月恪日 电话：塑膛2 生2 兰2 1 邮编：丝 塑童查兰堡圭兰篁篁圣； ；墼；童 前言 我们所说的语言指的是某个字母表( 或者叫做符号集) 上的一些有限序列组成 的集合对语言的研究是计算机科学中的一个重要内容由于语言理论不仅与理论 计算机科学、代数学、组合数学、概率论等一些理论性学科的发展密切相关，而 且在许多新兴的应用性学科如运筹学、控制论、最优化理论、密码学、生物信息 学中都有莺要的应用，因此他的发展越来越受到人们的关注 对语言的研究始于上世纪初到了上世纪四五十年代，在新崛起的计算机科学 的推动下，有了飞速的发展研究语言最常用的工具是自动机和文法他们都是表 示语言的有效工具最简单的一类自动机就是有限自动机它所识别的语言叫做正 则语言随着语言理论和半群代数理论的发展，从七十年代初起，一些学者开始用 句法幺半群( 或句法同余) 去定义和研究非正删语言其中h ，j s h y r 和c m r e i s 提出来研究的析取语言就是一个典型的代表f 2 1 析取语言类不是作为正则语言的 推广而提出的，无论在什么字母表上，它与正则语言类部不相交当字母表只含有 一个字母时，一个语言不是正则语言就是析取语言f 4 】关于析取语言的理论，从上 世纪七十年代到现在，国内外许多专家学者如h j s h y r ，郭聿琦，c m r e i s ，g t h i e r r i n ，m k a t s u r a ，s s y u ，y s t s a i ，s w j i a n g ，许光午，李廉等作了大量的 研究工作，主要的参考文献有 1 7 ，1 8 ，1 9 ，2 0 ，2 1 ，2 3 】当字母表含有至少两个字母 时，析取语言类与正则语言类这两个极端的边界线不再重合出现了既不析取又 不正则的语言从八十年代中期开始，郭聿琦，c m r e i 8 ，h j s h y r ，g t h i e r r i n ， a d p a r a d i s 等一些专家对析取语言作了各种推j r 作，在析取语言这个极端上 建立了一个层次结构，开创了语言的，“义析取层次的研究主要的广义析取语言 有：，析取语言 2 0 】，r ，一析取语言【2 1 】，q 一析取语言 1 】，q f - o 斤取语言等【17 j 刘云在他的博士学位论文中系统的研究了各类广义析取语言，结合码论定义 了若干由码定义的广义析取语言类，本文在第二章中主要对这类广义析取语言进 行了详细的讨论，并给出了这些广义析取语言类之问的析取层次关系另外作为 正则语言的推广，f 2 2 】中定义了相对正则语言，并指出在任何字母表上，一个语言 不是相对正则语言就是相对析取语言h 爿绕【2 4 l 中提出的问题( 是否所有相对正则 语言都可以分解成正则语言和非稠密语言的并? ) ，本文的第三部分主要是对稠密 相对正则语言进行讨论，并给出了这。问题的+ 个等价刻划，为问题的解决提供 了新的途径 西南人学硕+ 学似论文 第1 章基本概念 第1 章基本概念 在本章，我们给出论文中需要使用的概念与记号第1 节给出了半群代数理论 的些基本概念：第2 节则对我们所涉及的语言方面的知识作一个简单介绍关 于半群代数理论的系统介绍可参考h o w i e 的书【9 】或p e t r i c h 的书【14 】t 关于语言学， 码论方面的知识，可参考【7 ，8 ，1 6 而l a l l e m e n t 的书【1 3 】则包含了许多半群代数 理论在语言学及码论中的应用本文没有定义的概念与记号都是惯用的，都可以在 这几本书中找到 1 1 半群与幺半群 称二元组( s ，) 为一个半群，若s 是一个非空集，“”是s 上的一个满足结合律 的二元运算通常称此二元运算为这个半群的乘法运算在不引起混淆时，我们也 简称s 为半群将乘法a b 简记为0 6 ，其中a ，b s 令s 是一个半群1 s 称为s 的幺元，若 ( v s s ) l s = s l = s 0 s 称为s 的零元，若 ( v s s ) o s = s o = 0 称二元组( m ，1 ) ( 或简称m ) 为一个幺半群，若( m ，) 是一。个含有幺元1 的半群 我们总可以用以下方式给一个半群s 添加一个幺元使其成为。个幺半群令 1 垡s ，将s 的半群运算延拓到s o ( 1 ，上： ( v s s ) l s = s l = s ，1 l = 1 ， 则s t 3 1 ) 成为一个幺半群，1 为其幺元定义 q l j s 若s 含有幺元 。一1s u 1 ) 若s 不含幺元 半群s 的非空子集，称为s 的理想( 左理想，右理想) ，若s ju 碍i ( s i i ， j s n 称一个 左，右】理想，为主理想，若，可由s 中的一个元素牛成，显然s 自 身是s 的。个【左，右 理想s 的其他【左，右】理想称为真理想不含有真 左，右】理 想的半群称为f 左，右1 单半群 令x 是一个集合，我们称x x 的子集为x 上的2 2 元关系，简称关系，x 上 的所有二元关系构成集合记为b ( x ) 在关系的合成运算 p o j = “z ，y ) x x i ( 3 z x ) ( x ，z ) p ，( 。，y ) 6 ， 2 两南人学硕十学仲论文 1 1半群与幺半群 下，b ( x ) 形成一个幺半群，其中l x = ( z ，x ) l x x 为其幺元，称为相等关系称 x 上的关系p 为等价关系，如果p 满足 ( 1 ) 自反性( 1 x p ) ； ( 2 ) 对称性( ( z ，y ) p 辛( y ，z ) p ) ； ( 3 ) 传递性( ( z ，y ) p ，( y ，2 ) p = ( z ，：) p ) 令p 是x 上的一个等价关系，z x 则商集x l p = z p l x x ) 构成x 的一 个划分，我们称诸z p 为p 一等价类，简称p 类，p 称为渗透x 的子集l ，若工是x 的若干p 一类的并 称半群s 上的关系p 为左相容的，若 右相容的，若 相容的，若 ( w ，b ，c s ) o 加净础； ( v a ，b ，c s ) o 加辛a c p b c ； ( v a ，b ，c ，d s ) a p b ，c 膨辛a c p b d s 上的 左，右】相容的等价关系称为 左，右】同余 若p 是半群s 上的同余，则商集s p 在运算 ( 比，y s ) x p y p = v ) p 下形成半群，叫做s 关于p 的商半群 下面的一个同余称为句法同余，将在本文中经常用到 令l 是半群s 的一一个子集，z s 定义z 关于l 的上下文集为 c a n t l ( z ) = ( u ，u ) s 1xs 1i 乱王 l 关于l 的句法同余( 或主同余) p l 定义为( z ，y ) p l 当且仅当c o n t l ( z ) = c o n t ( y ) 即 p l = ( z ，可) s s i ( v u ， ) s 1 ) t 珏 l 当且仅当u y v l 我们通常将自然同态p 2 叫做句法同态，记为饥，称z s 所在的p l 一类x p l 记 为m l 命题1 1 令l 是半群s 的任一子集则p l 是s 上渗透l 的最大同余 3 堑查奎兰堡圭兰堡鎏圣；：兰皇里垒茎堑皇篁童 令s 是一个半群在s 上定义关系? ，曰，。形和9 如下 n 乡6 当且仅当 s 1 0 = s 1 b ( o ，b s ) ， n 曰b 当且仅当a s l = b s l ( o ，b s ) ， 8 夕6 当且仅当s 1 a s l = s 1 b s l ( n ，b s ) ， 而j 垆= ? v 留，9 = 彤a 曰这五个关系都是s 上的等价关系，称为g r e e n 关系 元素o s 所在的z ，历，夕，钟9 和互 类分别记作厶，心，五，f 和d 。 称半群s 中满足铲= 口的元素a 为幂等元，用e ( s ) 表示s 中所有幂等元组 成的集合称半群s 中的元素a 为正则元，若存在z s 使得a x a = a 记s 的所有 正则元组成的集合为r e g ( s ) 若r e g ( s ) = s ，则称s 为正则半群关于g r e e n 关 系和正则半群的基本理论可参考9 ，1 5 1 2自由幺半群与语言 令a 是一个非空有限集，称为字母表a 中的元素称为字母，a 上的有限序列 w = ( a l ，0 2 ，o 。) ，啦a ， 称为字a 上所有字组成的集合记为a 岔在连接运算 ( a l ，a 2 ，a m ) ( 6 1 ，5 2 ，k ) = ( a l ，a 2 ，a m ，6 1 ，b 2 ，k ) 下形成一个幺半群，叫做a 上的自由幺半群其中空序列0 是其幺元叫做 空字，记为1 我们通常将a a 与序列 n 等同起来，这样可以将 = ( a l ，0 2 ，) ，a i a 简记为w = a l a 2 n 。令a + = a + 1 ) 则a + 在连 接运算下形成半群，叫做a 上的自由半群 令w = a l a 2 一a 。，啦a ，i = 1 ，2 ，n 则称n 为字w 的长度，记为冶m ) ； 称a l ( o 。) 为字 3 的首字母( 尾字母) ，记为 ) ( ) ) 令a a ，w a + 记a 在w 中的出现的次数为i ”小 一个字 称为本原的，若w = u n ，t a ，n n ，意味着n = 1 a 上所有本原 字的集合记为q ( a ) 或简记为q 关于本原字有许多很好的结论，下面列举本文中将要经常用到的关于本原字 的两个引理： 引理1 2 ( 吲) 令，1 9 q ，g 则，”g “q 关于任意的m22 ，n22 成 立 4 西南人学硕十学位论文1 2 自山幺半群弓语言 引理1 3 ( 【7 】) 4 - f ，9 q ，g ，n 1 若，矿隹q ，l , l ，矿+ q 关于任 意的k 2 成立 令t ，口a 。称t 为 的前缀( 或左因子) ，若存在z a ，使得口= t l z 对称 的可以定义后缀( 或右因子) 的概念称u 为u 的内缀( 或因子) ，若存在z ，y a + ， 使得 = x u y 称u 为 的外缀，若存在z ，y ，z a ，使得t = x y ，口= x z y a 上 关系 p = ( u ， ) a + a i ( j z a ) 口= “z 是上的一个偏序关系，叫做前缀序同样的可以定义后缀序。和内缀序 称小的子集l 为a 上的语言称a 上的一个语言l 是有限语言，若| l l o o ， 反之，称为无限语言称a 上的语言l 是左，右1 稠密语言，若关于任意w a + ，存 在z ，y a + 使得 x w l ，w y l x w y 上反之，若个语言不是稠密语言则称 为非稠密语言关于稠密语言的性质可参阅文献f 6 1 令l 岔称a + p l 为语言l 的句法幺半群，记为跗n ( l ) 称l 为正则语言， 若1 5 肌) j 1 首先关于a 上的一1 个p 析取语言l ，我们有： 命题2 3 令l 是a 上的一个语言则以下两款等价： ( 1 ) l 是一个p 哳取语言( 8 - 析取语言，6 - 析取语言，i 析取语言，d 一析取语言) 6 西南人学硕十学化论文2 2 语言的件质 ( 2 ) 关于任意的t l ，t z q ，z a ，若“p l z ，n , iz = l ( 关于任意的 t ，黜口，z a 若牡p lz t ，则z = l ；关于任意的牡，跏，u y q ，z ，y a 若 t 正p lz “，“p l t 上耖则z = 1 ，y = 1 ；关于任意的t 正，x u y q ，z ，y a + 若u p l x u y ， 则x y = 1 ；关于任意的聊，x u y q ，t a 若叼p lx u y ，则t = 1 ) 证明( 1 ) 辛( 2 ) 由定义显然成立 ( 2 ) 辛( 1 ) 下面我们先证明命题关于p 析取语言成立，对s 斯取语言，6 - 析取语 言，伊析取语言可以类似证明 假设l 不是一个p 析取语言，即存在u ，t z a ，z a + ，使得u p l t z 若t 1 ，则令札= 哂( 札z ) ，z a ，且z l ( u ) 则显然z n u ，z “u z q ，且由 u p l 们得z n u p lz ”u z 矛盾 若“= 1 ，则令，i = 2 幻( z ) ，z a ，且： ( z ) 则显然z n x ，扩矿q ，而 z n x p ，z “舻矛盾 而关于i 一析取语言，情形要复杂些 若l 不是i 析取语言，即存在“，t u y a ，u p lr e u y ，x y 1 不妨假设1 ， 以卜分五种情况讨论 情形1 q ，t l ，x u y 聋q 令“= 广，m 彬= 9 m ，y = h ，9 ，h q ， n ，m 2 ，k 1 则有h ，h g 因为若h = ，则u ，x u y ，由上证明，矛盾若 h = g ，则u = g 9 5 ，9 。g ，8 n ，则“刍x u y ，由上证明，矛盾因此，由引理1 2 ， 得u y 2 = y h 驰q ，x u y y 2 = g m h 2 q ，u y 2 lx u y y 2 ，且u 鲈2p 上x u y j l l 2 ，矛盾 情形2 “盛q ，让1 ，x u y 0 令“= ，”，y = h ，删玑，h q ，n 2 ，k 1 则显然h x u y ，且h ，类似地，由引理1 3 ，存在m 3 ，使得z “鲫m = x u y h ”0 ，由引理1 2 ，u y ”= ，h m q 同理矛盾 情形3 “q ，茁仳掣隹q 令x u y = g m ，y = h ，u ，g ，h q ，m 2 ，k 1 则同 理h ，h g 由引理1 3 ，存在n 3 ，使得u y “= u h 础q 同时，由引理1 2 ， x u y y n = 9 m 柏q 同理矛盾 情形4 t q ，x u y q 显然矛盾 情形5 = 1 类似关于p 斩取语言的讨论，可得矛盾 闪此结论成立 口 推论2 4 令l 是a 上的一个语言若关于任意a 。，叫c n 0 是前缀码( 后 缀码，双缀码，内缀码，外缀码) ，则l 是p 一析取语言( s 一析取语言，6 哳取语言，i - 析 取语言，d 哳取语言) 证明由命题2 3 直接可得 7 口 堑至叁兰至圭耋丝篁圣；：兰重童竺丝里 注1 一般来说，关于a 上的一个语言l ，“a ，若阻】l n q 是前缀( 后缀， 双缀，内缀，外缀) 码，m l 不一定是前缀( 后缀，双缀，内缀，外缀) 码例如：令 a = 口，6 ，l = u 箍1 ( 缸) 2 “1 b 容易验证 n l i = 1 ，2 ，) 是一个p r 类，并且 ) n q = n ) 是一个前缀( 后缀，双缀，内缀，外缀) 码，但显然 ) 不是码 关于正则语言与我们所讨论的这些由码定义的广义析取语言之间的关系，我 们有如下命题 引理2 5 ( f 2 4 】) p - 析取语言，s 一析取语言，6 哳取语言，i 哳取语言，0 4 q 蝌- 都是稠密语言 命题2 6 令l 是a 上的一个i - 析取语言，r 是a 上的一个正则语言，且r l 则l r 是一个i 析取语言 证明若l r 不是i 一析取语言，则存在u ，x u y a + ，鲫a + ，满足“p l rx u y 因此关于任意i ，j n ，有u y p l k rx j u y j 由于冗是一个正则语言，故 t ，x u y ，z 2 u y 2 ，z ”让p “ 中必存在l j n ，使得x z u y p nx 3 u y 3 另一方面，由于工是个 一析取语言，且一u y z “矿，又由引理2 5 ，故存 在8 ，t a 使得8 x u y l t l ，s x j u y j t 硭l ，或者反之 不妨设s x 。u y 4 t l ，s x u y z t 隹l 则8 x j u y j t l r ，由x i u y p l rx u y j 得 矿u y 隹l 冗 又由于s t 以l ，故有s ，u y 。t r ，即存在8 ，t a ，使得 s z 2 u y l t r ，s u 矿f 岳r l 这与z 。u y lp rx u y j 矛盾故结论成立 口 类似地，我们可以证明 命题2 7 令l 是a 上的一个p 一析取语言( s 一析取语言，6 哳取语言) ，r 是 上的一个正则语言，且r l 则l r 是一个p 一析取语言( s 一析取语言，6 哳取语言 ) 8 堑童奎兰堡圭兰竺篁兰；：；：重童垄墼堑坠星奎 注2 命题2 6 的证明过程不能被用于证明l d 。的情形，但同时我们也没有 例子说明当l d 。时命题2 6 不成立 关于p 斯取语言，s 晰取语言，b 析取语言， 斯取语言，o - 析取语言的句法幺半 群，我们有如下几个命题 命题2 8 令l 是a 上的一个p 一析取语言( s 哳取语言，6 哳取语言，t 哳取语 言，d 哳取语言) 则s y n ( l ) 1 不舍正则元 证明令l 是a 上的一个伊析取语肓 若【u 】l 是s y n ( l ) l 中的个j 下则元，则存在m l s y n ( l ) ，使得阻】l 阻1 l 沁】l = 阻k 即u p l “7 u 矛盾 对s 析取语言，渐取语言，硝斤取语言可类似证明因此，命题成立 口 命题2 9 令l 是a 上的一个p 一析取语言( s 哳取语言，6 哳取语言，i 哳取语言 ) 则s y n ( l ) 上的劈( ? ，9 ，夕) 关系是相等关系， 证明我们只证明命题对矿析取语言成立，其余语言可类似证明 令阻】l m l s y n ( l ) 若【u i l , 曰 v l ，! i ! i j 存在【s 】l ，【t l s y n ( l ) 1 ，使得 阻】= ( “】l p l c ；【”】l = f u l i t l 故阻】l = m l h l = 【叫l 【c 】【s 】l ，即u p lu t s 矛盾故结论成立 口 2 3语言类的析取层次 本节主要讨论p - 析取语言类，s 一析取语弃类，撕取语言类，f 析取语言类，p 析 取语言类之间的析取层次得到主要结果如卜： 定理2 1 0 d i 互d b5d p ，d 。5d b ，d b 互d 。，d p 与d 。，d 。与d ，不可比 较 要证明上述定理，只需要构造四个语言厶，厶，岛，厶使得 l l d p d b ，l 2 d 。d 扣工3 d ，d 。，l 4 d 。d 令a = a ，6 ) ，x = u ( b a 2 - 1 b ，y = u 口”令l l = x y , l 2 = y x 易验证 n 2 ln = i l 1 是稠密语言，且若t l l ，则l i = 2 “，n = 1 ，2 ，因此，我们有： 9 西南大学硕+ 学付论文 2 3 语言类的析取层次 弓i 理2 1 1 若“p l 。 ，“，口a + ，舅日i u b i = = i 钉6 命题2 1 2 l l d p d b 证明若“p “，“a ，z a + 由引理2 1 1 ，得z = 扩，m 1 分以下三 种情形进行讨论： 情形1 若u = 1 ，则必存在n n ，使得对任意z n ，有妒+ m 2 因此 b 2 a z l ，而6 2 0 ”n ”隹l 故【x l = 1 情形2 若u = a l x b h a i 2 b j 2 一6 ，其中山1 ，i l ，i ”，i 。，j 1 ，力，矗一l n ，则必存在h ，k ，n n ，使得对任意f n ，有h + j l + + 五= 2 ，而2 “+ m 2 冈此驴矿6 如a 2 “l ，而驴n t l 沙n m n ”垡l 情形3 若“= 一- l 口“一- 驴口“，其中“21 ，i i ，i 2 ，以一l ，歹l ，j 2 ，五一i n ，则存在 ，k ，n ，s n ，使得对任意的f n ，有h + j 1 + 如+ + 一l = 2 k , i 。+ n = 2 l z ，而i ，n + r n 2 因此驴- n l a n l ，而6 i l 矿i a h a m a “岳l 因此“l i “z ，与假设矛盾故l l d p 另一方面，易验证0 6 p l 。a 2 b 故l l 譬d ，即l l d p d b 口 类似可证明 命题2 1 3 二2 d 。d b 注3 由命题2 1 2 ，2 1 3 我们知道 d b = d p n d 。= l a l 阻】l p n s ，u a ) 互d p ( d s ) 另。方面，我们有 d p u d 。= l a 。i 【让】l p u s ，u a 冈为若存在u ， a ，其中m 】l p s ，m s p ，即存在s ，t a + ，使得 f “】= 【s 】l 阻 l ，p 】l = v l l t l ，则 矛盾 u 】l = 【s l l m l v l = u l l v l t l 令l 3 = ua 2 n x a ”，可以得到 t l = 1 命题2 1 4 l 3 d i d 。 1 0 塑查奎兰璧圭兰堡尘兰；：；! 童童耋塑堡坚星姿 证明类似命题2 1 2 证明，可得l 3 d 而易验证 b 4 p bb 2 a b 2 故l a d 。，即l a d i d 。 推论2 1 5 l 3 d b d 。 口 在定义l 。之前，我们先回顾形式文法的的概念我们称一个三元组r = ( v a ，p ) 是一个形式文法，其中y 是一个有限集，称为r 的词汇；a 是y 的一个子 集，a 中元素称为r 的终结符；p 是( 矿一4 ) + v 的有限子集，称为r 的文法规 则，并记“一 ，若( “， ) p 称一个字w 7 v 在f = ( v a ，p ) 中由 派生得到，若 = x u y ，w = x v y ，其 中z ，y v + ，并且一 我们称一个字w 在r 中可由w 牛成，若伽= 或存 在蛳，w l ，w n v 使得w = w o ，= t e ，且t t ，l 由w l 派生得到，0 s i n 一1 并记作w 专 7 关于任意j v a ，a + 的子集l ( f ，6 ) = a i6 导 称 为6 在r 下牛成的语言 当p 是无限集时，同样可以有上述定义利用形式文法的记号，我们令g = ( k a ，p ) ，其中 v = 口，。，p ，n ，6 ； a = o ，6 ； p = 盯_ n 2 虬1 ，d 2 l 1 p a 铲- l p p q 2 n - l 卢_ 0 2 k 1 ，n _ a ，p _ b in = 1 ，2 由p 的定义可以看出，文法规则a o ，卢一b ，只是一个字符的替换的过程， 为f 面讨论方便，我们记这两个规则为i 型规则同时记规则n 2 “1 一p q ”- 1 卢为 i i 型规则，记触2 “1 口一n 2 “一1 为i i i 型规则容易验证，p 中任意。个由口生成 的字 ，可以只通过i ，i i ，i i i 型规则生成令w ，w p 若w 7 可由t ，只通过i ( i i ， 1 1 1 ) 型规则生成，则我们记作与w t ( w g ，伽琴) 令l 4 = l ( g ，口) ，l 7 = ua 2 “1 由厶的定义，我们首先有如f 引理 ，l = i 引理2 1 6 令l 4 ，f 定义如上则下列两款成立： ( 1 ) l 7 l 4 ； ( 2 ) ( v x ，可a 4 ) ( v 叫l 7 ) ( n ) x w y l 4 争x b ) w b i y l 4 证明( 1 ) 任意t = a 2 。1 ，我们可通过如f 方式生成： 口_ 0 2 n 一1 = 与( 1 2 “i 1 1 西南大学硕十学位论文2 3 语言类的析驭层次 故4 ( 2 ) 我们首先证明若t i ，”l ，t 睨v ，且w 三”l 旦二型! - 2 ，则存在i v 使得枷旦型已钾i 三忱 不妨令 = s n ，i i ) l = s a t ，s ，v 则由p 的定义，w 2 = s p a t 或者w 2 = s a t ， 其中s 坐磐，t 旦唑f 7 不妨令耽= s t a r i = s 7 c t t 则 ! 坐骂 ：三也 因此，任意i t l 4 ，存在( v a ) ，使得 且若i t = a l t 驴i n n 抄，i t , 五20 ，z = 1 ，2 ，n ，则叫7 = n t 1 口“砂因此 若x a y l 4 ，则存在s o t ( y a ) ，且盯_ n 护一l 尘当s a t5x a y ，85z t 与y 故我们从口可作如下生成得到z 驴n 驴玑j 1 ， 盯一0 2 n _ 1 些驾s a t 錾s o 每z 护n ! ， 因此z 护n l 4 同理可证若x b i a b j y l 4 则x a y l 4 由引理2 1 6 ，我们可以得到 引理2 1 7 工4 是左稠密语言，也是右稠密语言， 证明，关于任意“a + ，令“= a i l 砂n “弘，其中i t ，j r n ， 再令u 7 = 沙a ：沙一，n 2 ：一- t c a “，其中i ：n ，且满足： ( 了l n l 礼2 n ) i ：= 2 “1 1 一 l ， i ：= 2 1 2 “1 一i z ，z = 2 ，3 ，s 则 “t = t g a 2 。一2 ”。1 一“驴卜i 驴l n 2 “1 1 一i t a i l b j l 0 2 。驴 由引理2 1 6 ( 1 ) ，舻一1 l 4 ，f = l ，2 ，s 故由引理2 1 6 ( 2 ) 得 口 a 2 “。一1 l 4 辛抄n ”一1 砂l 4 = 6 ，一a 2 n s - - 2 n s - l - - i s 护- 1 a 2 “- 1 16 ，卜1 0 l 驴l 4 j 辛抄n ”一2 。1 一“砂一】砂a 2 4 1 1 1 铲护a r a b ，一厶 故l 4 左稠密同理可让厶右稠密 1 2 口 关于小6 上任意一个字u ，我们都可以写作如下形式 1 = 6 如z 驴- 厶k 一1 口如驴n ， 其中j o ，j n 0 ，j l , j 2 ，矗一1 ，i i ，i 2 ，i n l 令 d ( ) = 靠， w h e r ei o + i 1 + + “2 n + 1 e ( = 靠，w h e r ei o + l + + 旗2 n o k n 显然若 口，则d m ) = f ( u ) = 0 并且我们还有： 引理2 1 8 关于任意“l 4 ，0 ( “) = e ( u ) 证明，由l 4 的定义，存在w o ，w l ，w n v ，使得w o2 口，5 t ，且 毗_ + w ，+ l ，i ：0 ，1 ，n 一1 令叫a + ，且w i ；越则命题等价证明d ( 以) 2 e ( 以) ，i = 1 ，2 ，n 我们对i 使用数学归纳法 当i ：1 时，由p 的定义，训1 = 0 t 2 - 1n 1 ，故q = n 2 “1 ，因此o ( w 1 ) 2 e ( w l 、= 0 假设当l ：时成立当i = + 1 时，t i k 一 w k + 1 有三种情形： 情形1 当w k 三w k + l 时， o ( w 。t + 1 ) = o ( 叫：) = e ( 叫：) = e ( 叫：+ 1 ) 情形2 ，当饥卫w k + l 时 d ( 枷：+ 1 ) = o ( w i ) + 1 = e ( w d + 1 = e ( t 以+ 1 ) 情形3 当饥卫虮+ l 时 d ( 以+ 1 ) 一d ( ：) 一1 = e ( ：) 一1 = e ( w k + 1 ) 因此，综上讨论结论成立 推论2 1 9 若“= x y 厶，z ，a + ，则z 驴口譬l 4 ，j 1 引理2 2 0 若“p l 。口，则l u 。i = i i 命题2 2 1 l 4 d 。d t ， 1 3 口 西南大学硕十学何论文2 4 语言类的件质 证明由引理2 1 6 ，显然a p l 。b a b 故l 4 隹d i 下证l 4 d o 若x yp l 。x u y ，。，y a ，t a + ，则由弓i 理2 2 0 ，n = b j ，j 1 由弓i 理2 1 7 ， 存在a ，使得u x y l 4 ，因此u l x b i y l 4 由推论2 1 9 ，矛盾故结论成 立 口 推论2 2 2 l 4 d b d i 定理2 1 0 的证明由命题2 1 2 ，命题2 1 3 ，命题2 1 4 ，命题2 2 1 ，及推论2 1 5 ，推 论2 2 2 可得 口 2 4 语言类的性质 我们称一个语言类l 是a f l ，若l 关于并，连接，+ ，1 - f r e e 同态，逆同态，以及 与正则语言的交( 具体定义参见【7 】) 都封闭若l 关于上述六个运算都不封闭，则 l 称为一个a n t i - a f l 在f 2 ，4 1 中，指出了d ，dr 都是a n t i a f l 语言类另外还给出了其他一些语 言类都是a n t i - a f l ，如o l 语言类，拟析取语言类，a u t o - 析取语言类下面我们 证明p 析取语言类，s 一析取语言类，澌取语言类，i 晰取语言类，0 - 析取语言类都是 a n t i - a f i 命题2 2 3 p 哳取语言类，s 一析取语言类，6 哳取语言类， 一析取语言类，d 一析取 语言类都是a n t i a f l ， 证明令a 是个有限字母表 ( i ) 若是岔上的一个p - 析取语言( s 一析取语言，蜥取语言，争析取语言，i - b ? 取语言) ，则l c = a + l 也是p 晰取语言( s 一析取语言，b 斩取语言，弘昕取语言，口- 析取语言) 而lul c = a 是正则语言放它们关于并运算不封闭 ( i i ) 在i a i = 1 时，有d d p = d 。= d 6 = d ，= d 。，故参见【2 】命题4 4 0 ( i i ) ， 可得以上析取语言类关于连接，+ 运算不上寸闭另外，第三节构造的l 1 是一个p 析 取语言，研也是矿析取语言，而l l q 不足p 斯取语言，因为容易验证b 2 ap l ，t y a 2 f i i i ) 因为有限语言部是正则语言，所以以i - 并语言类中语言和有限正则语言的 交是正则语言，故关于同正则语言的交不封闭 ( i v ) 令a l = n ，a 2 = 。，6 ) ，h 是从a ：到如的同态，其中h ( a ) = h ( a b ) ， 令l = 0 2 ”i n n a ：则l 是析取语言，也足p 析取语言( s 析取语言，撕取语 言，卅斤取语言，o 一析取语言) 而h ( l ) = ( 0 6 ) 2 ”1n a ；是非稠密语言，故不 1 4 堑查查茎堡圭兰堡鎏兰! 兰重童垄竺篁星 是p 斩取语言( s 一析取语言，b 折取语言，i 斯取语言，渐取语言) 因此以上语言类 关于1 - f r e e 同态映射不封闭 最后令g 是禽到如的同态，其中9 ( n ) = o 由第三节构造的l l ，l 2 ，如，l 4 ( 对 l 。单独定义9 ( 口) = b ) 分别是生上的p _ 析取语言， 析取语言，d i 析取语言( 同时 也是澌取语言) ，i - 析取语言而g - t ( l 1 ) = g - i ( l 2 ) = g - i ( l 3 ) = g - 1 ( 厶) = o ，显 然不是析取语言故以上语言类关于同态逆像不封闭口 1 5 塑里垒兰堡圭兰篁鎏兰；望i 兰堡童塑型至! ! 重童墼堕篁 3 1引言 第3 章稠密相对正则语言的讨论 我们知道，当字母表只含有一个字母时，一个语言不是正则的就是析取的但 当字母表所含字母至少两个时，各种语言类之间的层次关系相对复杂1 9 8 8 年，郭 聿琦，c m r e i s 和g t h i e r r i n 定义了相对析取语言的概念相对析取语言是一种 与正则语言类不交的广义析取语言类另一方面，作为正则语言的推广，刘云在 2 2 1 中定义了相对正则语言，并对其进行了详细讨论，证明了一个字母表上的语言不是 相对析取就是相对正则2 2 1 中还指出任何非稠密语言都是相对正则语言，这样我 们可以把相对正则语言看成正则语言与非稠密语言的共同推广另外f 2 4 1 中提出 了个问题：是否任意相对正则语言都可以分解成正则语言与非稠密语言的并? 因 为o 是正则语言也是非稠密语言，所以该问题对非稠密的相对正则语言，以及正则 语言显然成立因此我们本章中主要对稠密相对正则语言的性质进行了讨论，虽然 我们对该问题没有给出最后刚答，但于第二节中我们给出了另外一类语言，给出了 该问蹶的个等价刻划 定义3 1 令l 小称l 为相对正则语言，若存在中的一个理想i ，使得 i i p l i 佗，则存在z ，z a ，y a + ，满足： ( 1 ) x y z = w ； ( 2 ) l g ( x y ) n ； ( 3 ) x y + o l 而关于a 上的任意一个稠密相对正则语言二，我们有 命题3 3 令l 是a 上的一个稠密相对正则语言，则存在加l ，x ，z a + ，y a + ，满足： ( 1 ) x y z = i ( 2 ) x y z l 1 6 堑童奎兰至圭兰丝篁圣； ；! 耋丝重 证明由于l a 是一个相对正则语言，故存在中的非空理想j ，使 得i ，吃i o o 任取u 1 1 i ，关于任意口矿，集合 s = 加l ， l 口2 ，- ， l ”， j 是无限集，故必存在i ，故l n q = o 但是当i a l 2 时，我们有：