（基础数学专业论文）格值文法及其语言.pdf

格值文法及其语言 盛莉 摘要本文研究的主要内容是格值文法及其语言李永明教授在文【1 9 】中建 立了一个新的模糊自动机模型，即格值自动机，在一个比以往研究的模糊自动机 更广的框架一格半群意义下，来研究自动机理论文f l9 中已经证明对于格值 语言，不确定型格值自动机( l a ) 比确定型格值自动机( d l a ) 识别语言的能力更 强，并且从层次结构上来讲。格值自动机比一般模糊自动机能识别更广泛的模糊 语言而在经典自动机与一般模糊自动机理论中，有一个重要的结论就是文法生 成的语言与自动机识别的语言等价。既然在格半群意义下d l a 与删不等价，我 们自然关心的问题就是d l a 与五a 识别的语言分别可以用怎样的文法来刻画 从这个问题出发，本文主要探讨了格值正则文法的结构，格值自动机与格值正则 文法的等价关系，格值正则语言的性质，格值上下文无关文法及其语言的性质等 问题 本文共分四章，第一章主要回顾了经典自动机与形式语言的相关知识，包括 经典有限自动机的定义，文法的定义与分类以及经典自动机理论中几个重要结 论 第二章，在自动机理论中，基于格半群，引入格值自动机及其识别的语言的 定义，格值正则文法及其产生的语言的定义，给出格值正则文法的分类，找出了 用格值正则文法刻殛确定型格值自动机的形式主要得出如下结论： ( 1 ) 格值正则文法与格值自动机等价； ( 2 ) 确定格值正则文法与确定型格值自动机等价 第三章：在格值文法的框架下重新给出了格值正则语言的各种运算对应的文 法的构造从文法的角度来研究语言的性质，讨论了格值正则语言关于正剥运算 的封闭性及其条件主要得出如下结论z ( 1 ) 格值正则语言在并，连接，k l e e n e 闭包和数乘运算下封闭； ( 2 ) 格值正则语言关于广义交运算，反转运算封闭的充要条件是运算满足 交换律 ( 3 ) 确定格值正则语言在并，交，广义交，连接，反转及数乘运算下封闭 ( 4 ) 确定格值正则文法与格值正则文法等价的充要条件是由格二的任意有限 子集l 7 生成的( l ，v ) 的子代数是有限的 第匹章：继续在格半群意义下，介绍格值上下文无关文法，给出了将格值上 下文无关文法分别转换成与其等价的c h o m s k y 范式文法和g r e i b a c h 范式文法的 算法，最后讨论了格值下文无关语言的性质 关键词：模糊自动机模糊正则文法模糊正则语言格半群正则运算 2 g r a m m a r sw i t ht r u t hv a l u e si nl a t t i c e o r d e r e dm o n o i d a n dt h e i rl a n g u a g e s s h e n g l i a b s t r a c ti nt h i sa r t i c l e ，w em a i n l ys t u d i e dl a t t i c e - v a l u e dg r a m m a r s ( l g ) a n dt h e i r l a n g u a g e s i n 【1 9 1 ，l ih a ss t u d i e df u z z ya u t o m a t at h e o r yw i t ht r u t hv a l u e si nt h em o r e g e n e r a ls t r u c t u r e ：l a t t i c e - o r d e r e dm o n o i d ，a n ds e tt h ef o r m a lm o d e l so fc o m p u t i n gw i t h w o r d so nt h el a t t i c e - v a l u e df u z z ya u t o m a t a i t ss h o w nt h a tl ac a nr e c o n g n i z em o r e l a n g u a g e st h a nr e g u l a rl a n g u a g e sf r o m t h e p o i to f v i e wo f l e v e ls t r u c t u r e ，a n dt h u sh a v et h e m o r e p o w e r t or e c o n g n i z e f u z z yl a n g u a g e st h a nc l a s s i c a lf u z z ya u t o m a t a a sw e l l - k n o w ni n t h et h e o r yo fc l a s s i c a la u t o m a t aa n d g e n e r a lf u z z ya u t o m a t a ，i t sa ni m p o r t a n tc o n c l u s i o n t h a tr e g u l a rg r a m m a r sa n df i n i t ea u t o m a t aa r ee q u i v a l e n tw h e ni tc o m e st ot h e r e c o g n i t i o n s o f l a n g u a g e s n o wt h a td l a a n dl aa r en o t e q u i v a l e n ti nt h er e c o g n i z i n gf u z z yl a n g u a g e s ， n a t u r a l l y w es h a l lc o n s i d e rh o wt oc h a r a c t e r i z et h e l a n g u a g e sr e c o n g n i z e db yd l a a n dl a w i t hl a t t i c e - v a l u e dg r a m m a r s ，r e s p e c t i v e l y c o n c e r n i n gw i t ht h i sp r o b l e m ，w es t u d yt i l e s t r u c t u r eo fl a t t i c e - v a l u e dr e g u l a rg r a m m a r s ( l r g ) a n dt h ee q u i v a l e n c eb e t w e e nl a a n d 五船，s o m ep r o p e r t i e so fl a t t i c e - v a l u e dr e g u l a rl a n g n a g e s ( l r l ) ，l a t t i c e - v a l u e d ( l v a l u e d ) c o n t e x t f r e eg r a m m a r ( l c f g ) ，t h ep r o p e r t i e so fl - v a l u e dc o n t e x t f r e el a n g u a g e s ( l c f l ) a r ea l s oc o n s i d e r d e d w ed i v i d et h ea r t i c l ei n t of i v ec h a p t e r s ，t h ef i r s tc h a p t e ri s p r e l i m i n a r l i e s ，i nw h i c h t h ec l a s s i c a la u t o m a t a t h e o r ya n df o r m a lg r a m m a rt h e o r ya r er e v i e w e d i nt h es e c o n dc h a p t e r ，l - v a l u e da u t o m a t aa n dl v a l u e dg r a m m a r sa r ei n t r o d u c e d a s p e c i a lk i n do fg r a m m a r w h i c ht oc h a r a t e r i z et h el a n g u a g e sg e n e r a t e d b yd l a a r eg i v e n ， a n dt h ee q u i v a l e n c eb e t w e e nl aa n dl r g ，d l aa n dd e t e r m i n i s t i cl - v a l u e d r e g u l a r g r a m m a r s ( d l r g ) a r e a l s os h o w n t h em a i nr e s u l t sa r ea sf o l l o w i n g ， ( 1 ) l aa n dl r g a x ee q u i v a l e n ti nt h er e c o g n i z i n gf u z z yl a n g u a g e s ； ( 2 ) d l aa n dd l r g a r ee q u i v a l e n ti nt h er e c o g n i z i n gf u z z yl a n g u a g e s i nt h et h i r dc h a p t e r ，f r o mt h ev i e w p o i n to fg r a m m a r ，w es t u d i e dt h ep r o p e r t yo f l v a l u e dr e g u l a rl a n g u a g e s ( l r l ) t h ec l o s e n e s so ff a m i l yo f 工r la n dd e r e r m i n i s t i cl v a l u e dr e g u l a rl a n g u a g e s ( d l r l ) u n d e r r e g u l a ro p e r a t i o n sa r er e s p e c t i v e l yd i s c u s s e d i n t h e e n d ，s o m e s u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n st og u a r a n t e et h el r g a n dd l r g b e i n g e q u i v a l e n ta r eg i v e n t h em a i nr e s u l t sa r ea sf o l l o w i n g ， ( 1 ) t h ef a m i l y o fl r li sc l o s e du n d e rt h e o p e r a t i o n so f j o i n ，c o n c a t e n a t i o n ，t h ek l e e n e 3 c l o s u r ea n dt h es c a l a ro p e r a t i o n s f 2 ) t h ef a m i l yo fl r l i sc l o s e du n d e rt h eo p e r a t i o n so fg e n e r a l i z e dm e e t r e v e r s a l o p e r a t i o n si f f s a t i s f i e sc o m m u t a t i v e l a w s ( 3 ) t h ef a m i l yo fd l r l i sc l o s e du n d e rt h eo p e r a t i o n so f j o i n ，c o n c a t e n a t i o n ，m e e t ， r e v e r s a la n ds c a l a ro p e r a t i o n s ， ( 4 ) f o ra n yl r g ，t h e r e i sa ne q u i v a l e n td l r g 册t h el a t t i c els a t i s f i e st h ef o l l o w i n g c o n d i t i o n ，f o ra n y f i n i t es u b s e tl o fl ，t h es u b a l g e b r a o f ( l ，v ) g e n e r a t e db yl i sf i n i t e i nt h ef o r t hc h a p t e r ，a n o t h e rn e wt y p eo f g r a m m a r c a l l e dl - v a l u e dc o n t e x t - f r e e g r a m m a r ( l c f g ) a r ei n t r o d u c e d w eg i v et h ea l g o r i t h m sw h i c ht ot r a n s f e rt h el c f g i n t oc h o m s k yn o r ma n dg r e i b a c hn o r m ，r e s p e c t i v e l y t h ep r o p e r t yo fl v a l u e dc o n t e x t f r e el a n g u a g e sa r ea l s oi n c l u d e d k e y w o r d s ：f u z z yf i n i t ea u t o m a t af u z z yr e g u l a rg r a m m a r f u z z yr e g u l a rl a n - g u a g e l a t t i c e - o r d e r e dm o n o i d r e g u l a ro p e r a t i o n s 4 学位论文独创性声明 y7 2 8 5 8 8 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人 已经发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均 已在文中作了明确说明并表示谢意。 作者签名：日期： 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西 师范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文 的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆、院系资料室被查阅：有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版- 作者签名： 日期： 前言 语言学家乔姆斯基( c h o m s k y ) 最初从产生语言的角度研究语言，1 9 5 9 年， 乔姆斯基根据产生语言的文法的特性将语言划分成了三大类克林( k l e e n e ) 在 1 9 5 1 1 9 5 6 年间，从识别的角度研究语言，给出了语言的另一种描述克林在研究 神经细胞中建立自动机，他用这种自动机来识别语畜；对于按照一定的规则构造 的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的 所有句子组成 1 9 5 9 年，乔姆斯基通过深入研究，将他本人的研究成果与克林的研究成果结 合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且 证明了文法与自动机的等价性此时形式语言才真正诞生并被置于数学的光芒 下 1 9 6 5 年l a ，z a d e h 教授创造性地提出模糊集理论( 【9 】) ，为研究人类智能提供 数学工具，之后，在计算机科学中，作为一般自动机的推广，开始了利用模糊集 的方法研究自动机理论除了在控制中经常采用外，其与形式语言和自动机理论 的结合，使得形式语言和自动机理论从此进入到一个全新的阶段既而在1 9 6 9 年e t l e e 和l a z a d e h 提出了f u z z y 有限状态自动机和f u z z y 正则语言的概念， 2 0 世纪7 0 年代g a i n e s 和k o h o u t 讨论了模糊自动机的逻辑基础( 4 2 ) ，s a n t o s 进 一步深入研究了模糊自动机识别的模糊语言及在各种算子下的封闭性，讨论了 由模糊文法生成的语言的性质( 【3 4 ，3 5 ，3 6 ) 在模糊语言的代数结构上，沈继中 ( 3 7 】) ，a s v e l d ( t ) 讨论了模糊语言中各种算子的性质，如并，连接，k l e e n e 闭包， 与正则语言的交及各种模糊置换 最近邱道文与a s v e l d 等又提出了基于剩余类逻辑的自动机理论( 【3 7 ，1 1 ，1 2 ) ， 从而提供了多值逻辑意义下研究自动机理论的方法正如文 10 所说，以往的模 糊自动机理论只是对经典问题的较初步的模糊化，因而缺乏层次结构为解决这 个问题，李永明教授在更广酌框架下，格半群意义下，来研究自动机理论，把基 于词的计算的模型建立建立在更广泛的格值自动机理论之上，他的研究结果表明 了格值自动机和通常的自动机及模糊自动机有许多不相同的地方，而且它能识别 更广泛的形式语言与模糊语言，这也构成格值自动机理论本身的特色 我们知道在经典自动机理论中，以下表示一个语言l 的方法是等价的： ( 1 ) l 棱一个确定型自动机接受( 或识别) ； ( 2 ) l 被一个不确定型自动机接受； ( 3 ) l 由正则表达式生成； ( 4 ) l 由一个正则文法生成 同样的结论对真值集为 0 ，1 】，运算为m a x - m i n 的模糊自动机也是成立的对于更 广意义下的模糊语言，即格值语言，李永明教授在文【1 9 中已经证明了在格半群 意义下，( 1 ) 与( 2 ) 是不等价的，则我们关心的另外的问题就是，给出确定型与不 确定型格值自动机的正则表达式与正则文法的结构其中正则表达式的问题已在 文 2 0 中解决，而本文的目的是研究正则文法的结构，找出分别与( 1 ) ，( 2 ) 等价的 格值文法的形式，并讨论正则语言的性质 本文结构安排如下，第一章先回顾了经典自动机的相关知识，第二章引入了 格值自动机和格值文法的定义，分别找出了与确定型和非确定型格值自动机识别 的语言对应的格值文法，并证明了工a 与l r g ，d l a 与d l r g 的等价性第三章 从文法的角度研究了格值语言的性质，包括d l r l 与l r l 在正则运算下的封闭 性，l r g 与d l r g 等价的充要条件最后一章介绍了格值上下文无关文法 本文的研究结果也表明了由于取值域由区间 0 ，1 l 扩展成格半群，格值文法与 以往研究的一般模糊文法有许多不同之处，格值语言的性质也与它取值的格半群 的代数性质密切相关，这也构成了格值自动机与格值文法理论的自身特色 2 第一章经典自动机与形式语言知识回顾 1 1 引言 形式语言与自动机理论给出了对问题进行抽象和形式化表示的模型，并且通 过研究这些模型的性质及其变化方法来对这些问题进行讨论，因而自动机理论与 形式语言在计算机科学的文本处理、编译程序、硬件设计、程序设计语言与人工 智能等应用领域发挥着重要作用1 9 5 9 年，乔姆斯基从语言产生的角度，按一定 规则定义文法产生语言，克林从语言识别的角度，利用自动机识别语言，并证明 了文法与自动机的等价性形式语言出现之后，很快就在计算机技术领域找到了 应用后来人们又将该文法用到了模式匹配、模型化处理等方面，这些都是算法 描述和分析、计算复杂性理论、可计算性理论等研究的基础本章的目的是简单 回顾关于经典自动机与形式语言知识，介绍经典自动机理论中一些重要结论，同 时也方便我们在后面章节中研究模糊自动机与文法时有一个参照和比较 1 2 预备知识 定义1 2 1 字母表( a l p h a b e t ) 是一个非空有穷集合，字母表中的元素称为该字 母表的一个字母，也可叫做符号或者字符 定义1 2 2 设是一个字母表，e 的正闭包： + = e u 2u 3ue 4u e 的克林闭包：e + = o u e + = o u u e 2 u e 3 u 定义1 2 3 设是一个字母表，忱e ，z 叫做上的一个句子句子还可 以称为字，( 字符、符号) 行，串 定义1 2 4 设e 是一个字母表，v x e ，句子z 中字符出现的总个数叫做该 句子的长度，记作阱长度为0 的字符串叫做空句子，记为a 在计算理论中，对象是语言，工具包括为处理语言专门设计的运算，定义语 言的3 种运算，称作正则运算，并且使用这些运算来研究正则语言的性质 定义1 2 5 设a ，b 是两个语言，定义正则运算并、连接和星号( 克林闭包) 如 下： 并： u b = $ | 。a 或x b ) 连接：ao b = z y i z a j l y b ) 星号：a = l z 2 x k l k2o 且每一个戤a ) 3 1 3 经典自动机介绍 1 3 1 确定的有穷态自动机的形式定义 定义1 3 1 有穷状态自动机( f i n i t ea u t o m a t o n ，f a ) m 是一个五元组 m = ( x ，uj ，。o ，f ) 其中， x ：状态的非空有穷集合，比x ，。称为m 的一个状态 u ：输入字母表，输入字符串都是v 上的字符串 d ：状态转移函数，d ：x u + x 对v ( 。，o ) x 以6 ( z ，n ) = 一表示m 在 状态z 读入字符m 将状态变成z ，并将读头向右移动一个带方格而指向输入字符 串的下一个字符 z o ：m 的开始状态( i n i t i a ls t a t e ) ，。o x f ：m 的终止状态( f i n a ls t a t e ) 集合，f 曼x ，v z 只z 称为m 的终止状态( 或 接受状态) 我们定义f a 的目的是用它来识别语言，所以我们需要将6 的定义域从x u 扩充到x u + 上，可得如下扩张映射，对任意的z x ，口u + ，a u ： ( 1 ) 6 + ( ，a ) = z ，这里a 表示空串； ( 2 ) 5 ( ，o a ) = 6 ( 扩( z ，口) ，口) 定义1 3 2 如果对于任意的z x ，a 阢6 ( 毛a ) 均有确定的值，我们将这种 f a 称为确定的有穷状态自动机( d e t e r m i n i s t i c f i n i t ea u t o m a t o n ，d f a ) 下面我们可以得到f a 接受的语言的定义： 定义1 3 3 设m = ( x ，以d ，, t o ，f ) 是一个f a ，对于v 8 u + ，如果6 ( a o ，口) f ， 则称口被m 接受；如果6 ( 。o ，日) g f ，则称m 不接受口 l ( m ) = o l e u 且5 ( x o ，口) f ) 称为由m 接受( 识别) 的语言 1 3 2 非确定的有穷态自动机的形式定义 定义1 3 4 不确定的有穷状态自动机( n o n - d e t e r m i n i s t i c f i n i t ea u t o m a t a o n ，n f a ) m 是一个五元组； 4 m = ( x ，以d ，x o ，f ) 其中x ，阢z o ，f 的意义同d f a j 称为状态转移函数，6 ：x u 2 x 对v ( x ，o ) x ud ( 。，a ) = y l ，y 2 ，) 表示m 在状态。读入字符o ，可以选择地将状态变成g l ，y 2 ，或者 并将读头向右移动一个带方格而指向输入字符串的下一个字符 在n f a 中，我们同样将6 扩充为扩：x u + - 2 x 对任意的。x ，p u + a 矿： ( 1 ) 6 ( z ，a ) = 。； ( 2 ) 6 + ( $ ，o a ) = yr 3 r d + ( 。，口) ，使得y j ( r n ) ) 定义1 3 5 设m = ( x ，u , g , x o ，f ) 是一个n f a 对于w u 。：如果d ( 蜘，o ) n f o ，则称x 被m 接受；如果6 ( x o ，口) f 3 f = o ，则称m 不接受8 l ( m ) = o l o u 且d ( 。o ，p ) n f 0 ) 称为由m 接受( 识别) 的语言 引理1 , 3 1n f a 与d f a 等价 证明参见文献【2 3 】定理3 - 1 5 1 4 形式语言和文法 1 4 1 文法及其生成的语言 定义1 4 1 文法( g r a m m a r ) g 是一个四元组 g = ( n ，t ，p ，s ) 其中， ：变量( v a r i a b l e ) 的非空有限集v u v ，u 叫做一个语法变量，也叫非终止 符号( n o n t e r m i n a l ) t ：终止符( t e r m i n a l ) 的非空有限集v a t ，a 叫做终止符，且n t = 0 p ：产生式( p r o d u c t i o n ) 的非空有穷集合p 中的元素均具有形式“- u ，称 为产生式，读作u 定义为”其中“( n u t ) + 且u 中至少有中的一个元素出 现， ( n u t ) ，u 称为产生式u - 口的左部， 称为产生式“_ ”的右部 5 s ：s n ，文法g 的开始符号( s t a r ts y m b 0 1 ) 例1 4 1 以下四元组都是文法 ( 1 ) ( a ) ， o ，1 ， a _ 叭， _ o a l ，a _ + 1 a 0 ，a ) ( 2 ) ( 研， n 1 6 ) ， s _ + a a s ，s 叶b b s ，s a a ，s _ b b ，s ) ( 3 ) ( 只a ，b ) ， n ，b ，榉) ，( s - a b ，s _ a b # ，a _ a a a ，a b - + a b b ，b - 存口，s ) 定义1 4 2 设g = ( n ，tp s ) 是一个文法，如果n _ ：p o t ，卢( n u t ) + ，则 称卢在g 中直接推导出a u 卢，记做a u 3 号g 一卢，读作卢在文法g 中直接推导 出一卢在不特别强调推导的直接性时“直接推导”可以简称为推导( d e r i v a t i o n ) ， 有时也称推导为派生与之相对应，也可以称删卢在文法g 中直接归约成a “口 在不特别强调归约的直接性时“直接归约”可以简称为归约( r e d u c t i o n ) 口： + 卢表示a 在g 中经过至少一步推导出卢；a 等卢表示。在g 中经过若 干步推导出芦 定义1 4 3 设文法g = ( n ，t ，p i s ) ，则称 l ( g ) = uj “j t + 且s = + u ) 为文法g 产生的语言枇三( g ) ，u 称为g 产生的一个句子 定义1 4 4 设有两个文法g 1 和g 2 ，如果l ( g 1 ) = l ( c 2 ) ，则称g 1 与g 2 等价 ( e q u i v a l e n c e ) 乔姆斯基( c h o m s k y ) 根据产生式的形式，将文法分成4 类，称为乔姆斯基体 系： 定义1 4 5 设文法g = ( t ，p 1 s ) ，则 ( 1 ) g 叫做0 型文法( t y p e0g r a m m a r ) 或短语结构文法对应地，l ( g ) 叫做0 型语言或短语结构语言 ( 2 ) 如果对于v u _ p ，均有川i “l 成立，则称g 为1 型文法( t y p e 1 g r a m m a r ) 或上下文有关文法( c o n t e x ts e n s i t i v eg r a m m a r ，c s g ) 对应地，l ( g ) 叫做 l 型语言或上下文有关语言 ( 3 ) 如果对于v u _ - d p ，均有i u l 并且u n 成立，则称g 为2 型文法 ( t y p e2g r a m m a r ) 或上下文无关文法( c o n t e x tf r e eg r a m m a r ，c f g ) 对应地，l ( g ) 叫 做2 型语言或上下文无关语言 ( 4 ) 如果对于u _ ”p 】u - + 口均具有形式 a _ + 口或a - a b 6 其中a ，b n ，n t ，则称g 为3 型文法( t y p e3g r a m m a r ) ，也可称为正则文法 ( r e g u l a rg r a m m a r ，a g ) 对应地，l ( a ) 叫做3 型语言或正则语言 1 _ 4 2 正则文法与f a 等价 引理1 _ 4 1f a 与正则文法等价 证明参见文献【2 3 】推论3 - 1 ，定理3 - 3 和定理3 - 4 1 4 3 正则语官的封闭性 本节讨论冗l 对有关运算的封闭性 定义1 4 6 如果任意的、属于某一语言类的语言在某一特定运算下所得结果 仍然是该类语言，则称该语言类对此运算是封闭的，并称该语言类对此运算具有 封闭性 定理1 4 1 r l 在并、乘积、闭包运算下是封闭的 定理1 4 2r l 在交运算下是封闭的 7 第二章格值自动机和格值正则文法 2 1引言 在经典自动机理论中，有几个重要的等价关系：d f a 与n f a 等价，f a 与 r g 等价文【1 9 1 中已经证明。在格半群意义下，d f a 与n f a 并不一定等价，那 么我们自然要关心的问题就是分别该用怎样的文法去刻画格半群意义下的d f a 与n f a ，以找到各自等价的正则文法，本章主要来解决这个问题 2 2基本概念 2 2 1 格半群 定义2 2 1 设工为格，v ，a 为上确界与下确界运算。0 ，1 分别为最小元与最 大元，为l 上的二元运算( 半群运算) ，且( 厶，e ) 为有单位元e l 的半群， 若满足 ( 1 ) v a l ，口0 = 0 o = 0 ， ( 2 ) v a ，b ，c l ，o ( b vc ) = ( n b ) v ( o c ) 及( 6 vc ) o = ( b n ) v ( c 口) 则称五为格半群 当我们谈及格半群时，我们主要关心它的乘法运算与有限上确界运算v ， 而不关心其他运算，因此格半群一般记为( 三，v ) 以下谈及格半群( l ，v ) 的子 代数l 1 时，是指l l l 且l 1 关于乘法运算与有限上确界运算封闭l 。不必关 于下确界运算封闭，因面不必是格。 下面我们给出一些格半群的例子 例2 2 1 ( 1 ) 设( l ，a ，v ) 为分配格，取= a ，则l 成为格半群，单位元为l _ ( 2 ) 设( l ，v ) 为格半群，单位元为e ，以l ( n ) 表示取值于二的n x n 维矩阵，其 上的乘法运算( 记为o ) 规定为矩阵的s u p 一合成；而v 为对应元索在上中的v ，即 设a = 陋玎) ，b = ( b i j ) ，则a o b = g = ( 叼) q j = v k = l ( a l k b k j ) ，而a v b = d = ( d i j ) ， d 玎= a q v b i j 则仁( n ) ，o ，v ) 为格半群，单位元为e = d i a g ( e ，e ，e ) 即主对角线 上元素为e 的对角矩阵二( n ) 上的乘法运算一般不可换，即使工上的乘法运算 是可换的 ( 3 ) 如果为单位区间 0 ，1 】上的t - 模，则( 【0 1 】，v ) 为可换的格半群。单位 元为e = 1 8 ( 4 ) q u a n t a l e 的例子及其应用见文献【1 4 ，1 5 ，1 6 ，1 7 ，3 z ( 5 ) 令l = o 删，v 为数的取大运算，为数的乘法运算。即 ro b ，o ，b 0 0 o b = 0 ， o = 0 或b = 0 【0 0 ，o 0 ，6 = 。或o = 0 0 ，b 0 则( l ，v ) 为可换的q u m a t a l e ，单位元为1 ，最大元为。 ( 6 ) 完备剩余格是一种特别的q u a n t a l e ，其中的乘法运算是可换的，且单位元 就是最大元，参见【1 ，4 1 】i 以下我们总是假设工为格半群 2 2 。2 格值自动机及其识别的语言 定义2 2 。2格值自动机( 记为工a ) 是五元对m = ( x ，弘最印，t t l ) ，其中，= u l ，“2 ，t 。) 为输入集合，x = 扎z 2 ，z 。) 为状态集合，6 ：x u - f ) 为模糊状态转移函数印，a t f ( x ) 分别为模糊初始状态与模糊接受状态 d ( z ，“) ( ) 表示在状态z ，输入字符u 后状态转移到掣的隶属度，以下为简单记 d ( z ，“) ( y ) 圭6 ( z ，u ，y ) 用f 1 9 】的方法，d 还可从一个输入符号推广到输入字符串 口u + = ( 口：口= 钍l l t 2 t 七，z 正1 ，u 2 ，- ，t 以岛o 上u + 为由u 生成的自由幺半群，u + 中的元称为串，乘法运算为串的连接， 单位元为空串，记为a 可得到如下扩张映射矿 ( i ) v y x ，； 知= z ，贝i i 扩( z ，a ，) = e ，否则5 + ( 。，a ，可) = 0 ( i i ) v 8 u ，u 阢6 ( 茁，口u ，y ) = v ：e x 6 。( z ，口，z ) d ( z ，u ，g ) 】 进一步地，因为l 为格半群，对任意的。，y x ，口= 口l 如， 6 + ( 。，8 ，) = v ：e x 陋( ，驴i ，z ) 6 ( z ，岛，s ，) 】 定义2 2 3 设m = ( x ，阢正( 7 0 ，a 1 ) 为l a ，则其可接受( 识别) 的格值语言 i m f ( u + ) 定义为： 加( 口) = o - 0 。南o o 1 = v ：灌x 【d 心( z ) 扩( 。，口，y ) a l ( 掣) 】 任意，f ( u ) 称为u 上的格值语言 两个l ， “与 幻称为等价的，如果它们接受相同的格值语言，即；，帆= ，帆 9 在经典自动机理论中有限态自动机分为确定型与非确定型，格值自动机的定 义是非确定型自动机的一个推广，自然是非确定型的，以下我们将给出确定型格 值自动机的描述 定义2 2 4 一个d l a 是五元组m = ( x ，玑j ，x o ，o 1 ) ，x ，以o 1 的定义与工a 的一 致，状态转移函数为6 ：x u _ + x ，x o x 为初始状态，6 在u 上的扩张映射 与经典情形一致 d l a 接受的格值语言定义为w u 4 ，m ( 口) = o 1 ( 扩( z o ，8 ) ) 2 2 3 格值文法 与经典自动机理论不同，文 1 9 中已经证明工 和d l a 在识别语言的能力上 并不等价在经典自动机理论中我们知道正则文法和有限态自动机从描述语言的 角度来看是完全等价的，故而我们需要进一步研究二a 和d l a 所对应的模糊文 法 定义2 2 5 ( 1 ) 格值文法是一个四元组g = ( zp s ) ，这里 ( i ) 为非终止符集； ( i i ) t 为终止符集，n t = 织 ( i i i ) s n 为开始符号； ( i v ) p 是tu 上的模糊生成式的有限集合， p = u 与训 ( u t ) n ( n u t ) + ， ( n u t ) 。) ，p l 一 o ) 表示被”取 代的程度 如果u 旦口，a ，卢( nu ? ) ，则有卢与a u 晟称卢可由a 印直接导出， 记作。够= 鸟a ”口， 又对u l ，u p ( u t ) ，若t l 骂u 2 马驽唧时，u p 称为可由上式表 示的从“1 导出的导出链，记作1 当+ p ，其中p = p l p 2 脚- l ( 2 ) 格值文法导出的格值语言记为，g ：t + 上定义为：f c ( e ) = v p ：s 当4 以 两个格值文法g l 和g 2 称为等价的，如果它们产生相同的语言，即：f c 。= ，g 。 按照文法的c h o m s k y 体系，格值文法可分为如下类型： 定义2 2 6 设g = ( n ，t ，p ，s ) 是一格值文法 ( 1 ) g 称为0 型文法，若对p 中元无任何限制对应地，g 称为0 型语言； ( 2 ) g 称为格值上下文有关文法( l c s g ) ，若对任意“鸟u p ，都有f “吲”f 1 0 对应地，g 称为格值上下文有关语言； ( 3 ) g 称为格值上下文无关文法( l c f c ) ，若对任意“鸟”p ，都有h ”i ， 且“n 对应地，知称为格值上下文无关语言； ( 4 ) c 称为格值正则文法( l r c ) ，若对任意t o p ，都有u n 且u t b ，b n u a ) 或t = 只 = a 对应地，g 称为格值正则语言； ( 5 ) c 称为格值弱正则文法( l w r g ) ，若对任意u 与 p ，都有“n 且 t + b ，b n u a ) 或“= s ，”= a 对应地，g 称为格值弱正则语言 定理2 2 1 格值弱正则文法与格值正则文法等价这里“等价”是指生成相 同的语言类 证明：由定义易见，格值正则文法就是一个格值弱正则文法下证每一个格 值弱正则文法生成的语言也是一个格值正则语言 设g 1 = ( n 1 ，正p l ，s ) 是一个格值弱正则文法，其生成的语言记为，g 。可定义 一个格值正则文法g = ( ，正p s ) ，使得f a = ，g ( i ) 对g l 中的生成式：。_ a l a 2 a m y p l 当m = 1 时，生成式为z _ a l y p ，满足要求； 当m 2 时，g 1 ，g 2 ，a 。矸，z ，y n l n ，令1 ，f 2 ，岛一l 是p 中一些 非终止符，并将它们的集合记为0 ，n = n 1u n o z - + o l f l ，f l _ a 2 已，f 。一1 - a m y p 以下我们用p c 和p c 。分别表示g 和g 1 中生成式的隶属度，且 p a ( x - 0 1 f 1 ) = p a ( f l _ a 2 如) = = p c ( e m 一2 一+ 口m 一1 f m 一1 ) = e ； p g ( 岛一1 - a m y ) = p c i 扛- + a l a 2 a m y ) 于是可得 p c ( x _ a 1 1 1 2 a m y ) = p g _ 0 1 乏1 ) 。p g ( 1 一+ 啦毒2 ) 。p g ( e m 一2 - n r n - - 1 专m 一1 ) p g ( f m 一1 a m y ) = p g l 和_ a l a 2 a m y ) ( i i ) 对g 1 中的生成式：$ - + b l b 2 b 。p 1 当n 1 时，b l ，6 2 ，k t 1 ，。n 1 n 令，7 1 ，啦，一1 是p 中一些非终 止符，并将它们的集合记为0 ，n = n 1u n o ，。_ b l y l ，口1 _ 6 2 t 7 2 ，一l _ h p ， 且 p e ( x - + 6 1 q 1 ) = p c ( v l _ + 6 2 ，7 2 ) = = p g ( 一2 _ + 6 n 一1 珊一1 ) = e ； p g ( 叩n 一1 - b 。) = p c 。扣_ 6 1 6 2 k ) 于是可得 p c ( x _ 6 1 6 2 k ) = ，g 扛_ + 6 l q l ) 。p c ( m _ 6 2 啦) 。p c ( n n 一2 - + b n _ l 一1 ) 。p g ( 叼。一1 + k ) = p c l ( 石+ 6 1