（基础数学专业论文）下推格值自动机与模糊系统.pdf

下推格值自动机与模糊系统 吴静杰 v v 一v 摘要自动机是计算的数学模型，擅长语言的识别；文法是描述语言的方 法，擅长语言的产生自动机与形式语言给出了对问题进行抽象和形式化表示的 模型，在计算机科学的文本处理、编译程序、硬件设计、人工智能等应用领域中 起着重要作用随着计算机技术的发展，自动机识别语言的能力及文法生成语言 的能力已经扩展到模糊集理论的应用范围，并随之产生了模糊自动机同时，输 入数据时不确定性情况产生了基于词( 模糊语言串) 的计算，即输入是输入字 母表的模糊子集，这使自动机识别的语言更接近自然语言，在人工智能领域中得 到了广泛的应用李永明教授基于格半群提出了格值自动机，本文在此基础上从 词的角度着重对自动机理论中的下推格值自动机( p d l a ) 与上下文无关格值文法 ( c f l g ) 进行了讨论 模糊系统控制是模糊集理论中最活跃的分支之一，是智能控制理论的重要组 成部分，着重解决系统中多变量表现出不确定性、非线性、时变性时的优化控制 问题，在动力设备、交通运输、航空航天、石油化工、机器人等控制方面取得了 显著的成果其中利用非线性系统的描述函数来分析模糊控制器的稳定性是模糊 控制系统研究的主要领域之一本文主要讨论连续状态下模糊控制器对被控过程 的稳定性能 本文针对自动机理论及模糊系统控制两方面的内容进行讨论，共分两章： 第一章：在自动机理论中，基于格半群，引入下推格值自动机与上下文无关 格值文法的定义，并从词的角度出发对p d l a 与c f l g 进行研究主要得出如下 结论： ( 1 ) 下推格值自动机基于词的计算可以通过基于值的计算实现 ( 2 ) 下推格值自动机以终态与以空栈两种接受词语言的方式是等价的 ( 3 ) 上下文无关格值文法生成的词语言关于并与连接运算封闭 ( 4 ) 上下文无关格值文法与乔姆斯基范式文法等价 ( 5 ) 下推格值自动机接受的词语言与上下文无关格值文法生成的词语言具有 等价关系 第二章：在模糊系统控制理论中，基于t s 模糊控制器模型，讨论了连续 状态下模糊控制器对被控过程的稳定性能主要得出如下结论 ( 1 ) 系统在连续状态下是渐近稳定的，则存在模糊控制器，使得经模糊控制 后的模糊控制系统也是渐近稳定的 ( 2 ) 系统在连续状态下是大范围稳定的，则存在模糊控制器，使得经模糊控 制后的模糊控制系统也是大范围稳定的 定性 关键词：下推格值自动机；上下文无关格值文法；格半群；词；稳 i i p u s h d o w nl a t t i c e v a l u e da u t o m a t aa n df u z z ys y s t e m s w u j i n g - j i e a b s t r a c ta u t o m a t aa r em a t h e m a t i c a lm o d e l so fc o m p u t a t i o n sw h i c ha r eg o o da tr e c o g - n i z i n gl a n g u a g e s g r a m m a ra r em e t h o d so fd e s c r i b i n gl a n g u a g e sw h i c hd ow e l li ng e n e r a t i n gl a n g u a g e s t h e s em o d e l sa r eu s e di ns e v e r a la p p l i e da r e a so fc o m p u t e r s c i e n c ea n d p r o v i d e u sf o r m a le x p r e s s i o n so fa b s t r a c tp r o b l e m s i ti sw o r t hn o t i n gt h a tt h e yp l a yar o l e i nt e x tp r o c e s s i n g ，c o m p i l e r s ，h a r dw a r ed e s i g na n da r t i f i c a li n t e u i g e n c e w i t ht h ed e v e l - o p m e n to fc o m p u t e rt e c h n o l o g y , t h ep o w e r o fa u t o m a t aa n dg r a m m a rh a v eb e e ne x t e n d e d t of u z z ys e t t h e o r y a 8ag e n e r a l i z a t i o no ft h ec l a s s i ca u t o m a t a 一f u z z ya u t o m a t aw e r e s t u d i e d m e a n w h i l e ，c o m p u t i n gw i t hw o r d sw a si n t r o d u c e db yz a d e h w h e nt h ea v a i l a b l e i n f o r m a t i o ni st o oi m p r e c i s et oj u s t i f yt h eu s eo f n u m b e r s ，t h a ti sam e t h o d o l o g yi nw h i c h w o r d sa r eu s e di np l a c eo fn u m b e rf o rc o m p u t i o n ga n dr e a s o n i n g n e e d l e s st os a y , w o r d s h a v et h ef o r mo fp r o p o s i t i o n se x p r e s s e di nn a t u r a ll a n g u a g e s ow o r d sc a nb ea p p l i e di n a ni m p o r t a n tf i e l do fa r t i f i c i a li n t e l l i g e n c e - - u n d e r s t a n d i n gn a t u r a l l a n g u a g e s r e c e n t l y , p r o f e s s o rl ip r o p o s e d an e wa u t o m a t am o d e lb a s e do nl a t t i c em 蚰o i d l a t t i c e - v a l u e da u t o m a t a i nt h i sp a p e r ，p u s h d o w nl a t t i c e - v a l u e da u t o m a t a ( p d l a ) b a s e do nl a t t i c em o n o i d i sd i s c u s s e dw h o s e i n p u t sa r ei n s t e a do fs t r i n g so ff u z z ys u b s e t so ft h ei n p u ta l p h a b e t a f - t e r w a r d s ，s o m ep r o p o s i t i o n so fc o n t e x t f r e el a t t i c e - v a l u e dg r a m m a r ( c f l g ) a r es h o w e d f u z z yl o g i cc o n t r o li so n eo ft h em o s ta c t i v ea r e a si nf u z z ys e tt h e o r y , a n dc o m p r i s e s t h ei m p o r t a n tc o m p o n e n t o f i n t e u i g e n tc o n t r o lt h e o r y i nt h e 缸l d o fs y s t e m s c o n t r 0 1 f u z z y c o n t r o lh a sb e e na p p l i e di ns o l v i n gu n c e r t a i n ，u n i i n e a ra n d t i m e - o p t i m a l c o n t r o lp r o b l e m s ， w h i c hh a sm a d e g r e a tp r o g r e s s e si nd y n a m i cf a c i l i t i e s ，t r a n s p o r t a t i o n ，a v i a t i o na n ds p a c e ， p e t r o l e u mc h e m i c a la n dr o b o t ak e ya s p e c to ff u z z yl o g i cc o n t r o li st h a ta n a l y s i s i n g s t a b i l i t yo ff u z z yc o n t r o n e ru s i n gu n l i n e a rf u n c t i o n s t h e ni nt h i sp a p e r ，t h ec o n t r o l l a b i t y o ff u z z yc o n t r o l l e rt oc o n t r o l l e dp r o c e s si sc o n s i d e r e di nt h ec o n t i n u o u sc o n d i t i o n c o n c e r n i n ga u t o m a t at h e o r ya n df u z z yl o g i cc o n t r o l ，t h i sp a p e ri sd i v i d e di n t ot w o c h a p t e r s ： i i na u t o m a t at h e o r y , b a s e do nl a t t i c em o n i d ，n e wt y p eo fc o m p u t a t i o n a lm o d e l s c a l l e dp d l aa n dc f l ga r ei n t r o d u c e dw h o s e i n p u t sa r ei n s t e a do f s t r i n g so f f u z z ys u b s e t s o ft h ei n p u ta l p h a b e t t h em a i nr e s u l t sa r ef o l l o w i n g ： ( 1 ) c o m p u t i n gw i t hw o r d sc a nb ei m p l e m e n t e db yc o m p u t i n gw i t hv a l u e s i i i ( 2 ) 。t h ee q u i v a l e n c eo fa c c e p t a n c ew o r d sb yp d l a w i t hf i n a ls t a t ea n dw i t he m p t y s t a c ki sp r o v e d ( 3 ) w o r d sl a n g u a g eg e n e r a t e db yc f l g i sc l o s e du n d e ru n i o na n dc o n c a t e n a t i o n ( 4 ) t h er e l a t i o nb e t w e e nc f l ga n dc h e m s k yn o r m a lf o r mi sd i s c u s s e d ( 5 ) t h ee q u i v a l e n c eo fw o r d sl a n g u a g ea c c e p t e db yp d l a a n d g e n e r a t e db yc f l g i sp r o v e d i ii nf u z z yl o g i cc o n t r o lt h e o r y it h ec h a n g e so f s y s t e ms t a t e sa r ed e s c r i b e db yi n p u t o u t p u tr e l a t i o nf u n c t i o n i nt h ec o n t i n u o u sc o n d i t i o n ，t h ec o n t r o l l a b i t yo ff u z z yc o n t r o l l e r b a s e do nt sf u z z ym o d e lt oc o n t r o l l e dp r o c e s si sc o n s i d e r e d t h em a i nr e s u l t sa r ef o l - l o w i n g ： ( 1 ) i nt h ec o n t i n u o u sc o n d i t i o n ，i ft h eo r i g i n a ls y s t e mi sa s y m p t o t i c a l l ys t a b l e t h e nt h ec o n t r o l l e ds y s t e mc a nb ea t t a i n e db yt - sf u z z yc o n t r o l l e ri nt h es a m ec o n t r o l p e r f o r m a n c e ( 2 ) i nt h ec o n t i n u o u sc o n d i t i o n ，i ft h eo r i g i n a ls y s t e mi s g l o b e ls t a b l e t h e nt h e c o n t r o l l e ds y s t e mc a r lb ea t t a i n e db yt - s f u z z yc o n t r o l l e ri nt h es a m ec o n t r o lp e r f o r m a n c e k e y w o r d s p u s h d o w nl a t t i c e - v a l u e da u t o m a t a ；c o n t e x t - f r e el a t t i c e - v a l u e dg r a m - m a r ；l a t t i c em o n o i d ；w o r d s ；s t a b i l i t y i v 前言 伴随着计算机和信息网络技术的发展，在我们用计算机进行问题求解时，需 要用适当的数据进行问题表示，再通过适当的算法分析数据以获得问题的结果 在这一过程中，形式语言与自动机理论给出了对问题进行抽象和形式化表示的模 型，并且通过研究这些模型的性质及其变化方法来对这些问题进行讨论，因而自 动机理论与形式语言在计算机科学的文本处理、编译程序、硬件设计、程序设计 语言与人工智能等应用领域发挥着重要作用 人们希望计算机具有智能，能够直接接受人类自然语言进行操作活动，随之 从语言生成与识别的角度开始了研究乔姆斯基从语言产生的角度，按一定规则 定义文法产生语言，克林从语言识别的角度，利用自动机识别语亩，并证明了文 法与自动机的等价性在对人类自然语言的研究中发现，名词，动词，介词及它们 短语之间的关系中存在着自然的递归，而上下文无关语言就具有这种特性同时 生成它们的上下文无关文法是一种能力较强的描述语言的方法，能够描述某些递 归结构，基于此，在人工智能等领域中，上下文无关文法备受关注下推自动机 是被称作计算模型的理想计算机，它能够识别上下文无关语言，这样我们在证明 一个语言是上下文无关的时候有两种选择；可以给出生成它的上下文无关文法， 或者给出识别它的下推自动机 长期以来，人们对于客观事物的认识习惯追求精确性或清晰性，而在实际中 对于一个动态系统的处理方法是，通过能获得的信息找出影响此系统变化的主 要因素，忽略一些次要因素，用相应的精确数据来建立反映其主要性质的数学模 型，这之中难免包含了不确定性从2 0 世纪4 0 年代中期第一台电脑发展到今天 的超大型并行计算机，人们都在逐步的使计算机能代替人类而解决更加复杂的问 题，比如图论上的四色问题，在棋盘上与人脑抗衡等，但计算机在模仿人的思维 判断方面“智力”很低例如，即使三岁小孩在遇到“六十岁老大爷”与“二十岁 阿姨”也能分辨谁是“爷爷”谁是“阿姨”，但是，现代计算机对此却无能为力究 其原因，四色问题、对弈等问题属于“非此即彼”的确定性现象，而人类年龄的 “老”与“年轻”则是模糊现象围绕着决策、检测、控制及其有关的一系列问题 使美国加利福尼亚大学的上a z a d e h 教授逐渐认识到传统数学的局限性，他指出 模糊性在人类的判断、感觉和情绪领域起着重要作用，利用模糊性是理解人类智 能与机器智能之间深奥区别的关键，并于1 9 6 5 年创造性的提出模糊集理论f 1 8 】，为 研究人类智能提供数学工具，之后，在计算机科学中，作为一般自动机的推广， 开始了利用模糊集的方法研究自动机理论 2 0 世纪6 0 年代s a n t o s 提出了模糊自动机( 6 ，提供了一种研究和处理包含模 糊性自然语言的有力工具7 0 年代，g a i n e s 和k o h o u t 讨论了模糊自动机的逻 辑基础 3 2 1 ，s a n t o s 进一步深入研究了模糊自动机识别的模糊语言，及在各种算 子下的封闭性，提出上下文无关模糊文法，讨论由它生成的语言的性质 4 t 5 】9 0 年代早期，舒兰提出模糊下推自动机及其两种接受语言方式( 终态方式和空栈方 式) ，得出模糊上下文无关语言可被模糊下推自动机以空栈方式接受 3 3 】，m a l i k 和 m o r d e s o n 研究了最大一最小模糊语言及其识别它的一类模糊自动机【9 】在模糊 语言的代数结构上，沈继中 1 q ，a s v e l d 加】讨论了模糊语言中各种算子的性质，如 并，连接，k l e e n e 闭包，与正则语言的交及几种模糊置换在模糊自动机的应用 上，k o s m a t o p o u l o u s 和c h r i s t o d o u l o u 研究了模糊自动机做为模拟各种不确定动 力系统设计工具的可能性【1 引，o m l i n ，t h o r n b e r 和g i l e s 还提出了将模糊自动机应 用到周期性神经网络的方法删 计算机科学面i 瞄的主要任务之一就是要计算机进一步模拟人脑思维，但是要 达到这个目的，不能单纯依靠计算机识别的语言形式语言因为自然语言无法 用形式语言写出程序，是计算机无法理解的语言，因此要解决这种问题就要在形 式语言中渗入一些自然语言自然语言的主要特点是它具有模糊性，z a d e h 将自 然语言与模糊变量融合起来提出了语盲变量的概念冽，它的形式是自然语言中的 字或句，其值是模糊集合，用以表征那些太复杂或不太精确的现象，并在文【2 2 l 中提出模糊约束及模糊约束繁殖的概念，随后产生了基于词( 模糊语言串) 的计 算【2 1 】，即用词取代数进行计算和推理自动机主要是被用来作为识别形式语言的 模型，应明生在文【1 2 】中针对有穷自动机及下推自动机研究了基于词的计算进 行基于词的计算原因主要有两点：第一，获得的信息不准确及变化过程中不确定 的情况使其精确的数学计算难以进行；第二，基于词的计算可使我们利用不确定 性以便使问题易于处理，获得鲁棒性、降低求解费用并更好的与现实一致为了 说明词的概念，我们考虑以下例子 例对于语言变量“方向”用t 表示：t ( 方向) = 向左转+ 不变+ 向右转 第i 种情况分别用论域矿中的i 表示：u = 1 + 2 + 3 + 4 ，( i = 1 ，2 ，3 ，4 ) 则可定义词a l ：a 1 ( 向左转) = 罕+ 警+ 其中“+ ”表示“并”而不是“算术和”a - 表示向左转和几种情况相配合 的程度，它不是建立在数学上有精确定义的对象集合之上，而是建立在语言表示 的一些不确切概念的集合之上，这样我们可将语言看作一个取值为模糊变量的变 量参与计算进行近似推理 2 基于词的计算可以解释成输入数据不确定时的计算，相应的，我们设计的自 动机模型的输入是输入字母表的模糊子集由词串做为输入的自动机可用来设计 分析动力控制系统，它的行为或规则由专家经验和对自然语言的描述而来模糊 自动机理论只是对经典问题较初步的模糊化，即以往的模糊自动机只是对经典自 动机的简单推广李永明教授在更广的框架下，格半群意义下，研究自动机理论 1 1 ，表明了格值自动机与经典自动机的不同之处，并说明它能识别更广泛的形式语 言与模糊语言，构成格值自动机自身的特点本文继续在格半群意义下定义下推 格值自动机，证明其以终止状态接受词语言与以空栈方式接受词语言的等价性， 并证明基于词的计算可以通过基于值的计算实现同时在格值语言的语构方面， 提出上下文无关格值文法，讨论其与乔姆斯基范式的等价性，及其生成的词语言 的性质，并进一步证明下推格值自动机接受的词语言与上下文无关格值文法生成 的词语言之间的等价关系 在控制理论中，处理实际问题必须知道被控对象的数学模型，然而随着科学 技术的发展，被控对象在结构，规模上变得复杂化大型化，使得控制系统的多输 入多输出表现出各种不确定性和非线性特征，然而根据不相容原理，这使精确建 模的方法失效人脑却不存在这样的问题，它可以在只知部分甚至不全对的信息 情况下进行分析判断著名控制论学者工a z a d e h 提出模糊集理论，之后他利用 逻辑规则的语言描述转化成相关控制量的思想，为早期模糊系统的形成奠定了基 础1 9 7 4 年，e h m a m d a n i 构造了基于模糊推理的模糊控制器，将模糊集理论 用于蒸汽机和锅炉的控制，取得了优于常规控制器的控制品质其主要方法是将 人的控制经验及推理过程纳入自动控制，为控制模型未知的复杂系统提供了很方 便的模式之后，模糊系统控制技术迅猛发展，在工业、航空航天、机器人等控 制方面取得显著成果 模糊系统是以模糊规则为基础而具有模糊信息处理能力的动态模型，它既可 以是用以代替被控对象的模糊模型，也可以是对实际对象所施加的模糊控制器 许多难以建立精确数学模型的控制过程如果由人来执行，往往结果非常好，为了 使机器能够模拟人的做法，必须把人的控制经验数学化，这就产生了模糊控制的 理论模糊系统现在的状态和输入，并不能唯一确定下一个状态和输出，而是下 一个可能状态的集合系统的控制方法建立在直觉和经验的基础上，可以视为一 组探索式的判定规则1 9 8 5 年t a k a g i 和s u g e n o 提出t a k a g i s u g e n o 模糊控制 模型 3 6 】( 简称t s 模型) ，其模糊推理由若干i f t h e n 规则构成，前件是模糊 量，后件是输入的线性组合，系统的最终输出由各模糊规则中输出的加权平均得 到 r m t o n g 提出由控制器和被控对象组成的模糊闭环控制系统，分析了基于 3 关系矩阵描述的模糊闭环的稳定性【3 5 】王立新提出稳定的自适应模糊控制器，把 自适应技术用到模糊控制器设计中，解决了模糊控制系统的稳定性设计问题和系 统的性能分析【“ 目前，模糊控制系统理论有了长足发展，但与传统控制理论相比还远未成熟， 对它的稳定性分析一直为人们所关注配有控制器的控制系统在数学上一般表示 为：s = ( p f ) ，其稳定性问题为，如果过程尸可稳定控制，或者说存在控制器f 使控制系统s 为稳定的( 渐近稳定的，大范围稳定的，大范围渐近稳定的等) ， 则是否过程p 也可由某一模糊控制器稳定控制，即是否存在一个模糊控制器f c 使模糊控制系统f s = ( 尸jf c ) 也是稳定的( 渐近稳定，大范围稳定，大范围渐近 稳定的等) ? j j b u c k l e y 已经证明了对可控过程p ，存在模糊控制器f c ，使得f s = ( 只f c ) 在有限时间内可控【2 7 】这样的结果在理论上是很保守的，而且正如他所说，对渐 近性质的行为未能解决，而在控制论中，渐近稳定往往比稳定更重要 s g c a o 等人在文【2 5 ，2 6 】中利用m a m d a n i 型模糊系统对此问题进行了讨论，但本身的推 导是不正确的，而且假设比较强，结果比较弱李永明教授在文【3 】3 中，针对此类 问题基于t s 模型研究了离散时动态系统的稳定性本文同样基于t s 模糊 控制器，在连续情况下给出此类问题的部分解答，回答了b u c k l e y 提出的有关问 题具体的，对于非线性系统s = ( f g ) ，其中f 为过程。由控制器g 控制，过程f 满足微分方程女= “x ( t ) ，u ( t ) ) ，控制器g 的方程为u ( t ) = g ( x ( t ) ) 证明了如果过 程f 可稳定控制( s t a b i l i z e d ) ，或者说存在控制器g ，使得控制系统s = ( f g ) 为稳 定的( 渐近稳定的，大范围稳定的，大范围渐近稳定的等) ，则f 也可以由某一模 糊控制器稳定控制，即存在一个模糊控制器f g 使得模糊控制系统f s = ( f f g ) 也 是稳定的( 渐近稳定的，大范围稳定的，大范围渐近稳定的等) 论文的内容安排如下第一章在格半群意义下，定义下推格值自动机，证明 其以终止状态接受词语言与以空栈方式接受词语言的等价性，并证明基于词的计 算可以通过基于值的计算实现同时在格值语言的语构方面，提出上下文无关格 值文法，讨论其与乔姆斯基范式的等价性，及其生成词语言的性质，并进一步证 明下推格值自动机接受的词语言与上下文无关格值文法生成的词语言之间的等价 关系本文第二章用输入输出的函数关系描述系统的状态变化，同时基于t s 模糊控制器模型证明了，在连续状态下若过程p 可稳定控制，则必可用丁一s 模 糊控制器达到相同的稳定控制性能 4 第一章下推格值自动机及其词语言 1 1 引言 自动机理论为计算理论提供了可靠的数学模型，它在计算机科学的若干领域 中有广泛应用，如文本处理、编译程序、硬件设计及人工智能等经典自动机有四 种基本计算模型：有穷状态自动机，下推自动机，线性有界自动机及图灵机在 识别语言的能力上，它们分别与正则文法，上下文无关文法，上下文有关文法， 短语语构文法等价其中，上下文无关文法是一种能力较强的描述语言的方法， 首先被用来研究人类语言，因为在自然语言中，名词、动词、介词及短语之间存 在自然的递归关系，上下文无关文法就能描述某些具有递归结构特征的语言自 动机在计算理论中主要是用来作为识别形式语言的模型，下推自动机在识别语言 的能力上与上下文无关文法等价，使它同样成为人们研究的重点 下推自动机( p u s h d a w na u t o m a f ；a ，p d a ) 可以看作具有一个输入带的有穷控 制器，并添加一个额外的设备一栈栈在控制器的有限存储量之外提供了附加的 存储，使得下推自动机能够识别更广泛的语言具体来说，p d a 是一个七元组： p d a = ( x ，以f ，d ，x o ，z o ，口) 其中，x 是状态的非空有穷集合，u 是输入字母表，r 是栈符号表，疡，a 分别 是栈开始符，初始状态，终止状态集合，用p f + ) 表示x r 的所有子集组成 的集合，r 是r 的克林闭包，则j 是状态转移函数：x ( u u h ) f - + p ( x x f + ) 文法实际上给出的是语言描述的一种模型系统，其中，上下文无关文法( c o n t e x t f r e eg r a m m a r ，c f g ) g 是一个四元组： g = ( k t ，p i s ) k t ，p s 分别代表变量的非空有穷集，终止符的非空有穷集，产生式的非空有穷 集，文法g 的开始符号对+ 卢p 均有捌a ，且卢( v u t ) ，o k 其中 表示卢的长度 z a d e h 提出模糊集理论后，自动机的识别能力扩展到模糊集理论的应用领域， 减少了形式语言与自然语言的差异其中，模糊上下文无关语言在简化程序设计 语言的翻译以及字符串处理中极其有用，但是，以往的模糊自动机理论只是对经 典问题的较初步的模糊化，因而缺乏层次结构，比如它识别的语言从层次结构上 与经典自动机等价李永明教授在更广泛的框架下，格半群意义下，研究自动机 理论【1 j 表明了格值自动机与经典自动机的不同之处，并说明它能识别更广泛的 形式语言，构成格值自动机自身的特点另外，大部分关于自动机的研究将输入 5 字母表中的字符当作输入值，仍然是关于值的计算，但在输入过程中仍然存在着 不确定性利用这种不确定性是基于词计算的主要方面，它将自然语言与模糊变 量的计算融合起来，即词在数学中表示成输入字母表的模糊子集，从而处理在机 器识别的状态或推理过程出现的不确定性情况 在下文中，我们提出一种“基于词计算”的下推格值自动机模型，它是在格 半群意义下，研究下推格值自动机识别的格值词语言，它的输入是输入字母表的 模糊子集，即讨论的是词串( 对应具有模糊性的自然语言) ，同时提出上下文无关 格值文法及其生成的词语言，并讨论其与下推格值自动机的关系 1 2 预备知识 定义1 2 1 设工为格，a ，v 分别为下确界与上确界运算，0 ，1 分别为最小元 与最大元，为工上的二元运算( 也称为乘法运算) ，且( l ，e ) 为有单位元e l 的半群，若满足： ( 1 ) v a l ，d 0 = 0 o = 0 ， ( 2 ) c a ，b ，c l ，( b vc ) = ( a b ) v ( c ) ，石e ( b vc ) 8 = ( b n ) v ( c o ) ， 则称三为格半群进一步，若工为完备格，且 ( 3 ) d ( v t b t ) = v t ( a k ) ，及( v t b t ) o = v t ( b t n ) ， 则称工为q u a n t a l e 若条件( 3 ) 只对 “) 取为可数集时成立，则称厶为可数格半 群 例1 2 1 ( 1 ) 设( l ，v ) 为分配格，取为a ，则l 为格半群，单位元为1 ( 2 ) 若为单位区间【0 ，1 】上的任一厶模，则( 0 ，1 1 ，v ) 为可换的格半群，单 位元为1 在下文，我们要用到z a d e h 的扩张原理；设以矿为任意集合，：u _ + y 为 通常映射，有模糊集的集合f ( u ) 到f ( v ) 的扩张仍记为，：f ( u ) _ f ( v ) ，如下 定义： v a f ( 【，) ，f ( a ) f ( y ) ，( a ) ( ) = v a ( u ) l u u ，( u ) = ) 文 1 】利用分解定理，先扩张如下模糊映射，g ：u _ f ( y ) ，然后9 可以扩张 到u 的幂集2 u 上，仍记为g ：2 盯_ f ( y ) ，定义为， 9 ( c ，) ( ) = v u u g ( u ) ( 口) 6 进而扩张到映射g ：f ( u ) _ f ( y ) ，为v a f ( u ) ， 9 ( a ) = 9 ( v 。e l a a n ) = v o e l a g ( a n ) 其中a 9 ( a 。) f ( y ) ，定义为， a g ( a 。) ( ) = v u e a 。a g ( “) ( u ) 由此，该扩张映射又有如下刻画( 见文献【1 1 定理1 1 ) ，v a f ( u ) ，v v u 9 ( a ) ( ) = v a ( u ) g ( u ) ( v ) l u c ，) ( 1 1 ) 1 3 下推格值自动机及其词语言 以下假设三是格半群，f ( x ) = 似：x - l i a 是l 值模糊集 定义1 3 1 下推格值自动机( 2 v u s h d o w nl a t t i c e v a l u e da u t o m a t a ，p d l a ) m 是 一个7 元序列m = ( x ，f ，d ，z o ，蜀，a ) ，其中 x 一状态的非空有穷集合v x x ，z 称为m 的一个状态 u 一有穷输入符号集 r 1 一有穷栈字母表v a f ，a 称为m 的一个栈符号 x o 一初始状态 蜀一开始栈底符号是m 启动时栈内唯一一个符号 a 一模糊终状态，a f 瞬) 扣一模糊状态转移函数6 ：x ( u o a ) f _ + 2 f ( x 。) 为了描述下推格值自动机的行为，我们需要介绍一个概念一即时描述 v ( z ， ，7 ) x u xp 称为m 的一个即时描述，表示m 处于状态。，w 是当 前尚未处理的输入字符串，且读头指向”的首字符，栈中的符号串为仉7 的最 右符号为栈底符号对，y x ，u u i z f ，y f + ，d ( z ，u ，z ) ( ，7 ) 代表当状态为 。，栈顶符号为z ，输入为u 时，进入下一个状态y ，栈底符号换为7 的可能度若 a f ( u ) ，f ( u ) 表示词( 模糊语言) 串，则d ( 茹，a ，z ) ( f ，y ) 表示输入为u 上的模糊 集时，状态由。换为y ，栈底符号由z 换为7 的可能度，即表示接受词串的程度， 因此d 可用来处理含有模糊性的自然语言借助于文 1 的扩张映射表达式，j 的 表达式如下： d ( z ，a ，z ) ( 口，7 ) = u u u 陋( 。，“，z ) ( f ，1 ) a ( “) ( 1 2 ) 7 对v a l ，a 2 f ( c ，) ，y x ，7 r ，由扩张映射的刻画( 1 1 ) ，我们有： 占( z ，a l a 2 ，z ) ( 可，一r ) = u y , e x , e f * 陋0 ，a 1 z ) ( 掣，一r ) 占( ，a 2 ，y ) ( 玑7 ) 下推格值自动机的模糊状态转移函数是模糊二元关系，设u 是任意的集合 r 1 ，r 2 是u 上的两个模糊二元关系，则五1 。咒2 定义如下：v u ，w u ， ( r 1o r 2 ) ( “，w ) = u 。e u 陋1 ( ， ) r 2 ( v ， ) r + 是r 在u 上的反射与传递闭包，定义为 r + = r o u r u r 。r u u r ”u 其中印( u ，”) 定义为； 砒扣 ；萋箍蒜 u + 是由u 生成的自由幺半群，u 中的元称为串，乘法运算为串的连接，单 位元为空串，记为a ，下面定义j 的扩张a ：x u p _ f ( x u + r ) 定义1 3 2 设m = ( x ，阢r ，6 ，z o ，z o ，口) 是下推格值自动机，对比，y x ， ，t l ， u + ，o ，卢r + 定义： ( j ) f d ( ，a ， e d ( 卢) ) ( z ，o t t a i t ( 卢) )若 = 0 3 且t a i t ( b ) a z x ( ( u ， ，卢) ，扛，”，q ) ) = d 国，h e a d ( w ) ，h e a d ( b ) ) ( x ，o t a i l ( b ) ) 若 = t a i l ( w ) 且t a i l ( b ) sa 1 0 其它情况 + 是的反射与传递闭包 注；对饱，卢，7 1 1 + ，若d = 伊，记卢口，称卢为o t 的尾( t a i l ) ，且记 7 = a ，h e a d ( f 1 ) 为卢的首字符 自然的，当输入为词，即u 上的模糊集时，由( 1 2 ) ，模糊状态转移函数可相 应定义，对于v v , w f ( u ) + ，( z ，k n ) ，( y ，w 卢) x f ( 矿) + r ，我们可定义a m ： ( j ，) f d ( ，a ，h e a d ( b ) ) ( x ，a t a i l ( b ) )若v = w 且t a i l ( 卢) n m ( ( f ，彬卢) ，( 。，un ) ) = j ( 玑h e a d ( ) ，h e a d ( b ) ) ( x ，烈t a i l ( b ) ) 若v = t a , t ( w ) 且t a i t ( 卢) 1 0 其它情况 a m + 是m 的反射与传递闭包 8 很明显，( j ) ( ，) 很类似，只是输入串不一样，( ，) 是u 中的符号集，而在 ( ) 中输入的是词串即u 的模糊集，表示的是接受词串的程度 下推格值自动机是在有穷自动机基础上增加了栈处理功能，因此我们需要从 有穷自动机本身具有的终态与新增设备一栈两方面来考虑其接受的词语言 定义1 3 3 设m = ( x ，以f ，6 ，孤z o ，o - ) 是下推格值自动机，w f ( ) + ， ( 1 ) m 用终态方式接受词的程度，m ( ) 定义为： 厂m ( w 7 ) = v x e x ，1 r m + ( ( z 。，w z 0 ) ，( ，a ，7 ) ) 盯( $ ) 】 相应的，m 接受的基于词的词语言定义为： l i ( p d l a ) = ( 彬l u ( w ) ) l w f ( c ，) + ( 2 ) m 用空栈方式接受诃w 的程度跏( ) 定义为： 9 m ( w ) 葛v x e x , t e r 。m ( ( 。o ，w ；g o ) ，( 。，a ，a ) ) 相应的，m 接受的基于词的词语言定义为： l 9 ( p d l a ) = ( 暇g m w ) ) l w f ( u ) + ) 关于下推格值自动机接受的基于词的程度，m ( ) 与鲫( ) ，以下我们以m 用终态方式接受为例进行说明 例1 3 1 设m = ( z o ，搿1 ， o ，1 ) u n ) ， z o ，历) ，6 ，z o ，疡，口) 是下推格值自动机， 其中，a = 等+ 百0 9 ，d 定义如下： 6 ( x o ，0 ，z o ) ( f ( x o ，0 ，z t ) 5 ( x o ，1 ，玩) 6 ( x o ，1 ，z 1 ) 6 ( x o ，a ，z o ) 6 ( z o ，a ，z t ) ( f ( x l ，0 ，z o ) ( i ( x l ，0 ，z 1 ) o 。( x l ，1 ，g o ) 5 ( x l ，1 ，z 1 ) 6 ( x l ，a ，z o ) 5 ( 3 ：1 ，a ，历) 9 瓦 瓦 瓦丽， 郾叼一。咐一。即甲一。m 且有a 1 = 5 - - 学，a 2 = 警+ 毕，l 取值为【o ，1 ，取乘法运算 则： 5 ( x o ，a 1 ，玩) = 1 5 ( x o ，0 ，z o ) v0 6 ( f ( x o ，1 ，玩) ：= 粼o , 3 + v 舻 g ( x o ，a 2 ，z o ) = 0 4 c i ( x o ，0 ，g o ) v0 9 d ( 。o ，1 ，z o ) 三当砖蝥：9 。尚 一( o o ，z l 面) 。e z l ，z 1 j j ( 。o ，a 1 ，蜀) = 1 6 ( 。o ，0 ，z 1 ) v0 6 t5 ( x o ，1 ，而) = 尚 d ( z o ，a 2 ，z 1 ) = 0 4 6 ( x o ，0 ，z 1 ) v 0 9 6 ( x o ，1 ，z 1 ) ：轳 6 ( x l ，a 2 ，g o ) = 0 4 6 ( x i ，0 ，g o ) v0 9 d ( 。l ，1 ，z o ) j ( z 1 ，a 2 ，蜀) = 0 4 - 占( z l ，0 ，z 1 ) v 0 9 d ( 。l ，1 ，z 1 ) ! 臻。尚 词串a i a 2 的模糊状态转移函数计算为z 6 ( x o ，a i a 2 ，g o ) = 6 ( j ( z o ，a i ，z 0 ) ， 2 ) = d ( 尚+ 考勤，a 2 ) = 0 3 5 ( x o ，a 2 ，z 1 9 0 ) v 0 2 4 6 o 蠹：曩01 丽6 盎茹”、写孺0 而