（基础数学专业论文）关于若干语言及其句法半群的研究.pdf

关于若干语言及其句法半群的研究 专业：基础数学 博士生：刘云 指导教师：郭聿琦教授 摘要 0 1 4 7 7 1 本文主要利用句法同余和句法 幺l 半群对语言进行刻画与分类首先，利用s o l i d 码的理论，解决了郭聿琦，c m r e i s 和g t h i e r r r i n 于1 9 8 8 年提出的问题“是 否每一个f d - 辖区都是一致稠密的? ”其次，提出了半群中的拟长度的概念对带 拟长度的半群进行了详细的刻画给出了一类带 拟长度的半群是句法半群的 一个十分简单的判定条件，这类半群包含有限生成的带f 0 _ 1 拟长度的半群，有限丌群 以及有限逆半群的有限诣零扩张等为其子类利用这个部分的理论，我们对曾经被 许多学者研究过的以下问题给出了完满的回答：“如何刻画f 析取语言的句法f 幺1 半 群? ”，什么样的b 析取同余是句法同余? ”最后，我们对多种语言类进行了讨论先 给出了一些有关语言类的基本概念，讨论了语言类与幺半群类之间代数封闭性的联 系随后对各种广义析取语言进行了系统的讨论，给出了这些语言类的句法幺半群 刻画以及层次关系另外+ 我们还研究了一类广义正则语言，它不但是正则语言和薄 语言的共同推广，而且与许多广义析取语言类，码类以及f d 一辖区等多种语言类都有 着紧密联系，是一一类值得仔细研究的语言类 关键词：语言，句法 幺】半群，f d 一辖区，一致稠密语言，s o l i d 码，带厶拟长度的半 群，广义析取语言，相对正则语言 s t u d i e so ns o m el a n g u a g e sa n dt h e i r s y n t a c t i cs e m i g r o u p s m a j o r ：b a s i cm a t h e m a t i c s n a m e ；l i u 扬n s u p e r v i 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 eu s 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 cs e m i g r o u p s ( m o n o i d s ) t oc h a r a c t e r i z ea n dc l a s s i f yl a n g u a g e s f i r s t l y ，b ym e a n so ff u r t h e ri n v e s t i g a t i o no ns o l i d c o d e s t h ep r o b l e m c he v e r ym - d o m a i nu n i f o r m l yd e n s e ? ”p r o p o s e db yy q g u o ，c m r e i sa n dg t h i e r r i ni n1 9 8 8i ss o l v e d s e c o n d l y , t h ec o n c e p to f - q u a s il e n g t hi sd e f i n e d a n dc a r e f u l l yc h a r a c t e r i z e di ns e m i g r o u p s a n d8v e r ys i m p l en e c e s s a r ya n ds u m c i e n tc o n - d l t i o nf o rac l a s so f s e m i g r o u p sw i t hi - q u a s il e n g t h ，i n c l u d i n gf i n i t e l yg e n e r a t e ds e m l g r o u p s w i t h 【0 - q u a s il e n g t h ，f i n i t e ，r - g r o u p s ，f i n i t en i l - e x t e n s i o n so f f i n i t ei n v e r s es e m i g r o u p s ，t ob e s y n t a c t i ci sg i v e n t h ep a r to f t h i sw o r kc o m p l e t e l ya n s w e r st h ef o l l o w i n gq u e s t i o n s ：h o w t oc h a r a c - t e r i z et h es y n t a c t i cs e m i g r o u p ( m o n o i d ) o ff - d i s j u n c t i v el a n g u a g e s ? ”a n d “w h a t k i n do ff - d i s j u n c t i v ec o n g r u e n c e si ss y n t a c t i c ? ”，w h i c hw e r ep u tf o r w a r da n ds t u d i e db y m a n ya u t h o r s l a s t l y , v a r i o u sk i n d so fl a n g u a g ec l a s s e sa r ei n v o l v e d i nt h i sp a r t ，w ef i r s t g i v es o m eb a s i cc o n c e ! p t sa n dp r o p e r t i e so ns o m ec o n c e r n e dl a n g u a g ec l a s s e sa n ds h o w t h a tt h ea l g e b r a i cc l o s u r ep r o p e r t i e so fl a n g u a g ec l a s s e sa n dm o n o i dc l a s s e sa r ec l o s e l y r e l a t e d t h e n ，v a r i o u sk i n d so fg 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 r es t u d l e ds y s t e m i c a l l y i np a r t i c u l a r ，t h es y n t a c t i cm o n o i dc h a r a c t e r i z a t i o n sa n dah i e r a r c h yo ft h e s ec l a s s e so f l a n g u a g e sa r eg i v e n 。i na d d i t i o n ，ac l a s so fg e n e r a l i z e dr e g u l a rl a n g u a g e sc a l l e dr e l a t i v e l y r e g u l a rl a n g u a g e si ss t u d i e d t h i sc l a s so fl a n g u a g e si s n o to n l yac o m m o ng e n e r a l i z a t i o n o fr e g u l a rl a n g u a g e sa n dt h i nl a n g u a g e s ，b u ta l s oc l o s e l yr e l a t e dt om a n yl a n g u a g ec l a s s e s s u c ha ss o m ek i n d so fg 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 s ，c o d e sa n df d - d o m a i n s i ti sa r e m a r k a b l ec l a s so fl a n g u a g e st ob es t u d i e di nd e t a i l k e yw o r d s ：l a n g u a g e s ，s y n t a c t i cs e m i g r o u p s ( m o n o i d s ) ，f d d o m a i n s ，u n i f o r m l y d e n s el a n g u a g e s ，s o l i dc o d e s ，s e m i g r o u p sw i t h - q u a s il e n g t h ，g 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 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 i i 刖吾 我们所说的语言指的是某个字母表( 或者叫做符号集) 上的一些有限序列组成 的集合对语言的研究是计算机科学中的一个重要内容由于语言理论不仅与理论 计算机科学、代数学、组合学、概率论等一些理论性学科的发展密切相关，而且在 许多新兴的应用性学科如运筹学，控制论，最优化理论、密码学、生物信息学中都 有重要的应用，因此它的发展越来越受到人们的关注 对语言的系统研究始于上世纪初到了上世纪四五十年代，在新崛起的计算机 科学的推动下，有了飞速的发展研究语言最常用的工具是自动机与文法它们都是 表示语言的有效工具最简单的一类自动机就是有限自动机它所能识别的语言叫 做正则语言( r e g u l a rl a n g u a g e s ，有的文献将其翻译为正规语言) 这类语言处于语言 类的c h o m s k y 层次中的最底层我们知道，每个语言都决定了一个句法幺半群( 定 义见1 2 ) 一个语言是正则语言当且仅当其句法幺半群是有限的 语言理论与自动机理论，码论，字的组合学，代数学等学科是紧密联系在一起 的本文主要采用半群代数方法去研究语言，涉及用句法同余与句法幺半群对语言 进行刻画与分类的问题语言的半群理论正是从对正则语言的分类开始的人们用 句法幺半群对语言进行分类的工作可以追溯到经典的s c h f i t z e n b e r g e r 定理1 9 6 6 年，s c h n t z e n b e r g e r 发现一个语言是无星号语言( s t a r - f r e el a n g u a g e s ) 当且仅当其句 法幺半群是有限非周期幺半群( f i n i t ea p e r i o d i cm o n o i d s ) 自从s c h i i t z e n b e r g e r 发 现无星号语言与有限非周期幺半群的这种对应后，许多类似的结果如雨后春笋般呈 现在我们面前例如，分段可测语言( p i e c e w i s et e s t a b l el a n g u a g e s ) 与有限夕一平凡 幺半群相对应( f 5 4 1 ) i 局部可测语言( 1 0 c a l l yt e s t a b l el a n g u a g e s ) 与有限局部半格相 对应( 3 ，3 2 ) 等等1 9 7 6 年，e i l e n b e r g 在他的书【5 】中给出了建立这类对应的一个 指导性的理论框架( 即e i l e n b e r g 对应定理) 后来，在这些结果的基础上，逐渐形成 了语言簇的理论 随着语言理论和半群代数理论的发展，从七十年代初起，一些学者开始用句法 幺半群( 或句法同余) 去定义和研究非正则语言其中石焊然与c m r e i s 提出来 研究的析取语言就是一个典型的代表( 3 8 ，4 4 】) 析取语言类不是作为正则语言类的 推广而提出的，无论在什么字母表上，它与正则语言类都不相交不仅如此，它无论 在定义上还是在性质上都与正则语言有某种对立性从句法刻画的角度来说，走到 了与正则语言类相对的另一个极端有趣的是，当字母表只含一个字母时，一个语 言不是正则的就是析取的( 1 4 4 】) 关于析取语言的理论，从上世纪七十年代到现在， 国内外许多专家学者如石辉然，郭聿琦，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 i v y u ，y s t s a i ，s w j i a n g ，许光午，李廉等做了大量的研究工作，主要参考文献有 【7 ，9 ，1 8 ，1 9 ，2 0 ，3 8 ，4 4 ，4 7 ，4 8 ，4 9 ，5 3 ，5 5 】当字母表舍有至少两个字母时，析取语言 类与正则语言类这两个极端的边界线将不再重合出现了既不析取又不正则的语言 ( 在文f 5 2 l 中称这种语言为中闻语言) 从八十年代中期开始，郭聿琦，c m ，r e i s ，石 婶然，g t h i e r r i n ，a d p a r a d i s 等一些专家对析取语言作了各种推广工作，在析取 语言的这个极端上建立了一个层次结构，开创了语言的广义析取层次的研究主要 的广义析取语言有：f - 析取语言。( 【1 0 】) ，r f - 析取语言( 即相对f _ 析取语言) ( 【1 1 】) ，口新 取语言( 3 4 1 ) 和驴析取语言( 8 1 ) 等 为研究f - 析取语言，郭聿琦，c m r e i s 和g t h i e r r i n 于1 9 8 8 年在f 1 1 1 中提 出了f d 辖区的概念( 见定义2 1 1 ) f d - 辖区可以理解为f 析取语言的检澳4 集，可用 它来检测语言的f - 析取性，例如，本原字集q ，稠密正则语言以及a + 中的双理想都 是f d 辖区( 【1 1 1 ) 类似的概念如析取辖区，稠密辖区，正则辖区曾被石烽然等一些 专家讨论过从文献【1 1 中可以看出，f d 辖区与r f - 析取语言有着密切的联系因此 对f d 辖区的刻画，不仅关系到f 析取语言的研究，而且对于我们研究r f - 析取语言乃 至语言的广义析取层次都有帮助为了刻画f d 辖区，在1 1 1 】中作者提出一致稠密语 言的概念( 见定义2 1 2 ) 由定义可知一致稠密语言一定是f d - 辖区是否f d 一辖区可 用一致稠密性来刻画呢? 郭聿琦等人在此文中提出了如下问题：“是否每一个f d 辖 区都是一致稠密的? ”这个问题在一些文献中被称为g r t 问题1 9 8 9 年，江中豪在 文 1 7 】中曾专门讨论过此问题，给出了这个问题的一个等价描述本文的第2 章专 门对这个问题进行了讨论利用s o l i d 码的理论和一些精细的构造技巧，完全解决了 这个问题 在这个领域中，八十年代末遗留下来的另一个重要的问题是：“如何刻画f - 析取 语言的句法 幺 半群? ”为了解决这个问题，c m r e i s 在他的两篇文章【3 9 】和1 4 0 】 中分别提出了f _ 析取同余和q l - 幺半群的概念，并对其进行了大量刻画我们知道， f 析取语言的句法同余一定是f 析取同余r e i s 用q l 一幺半群对f 析取同余进行了一 个比较清楚的刻画因此对f - 析取语言句法幺半群的刻画即归结为“什么样的f - 析 取同余是句法的? ”在【3 9 1 中，r e i s 证明了可消的f - 析取同余是句法的然而有例 子表明，可消性并不是f 析取同余成为句法同余的必要条件( 1 0 ，3 9 】) 我们在本文 的第3 章中发展了r e i s 关于q 1 幺半群的理论，最终在3 3 中完全解决了这个问 题，给出了判断f _ 析取同余是不是句法同余的一个十分简单的充分必要条件另外， 我们的这个理论不但适用于f 析取语言，而且对q f 析取语言也同样适用因此也一 并解决了关于q f 析取语言句法【幺】半群的刻画问题 随着研究的不断深入，我们需要一些统一的方式去定义和讨论广义析取语言 令c 是一个语言类称a 上的语言l 为c 哳取语言，若每一个兄类都是c 语 v 言f 一析取语言，n d - 析取语言，吐析取语言，正则析取语言，内缀析取语言等大多数 广义析取语言都可以用这种方法来定义这种方法便丁我们对这些广义析取晤言进 行统一刻画和分类例如，我们在4 2 中对各种码类c 决定的c 一析取语言的句法 幺半群进行了统一刻画，利用句法幺半群刻画，我们还在这一节的最后给出了一些 常见的广义析取语言类之间的层次关系( 见定理4 2 2 1 和图4 - 1 ) 前面说过，当字母表只含有一个字母时，一个语言不是正则的就是析取的1 9 8 8 年，郭聿琦，c m r e i s 和g t h i e r r i n 定义了相对析取语言的概念，并证明了它与 r b 析取语言类实际上是一样的( 【1 1 】) 相对析取语言类是一种与正则语言类不交的 广义析取语言类我们在第4 章的最后一节中讨论了一种广义正则语言，称为相对 正则语言这种语言不但是正则语言的一种推广，也是薄语言的一种推广并且有： “在任何有限字母表上，一个语言不是相对正则的就是相对析取的”在这一节中，通 过对相对正则语言的研究，我们发现这类语言与析取语言，码，本原字，f d - 辖区等多 种语言类都有着密切的联系推广了一系列关于析取语育和码论文章中的一些与正 则语言或薄语言相关的重要结论对相对正则语言的研究，实际上使我们找到了一 种能统一处理正则语言和薄语言的方法 v i 第1 章预备知识 在本章中，我们给出在整篇论文中需要经常使用的概念与记号第1 节绘出了 半群代数理论的一些基本概念；第2 节则对我们将用到的语言与码论方面的知识作 了一个简单介绍；在第3 节巾，我们专门对半群r i 的稠密子集进行了讨论，给出了 稠密子集的一些基本性质，这些性质将在本文中经常用到关于半群代数基本理论 的系统介绍可参考h o w i e 的书f 1 4 j 或f 1 6 关于语言学，码论方面的知识，可参考 f 1 ，1 3 ，1 5 ，5 3 1 而l a l l e m e n t 的书f 2 2 1 则包含了许多半群代数理论在语言学及码论 中的应用本文中没有定义的概念与记号都是标准的，都可在这几本书中找到 1 1 半群与幺半群 称二元组( s ，) 为一个半群，若s 是一个非空集合，“”是s 上的一个满足结 合律 ( v a ，b ，c s ) ( a b ) c = a ( b c ) 的二元运算通常称此二元运算为这个半群的乘法运算在不引起混淆时，我们也常 常简称s 为半群，将乘法a b 简记为口6 ，其中口，b s 令s 是一个半群1 s 称为s 的幺元( 或单位元) ，若 ( v s s ) l s = s l = s 0 s 称为s 的零元，若 ( v s s ) 0 s = s o = 0 易证，一个半群至多含有一个幺元( 零元) 称三元组( m ，1 ) ( 或简称m ) 为一个 幺半群，若( ，) 是一个含有幺元1 的半群， 例如，所有正整数( 非负整数) 组成的集合n ( 即) 在通常的整数加法下，形成 一个半群( 幺半群) 我们总是可以用以下方式给一个半群s 添加一个幺元使其成为一个幺半群令 1 芒s ，在s u f l 上规定： ( v s s ) l s = s l = s ， 则s u 1 ) 成为一个幺半群，1 为其幺元定义 。1f s 若s 含有幺元； 。一1s u 1 ) 若s 不含幺元 类似地，可定义 s o = ；u 们，喜；某喜善雯 令a 与b 是半群s 的两个子集我们用a b 表示 0 6 ia a ，b b ) ，称为a 与b 的乘积易见，定义在s 的子集上的这个运算满足结合律从而幂集币( s ) = 2 5 在这个运算下形成半群记 a 1 a ，a 叶1 = a a “，a g = u ，a 劲= l j a ，n i 1 i = li = n 若s 是幺半群，则也有类似的记号 n a o = 1 ) ，a 1 = a a “，a 如= u a ，a h = u a ，礼n o = 0i = r 我们用a - 1 b 和a b _ 1 分别表示s 的子集 z s i 存在口a 使得a x b ) 和 石s i 存在b b 使得x b a ) 另外，a o ) ， a a ， o ) _ 1 a 与a o ) - 1 分别简记为a a ，a a ，a - l a 与a a ，其中 口s 我们常常将单点集与其元素在记号上不加区分，在后文中也就不一一说明 了 称幺半群( g ，- ，1 ) 为一个群，如果关于任意a g ，存在0 7 g ，使得 a a 7 = a 7 a = 1 令( m ，1 ) 为一幺半群，o m 称满足上式条件的元素a 7 为口的群逆元存 在群逆元的元素叫做m 的单位m 的所有单位组成的集合在m 的运算下形成一 个群，称为m 的单位群 半群s 的非空子集t 称为s 的子半群，若t 关于s 的运算封闭若t 在此 运算下形成幺半群( 群) ，则称t 为s 的子幺半群( 子群) 关于任意s 的非空子集 x ，包含x 的所有子半群的交是包含x 的最小子半群，叫做由x 生成的子半群， 记作( x ) 若s = ( x ，则称x 生成s ，或x 是s 的生成元集由一个元素生成 的半群称为单演半群 2 半群s 的非空子集j 称为s 的理想( 左理想，右理想，拟理想) ，若s 儿j j s j ( s j j ，s ，s ，n ，s j ) 易证，s 的任何i 左，右，拟】理想都是s 的子半 群。关于任意s 的非空子集x ，包含x 的所有| 左，右，拟1 理想的交是包含x 的最 小i 左，右，拟 理想，叫做由x 生成的【左，右，拟】理想称一个【左，右，拟】理想j 为 主悻，右，拟】理想，如果，可由s 巾的一个元素生成显然，s 本身一定是s 的一 个【左，右，拟】理想，称为平凡【左，右，拟】理想，而s 的其它i 左，右，拟】理想称为非平 凡【左，右，拟】理想只含有平凡 左，右 理想的半群称为【左，右 单半群易证，只含 有平凡拟理想的半群一定是群 令x 是一个集合称x x 的子集为x 上的二元关系，简称关系。x 上所有 二元关系组成的集合记为劈( x ) 在关系的合成运算 p o 口= ( 。，y ) x x i ( 3 z x ) ( z ，z ) p ，( z ，y ) 叮) 下，留( x ) 形成一个幺半群，其中l x = ( z ，z ) iz x ) 为其幺元，称为相等关系 以下给出一些与二元关系有关的常用概念与记号令p 劈( x 1 ( 1 ) d o m ( p ) = t xl ( j 可x ) ( z ，) p ) ，叫做p 的定义域 ( 2 ) i m ( p ) = = z x i ( j g x ) ( ，卫) p ) ，叫做p 的值域 ( 3 ) p - 1 = ( z ，) l ( g ，z ) p ) ，叫做p 的逆显然有d o m ( p - 1 ) = i r a ( p ) ，i m ( p - 1 ) = d o m ( p ) ( 4 ) p 1 = p ，矿“= p 。矿，n n ；p ”= u 墨i 矿，称为p 的传递闭包 ( 5 ) 关于任意z x ，令：t p = 爹f ( 。，) 舛则。d o m ( p ) 当且仅当x p 0 ( 6 ) 在某些场合我们也将( z ，) p 记为。倒或者z 三y ( 户) 令妒穷( x ) 若关于任意z x ，l 邓_ | = 1 ( j z 妒s1 1 ) ，则称妒为x 上的 变换( 部分变换) x 上所有交换( 部分变换) 的集合记为少( x ) ( 伊少( x ) ) 显然 伊少( x ) 是留( x ) 的子幺半群，矿( x ) 是汐夕( x ) 的子幺半群 称x 上的关系p 为等价关系，如果p 满足自反性( 即i x p ) ，对称性( 即 p 。= 和传递往( 即p 2 力x 上所有等价关系组成的集合记为护( x ) 。 令p 是x 上的一个等价关系，z x 则商集x p = o p io x ) 构成x 的 一个划分称诸z p 为p 等价类，简称p 类集合上的等价关系与该集合e 的划分 之间有着一一对应的关系在此我们就不详述了p 叫做渗透x 的子集厶若l 是 若干俨类的并 x 上的关系s 称为x 上的个偏序，如果s 满足自反性，反对称性( 即 si - 1 - 1 1 x ) 和传递性称( x ，s ) ( 或简称x ) 为偏序集，若为x 上的一个偏 序通常将s - 1 记为令( x ，) 是一个偏序集称茹，”x 为可比较的，如果 口或者z 若x 中任意两个元素都可比较，则称为全序，x 为全序集 3 ( 或链) 称x y 量x 为y 的极小元，如果关于任意y y ，y z 蕴涵着y = z ； 称z 为y 的最小元，如果关于任意y y ，有z y 类似地町定义极大元，最大元 的概念如果x 的任何子集都含有极4 、( 大) 元，则称x 满足极小( 大) 条件满足 极小条件的全序集称为良序集 称半群s 上的关系p 为左相容的，若 ( v n ，b ，c s ) a p b 净c a p c b ； 右相容的，若 ( v a ，b ，c s ) a p b 号a c p b c ； 相容的，若 ( v a ，b ，c ，d s ) a p b ，c p d 辛a c p b d s 卜f 左，右】相容的等价关系称为【左，右 同余易见，p 是s 卜的同余当日仅当p 既 是左同余，又是右同余s 上所有同余组成的集合记为够帆( s ) 若p 是半群s 上的同余，则商集s p 在运算 ( v x ，y s ) x p - y p = ( x y ) p 下形成半群，叫做s 关于p 的商半群 令s 与r 是两个半群称映射妒：s 一丁为s 到丁的同态，如果妒保持运 算，即关于任意a ，b s ，妒( 0 6 ) = 妒( o ) 妒( 6 ) 若妒还是s 到t 的满射( 单射，双射) ， 则称妒为s 到t 的满同态( 单同态，同构) 称s 与t 同构，记为s ! t ，若存在 s 到丁的同构映射从s 到其自身的同态( 同构) 称为自同态( 自同构) 令p 是半群s 上的同余则x z p 足s 到商半群s p 的一个满匠态， 叫做由p 决定的自然同态，记为砂。令妒是半群s 到半群丁的一个例态，则 ( z ，y ) sxs l 。妒= 可妒 是s 上的一个同余，叫做妒的核，记为k e r 妒半群s 的 同余与同态之间通过自然同态与同态核有着相互决定的关系( 同态基本定理) 在本文中我们经常用到两种同余，它们是r e e s 同余与句法同余 令，是半群s 的一个理想则p ，= 1 s u ( i i ) 为s 上的同余，称为兄e e s 同 祭s ? p i 您为r e e 8 商，常筒记为s i 令l 是半群s 的任一子集，x s 定义正关于三的上下文集为 c o a t l ( x ) = ( ( “，u ) s 1 s 1i 乱z l ) 关于l 的句法同余( 或主同余) 兄定义为( ，y ) p l 当且仅当c o n t l ( x ) = c o n t l ( y ) ，即 兄= ( 茁，y ) sxs i ( v u ，”s 1 ) t z 口l 当且仅当u y v l ) 4 我们通常将自然同态硅叫做句法同态，记为饥，将z s 所在的兄一类。凫记为 i x l 工称为s 的析取子集，如果兄= 1 s 类似地，我们可定义主左( 右) 同余蹬 ( p l r ) 例如， 尸= ( z ，y ) s s i ( v u s 1 ) 。l 当且仅当u y l ) 也有相应的左( 右) 析取子集的概念 以下命题是众所周知的 、 命题1 1 1 ( 见【2 2 】) 令l 是半群s 的任一子集则兄( 硝，p 三r ) 是s 上 渗透l 的最大同余( 左同余，右同余) 下面我们列举几类经常用到的半群称半群s 为一个 ( 1 ) 带，若关于任意o s ，口2 = 口； f 2 1 左零半群，若关于任意a ，b s ，n b = n ； ( 3 ) 右零半群，若关于任意a ，b s ，a b = 6 ； ( 4 ) 矩形带，若关于任意n ，b s ，a b a = 口； ( 5 ) 半格，若关于任意d ，b s ，n 2 = a ，a b = b a ； ( 6 ) 6n u l l 半群，若s 含零元0 ，且关于任意a ，b s ，曲= 0 称半群s 中满足a 2 = a 的元素q 为幂等元，用e ( s ) 表示s 中所有幂等元组 成的集合 令s 是个半群在s 上定义等价关系堂，露，夕，冀9 和9 如下： 以6 当且仅当 s 1 a = s 1 b ( n ，b s ) n 露6 当且仅当 a s l = b s l ( a ，b s ) n 6 当且仅当s 1 a s l = s 1 b s l ( d ，b s ) 而j 护：2a 魔，9 = zv 贸，其中v 和 是s 上等价关系格( 芎( s ) ，v ，a ) 上的 两个运算称这五个关系为s 上的g r e e n 关系元素a s 所在的j 矽，魔，夕，p 纩 和9 类分别记为l 。，忍，五，也和z k 称半群s 的元素a 为9 - 月, l , t ，着存在o s 使得o z n = n 记s 的所有正则 元组成的集合为r e g ( s ) 若r e g ( s ) = s ，则称s 为乓别半群a s 称为o s 的逆元，若。口7 0 = o ，a a a = a a 的逆元集记为y ( o ) 则有o r 启g ( s ) 当且仅 当y 8 ) 毋。称s 为完全正则的，若关于任意8 s ，存在s 使得a , t a = 口， 盯：茁d 完全正则的单半群称为完全单半群关于g r e e n 关系和正则半群的基本 理论可参考h o w i e 的书1 1 4 】 5 我们以上定义的子结构，同余，同态等概念可以完全类似地在幺半群或群等其 他代数系统上定义，在此就不再撰述了 在本文中，我们用吲表示集合s 的基数i s i o ) ，而 a l p h ( l ) = u 。e a l p h ( w ) ，其中l a + 令z ，y a 称z 为y 的前缀( 或左因子) ，若存在u a ，使得y = z 对称 地可定义后缀( 或右因子) 的概念称z 为y 的内缀( 或因子) ，若存在对，口a + ，使 得y = 伽 a + 上的关系 p = ( ( 。，y ) a a i ( 3 u a + ) y = z u ) 是的一个偏序，叫做前缀序同样可以定义后缀序s 和内缀序s i 关于自由【幺】半群，我们有 命题1 2 。1 ( 见f 1 4 ，2 2 i ) 令a 是一个字母表，s 是一个半群( 幺半群) ，妒是一 个a 到s 的映射则存在唯一a + ( a ) 到s 的同态妒使得l a = 妒此外，是 满同态当且仅当妒( 五) 生成s 6 通常称一个半群( 幺半群) 为自由的，若其同构于某个a + ( 小) 令s ( m ) 是一个半群( 幺半群) ，a 为s ( m ) 的某个生成元集，妒= l 则由 上述命题，得 推论1 2 2 任何【幺】半群都是某个自由【幺】半群的同态像 称小的子集为a 上的语言令l 是a 上的一个语言，我们用l g ( l ) 与l g ( l ) 分别表示l 中字的最小与最大长度，若l 中的字不存在最大长度，则令幻( 三) = 0 0 幻( l ) o o 的语言叫做有界语言，l g ( l ) = 0 0 的语言叫做无界语言显然，有限语 言( 即i l i 0 0 的语言) 一定是有界语言，如果a 有限，那么有界语言与有限语言 是两个相同的概念 注意1 2 3 以上定义的语言是在自由幺半群上定义的，我们也可在其他代数系 统的自由对象上定义语言通常称自由幺半群上的语言为+ 一语言，而称自由半群上 的语言为+ 一语言在某些场合( 如在讨论语言簇时) ，区别 语言与+ 一语言是有必 要的在本文中，如不加特别说明，我们通常讨论的是+ 一语言，而相应的关于+ - 语 言的理论可以类似地得到 令l 为a 上的一个+ 语言( + 语言) 称a + 兄( 印吃) 为l 的句法半群 ( 句法幺半群) ，记为s ( l ) ( m ( l ) ) 称一个半群( 幺半群) s 为句法半群( 句法幺半 群) ，如果s 同构于某个+ 一语言( + - 语言) 的句法半群( 句法幺半群) 命题1 2 4 ( 见【2 2 1 ) 【幺】半群s 是句法 幺】半群的充要条件是s 舍有析取子 集 称a 上的字w 为本原字，如果由w = u n ，u a ，n n 可得几= 1 a e 所 有本原字组成的集合记为q ( a ) ，或简记为口易证，关于任意w a + ，存在唯一的 札q ，凡n ，使得w = u “上式- i 一的u 称为w 的本原根，记为r ( 叫) 关于任意 工a + ，记r ( l ) = r ( 伽) i w l ) a 上的字w 叫做无平方字( 无立方字) ，若叫没有平方( 立方) 因子，即关于任 意钍a + ，u 2 ( 缸3 ) 不是w 的因子关于无平方字和无立方字，有如下著名结论： 命题1 2 5 ( 见【2 6 0 在至少含有两个字母的字母表上有无限多个无立方字i 在 至少含有三个字母的字母表上有无限多个无平方字 称非空语言l a + 为a 上的一个码，若由 x l x 2 x m = 掣l 钝， 而，珊l ，i = 1 ，2 ，m ，j = 1 ，2 ，n ， 7 可得 仇= n ，z i = 玑，i = 1 ，2 ，n 称工为前缀码( 后缀码，内缀码) 若l 中任何一个字都不是另一个字的前缀( 后缀， 内缀) 既是前缀码又是后缀码的语言称为双缀码我们将a 上所有码，前级码，后 缀码，双缀码和内缀码组成的集合分别记为c ( a ) ，p ( a ) ，s ( a ) ，b ( a ) 和i ( a ) 我 们一般只在至少含有两个字母的字母表上讨论码，冈为在只含一个字母的字母表a 上，一个语言是码当且仅当占是a + 中的单点集易证，若l a l 2 ，则有 i ( 岖m ) 裂c c ( a ) 注意1 2 6 方便起见，我们在讨论+ 语言时，也把单点集 1 ) 当作【前缀，后缀， 双码，内缀】码从而前缀码等也可用以下方式定义：非空语言l 小叫做 ( 1 ) 前缀码，若( v u ，o a + ) z ，z t l 垮u = l ； ( 2 ) 后缀码，若( 地，a ) z ，钾l 号缸= l ； ( 3 ) 双缀码， 若( v u ，z a + ) “x ，z 札l = 让= 1 ”& “z ，札z l 辛i , = 1 ” ( 4 ) 内缀码，若( v u ，u ，z a + ) o ，u z l 号u = = 1 易见，这种定义只比前面的定义多了那个单点集1 1 正则语言是语言学中的一个十分重要的研究对象它有多种不同的等价定义 我们给出其中的一种：称有限字母表上的一个语言为正刘语言，着其句法幺半群为 有限幺半群 1 3 半群中的稠密子集 半群s 的子集三叫做s 的稠密子集，如果关于任意w s ，s 1 w s lnl 0 。 自r e e l 半群中的稠密子集叫做稠密语言若l s 生成的子半群在s 中稠密，则 称l 是s 的完全子集有时候，我们也称半群中的非稠密子集为薄的若f z ) 在半 群s 中稠密，则称z 为s 的一个稠密元 下面的命题是关于稠密子集的一些基本性质我们在本文的许多地方都会用到 这些性质 命题1 3 1 令s 是一个半群，x ，y s 则 ( 1 ) s 在s 申稠密，d 在s 中非稠密j ( 2 ) 若x 在s 中稠密，y x ，则y 在s 中稠密 8 ( 3 ) x u y 在s 中稠密当且仅当x 与y 至少有一个在s 中稠密； ( 4 ) x 与其补集至少有一个是稠密的j ( 5 ) 若x 与y 非空且至少有一个在s 中稠密，则x y 在s 稠密i ( 6 ) s 中的稠密子集与理想的交还是稠密的因此，任何理想的补集都是薄的 证明( 1 ) 和( 2 ) 由稠密子集的定义直接可得 ( 3 ) 若x 或y 稠密，则由( 2 ) ，xu y 也稠密反之，若x 和y 都不稠密，则 存在z ，y s 使得s 1 x s ln x = d ，s 1 y s la y = 0 从而s 1 x y s ln ( x u y ) = 0 即x u y 是薄的 ( 4 ) 是( 1 ) 和( 3 ) 的直接推论 ( 5 ) 不失一般性，假设x 是稠密的则关于任意x s ，s 1 x s ln x 0 由于 y 非空，我们有 s l z s ln x y ( s 1 x s ln x ) r o 因此x y 是稠密的 ( 6 ) 令d 是s 的一个稠密子集，是s 的一个理想则关于任意z s ，y j ， 存在牡， s 1 使得u x y v d 而显然有u x y v i ，凼此u x y v d n i 即d n ， 是s 的一个稠密子集 口 命题1 3 2 令s 是一个含有零元0 的半群，l s 剧 ( 1 ) l 稠密当且仅当0 l j ( 2 ) l 稠密当且仅当l 。是薄的j ( 3 ) 若s 中含有析取子集，则s 既舍有稠密析取子集，也含有薄析取子集 证明( 1 ) 由于0 显然是s 的一个稠密元，充分性是命题1 3 1 的直接推论 反之，设0 岳三则s 1 0 s 1 n l = d 因此l 不稠密 ( 2 ) 可由( 1 ) 直接推出 ( 3 ) 因析取子集的补集还是析取的，故由( 2 ) 可得 口 命题1 3 3 令s 是一个不舍零元的半群则s 的任何析取子集都是稠密的 证明假设三是s 中的析取子集但不稠密则存在叫s 使得s 1 w s l a l = 0 由于关于任意u ， s 1 ，有s 1 u w v s l s 1 w s l ，因此，s 1 u w v s lnl = d 从而 s 1 w s l l l = ) 这说明叫是s 的零元，矛盾 口 令工是半群s 的任一子集则 w ( l ) = w s ( l ) = 嚣s i s l 。s l n l = 0 ) 9 称为l 的剩余子集显然，l 在s 中稠密当且仅当w ( l ) = o 若w ( l ) 非空，则 其既是s 的一个理想，也是s 的一个兄类从而是s p l 的零元进一步，我l f j 有以下命题 命题1 3 4 关于半群s 的任意子集l 下列各款等价? ( 1 ) l 与己。都稠密j ( 2 ) w ( l ) = w ( l 。) = d i ( 3 ) s 屁不含零元i ( 4 ) s 中或者不舍有稠密兄一类，或者舍有至少两个稠密r 一类 证明( 1 ) 与( 2 ) 的等份性由w ( l ) 的定义直接得 ( 2 ) 辛( 3 ) 若z 是彤r 的零元，则s 1 z s l z 令枷z 若w 隹l ，则由 于z 是s 的个兄类，且p l 渗透l 有znl = 0 ，从而s 1 w s lnl = 0 因 此w w 仁) ，这与w ( l ) = 0 矛盾同理，若w 隹l c ，则有w w ( l c ) ，这与 w ( l c ) = o 矛盾因此s 屁不含零元 ( 3 ) = 争( 4 ) 。假设s 烩好含有一个稠密的屁类z = 捌，则关于任意翟只 有w z f w z l ，z w 【z w t , 由命题1 3 1 ( 5 ) 可知，w z ( z w ) 在s 中稠密，从而 z l ( 【；训 l ) 也在s 中稠密因此【w z l = z w z , = z 这说明z = 【。 l 是剐r 的零元， ( 4 ) ：争( 2 ) 若w ( l ) d ，则w ( l ) 是一个稠密的p l 一类又因此时w ( l ) 是 s 的一个理想，由命题1 3 1 ( 6 ) ，w ( l ) 。是薄的因此s 仅含有一个稠密的兄一类， 矛盾同理，w ( l 。) 口也是不可能的， 口 命题1 3 5 令妒是半群s 到