（运筹学与控制论专业论文）基于神经网络的模糊有限状态自动机研究.pdf

摘要 摘要 由于模糊文法和模糊有限状态自动机的等价性，使得模糊文法成为模糊自动 机研究的一个核心领域。此外，模糊文法推导有着广泛的应用，比如在解决基于x 射线的骨成熟度的句法识别、基于动脉波的动脉损伤的检测和量化的模糊性、智 能接口设计、临床检测和词法分析等问题上模糊文法推导有着独特的优势。并且 模糊文法推导也是解决诸如语言识别、图像目标识别、蛋白质结构预测和基因结 构预测等问题的有效方法。再则，模糊文法推导中最简单应用最多的当属模糊正 则文法推导。因此，借助于人工神经网络技术强大的功能，使得基于神经网络的 模糊正则文法推导研究有着重要的现实意义和理论价值。 本文从c h o m s k y 体系下文法出发，对模糊自动机基本理论进行介绍后，主要 介绍了神经网络技术在模糊自动机研究中的应用情况。包括模糊有限状态自动机 及模糊文法和神经网络的关系，利用模糊自动机样本对网络进行训练，利用神经 网络进行模糊文法推导和从网络状态中抽取模糊自动机这一完整的系统过程。由 于基于神经网络的模糊有限状态自动机研究所涉及的领域和技术众多，本文的工 作主要是集中于基于神经网络的模糊正则文法推导算法这一领域。应用于该领域 的主要算法有实时间回馈算法( r t r l ) 和实编码基因遗传算法( r c g a ) 。但是， 用实时间回馈算法和实编码基因遗传算法训练二阶递归神经网络进行模糊文法推 导速度相当慢，而且时间复杂度高；实时间回馈算法还是一种不稳定的算法，实 编码基因遗传算法也容易出现过早成熟现象。更糟糕的是，这两种算法在面对模 糊有限状态自动机样本这种特殊的数据源时，异常情况在试验中出现频繁，在现 有网络基础上泛化性不强。 根据以上问题的存在，本文做了三项工作，概括如下： 一、提出基于神经网络l m g a 算法的模糊正则文法推导。在传统r c g a 的基 础上进行改进，将l e v e n b e r g - m a r q u a r d t 算法引入到最优基因的选择过程中，提高 速度并且剔除过早成熟的基因。实验显示了l m g a 的能加快成熟速度但不是病态 的过早成熟，解决了r t r l 时间复杂度高、泛化性和稳定性问题 二、提出了基于神经网络l m b p 算法的模糊正则文法推导，作为目前最快的 神经网络算法即l e v e n b e r g m a r q u a r d t ( l m b p ) 算法在模糊文法推导的实验中显示 了快速收敛能力，主要解决了海量样本和超长串的模糊文法推导问题。 摘要 三、提出了基于神经网络v l b p 学习算法的模糊正则文法推导。v l b p 算法是 基于反向传播且能充分利用梯度信息的r t r l 算法与启发式信息的技术相互结合 的产物，它是在r t r l 算法的基础上引进启发式技术中的可变学习速度。我们将 该算法用应于模糊文法推导的相关问题，实验显示v l b p 算法收敛速度比r g c a 快而且继承了r t r l 的优点并改善了其缺陷，在精确度上还优于l m b p 算法。 本文主要采用了比较、归纳、分析与综合等理论推导方法，并进行实验仿真和 实例验证。 关键词：模糊有限状态自动机，模糊文法推导，回馈神经网络 i i a b s t r a c t a b s t r a c t f u z z ) ，g r a m m ah a sb e c o m et h em a j o rd e v e l o p i n gf i e l d so ft h er e s e a r c ho ff u z z y f i n i t es t a t ea u t o m a t o nb e c a u s eo ft h ee q u i v a l e n c e m o r eo v e r , f u z z yg r a m m a t i c a l i n f e r e n c eh a se x t e n s i v ea p p l i c a t i o na n dd i s t i n c ta d v a n t a g ei ns y n t a c t i cr e c o g n i t i o no f s k e l e t a lm a t u r i t yf o r mx - r a y s ，d e t e c t i n ga n dq u a n t i f y i n gf u z z ya r t e r yl e s i o n sf r o m a r t e r i o g r a m s ，i n t e l l i g e n ti n t e r f a c ed e s i g n , c l i n i c a lm o n i t o r i n g , l e x i c a la n a l y s i s ，e t c f u r t h e r m o r e ，g r a m m a t i c a li n f e r e n c ei sas u i t a b l et e c h n i q u ef o rs o l v i n gt h ep r o b l e m s s u c ha ss p e e c hr e c o g n i t i o n , o b j e c tr e c o g n i t i o ni ni m a g e s ，p r o t e i ns t r u c t u r ep r e d i c t i o n , g e n es t r u c t u r ep r e d i c t i o n ，e t c i na d d i t i o n , t h ef u z z yr e g u l a rg r a m m a r i st h es i m p l e s ta n d m o s tw i d e l yu s e d t h e r e f o r e , t h er e s e a r c ho ff u z z yr e g u l a rg r a m m a ri n f e r e n c eb a s e do n n e u r a ln e t w o r k sh a sg r e a tp r a c t i c a ls i g n i f i c a n c ea n dh i g ht h e o r e t i c a lv a l u e i nt h i st h e s i s ，w ei n t r o d u c et h eb a s i ct h e o r yo ff u z z ya u t o m a t o nb e g i nw i t h c h o m s k yh i e r a r c h y a n dt h e n , w ei n t r o d u c et h ea p p l i e a t i o no ft h en e u r a ln e t w o r k s a p p r o a c hi nf u z z y f i n i t es t a t ea u t o m a t o n i tm a i n l yi n c l u d e sac o m p l e t es y s t e r no ff u z z y a u t o m a t o ni n d u c t i o n gu s i n gn e u r a ln e t w o r k , c o n c r e t e l y ，t h er e l a t i o n s h i po ff u z z yf i n i t e s t a t ea u t o m a t o na n dn e u r a ln e t w o r k sa n df u z z yg r a m m a , t h et r a i n i n go fn e u r a ln e t w o r k s b a s e do ns a m p l es e to ff u z z yf i n i t es t a t ea u t o m a t o n ，t h ef u z z yg r a m m a t i c a li n f e r e n c e u s e dn e u r a ln e t w o r k s ，t h ee x t r a c t i o na l g o r t t h i m so ff u z z yf i n i t es t a t ea u t o m a t o n i nt h i s t h e s i s ，o u rg r o u n dw o r kc e n t e r so nt h ea l g o r i t h m so ff u z z yg r a m m a t i c a li n f e r e n c eb a s e d o nt h en e u r a ln e t w o r k t h e r ea l et w om a i na l g o r i t h m sa v a i l a b l er e a l t i m er e c u r r e n t l e a r n i n g ( r t r l ) a l g o r i t h ma n dr e a l c o d e dg e n e t i ca l g o r i t h m ( r c g a ) b u t ，t h er a t eo f c o n v e r g e n c eo ft h eb o t hm e t h o d si nt h ef u z z yg r a m m a t i c a li n f e r e n c eu s e dn e u r a l n e t w o r k si sr a t h e rs l o w , t h et i m ec o m p l e x i t yc o u l db er a t h e rh i g h ，a n dw e a kg e n e r a t i v e a b i l i t y b e s i d e s ，r t r la l g o r i t h mi su n s t a b k l ea n dt h er c g aa l g o r i t h mc o u l db et r a p p e d i np r e m a t u r e l l t ye a s i l y w o r s e ，b o t ho ft h e ma n dt h ea b n o r m a lc o n d i t i o n so c c u r r e d f r e q u e n t l yb e c a u s eo ft h ed a t as o u r c e so b t a i n e di nt h ee x p e r i m e n t a c c o r d i n gt ot h ea b o v e - m e n t i o n e dp r o b l e m s ，w eh a v ed o n et h r e ew o f k s ，a n dm a y b eb r i e f l ys u m m e du pa sf o l l o w s ： b a s e do nt h el m g aa l g o r i t h mo fn u r a ln e t w o r kf o rf u z z yr e g u l a rg r a m m a t i c a l i i i a b s t r a c t i n f e r e n c et ob er a i s e d f o r i m p r o v i n g t h et r a d i t i o n a lr c g aa l g o r i t h m ， l e v e n b e r g - m a r q u a r d ta l g o r i t h mi si n t r o d u c e di n t ot h ep r o c e s so fo p t i m a ls e l e c t i o n ，i t n o to n l yi m p r o v e st h er a t eo fc o n v e r g e n c eb u ta l s os k i p st h ep r e m a t u r eg e n e s a u t o m a t i c a l l y e x p r i m e n td e m o n s t r a t e dt h a tl m g aa l g o r i t h mr e s o l v e st h ed r a w b a c ko f i l l - c o n d i t i o n e dp r e m a t u r e l i t ya n di m p r o v e st h er a t eo fm a t u r a t i o n t h ee x p r i m e n ta l s o i l l u s t r a t e st h a tl m g aa l g o r i t h mc a ns o l v eo u tt h ep r o b l e m so ft h eh i g hc o m p l e x i t y , w e e kg e n e r a t i v ea b l i t ya n du n s t a b l i t yo fr t r la l g o r i t h m b a s e do l lt h el m b pa l g o r i t h mo fn u r a ln e t w o r kf o rf u z z yr e g u l a rg r a m m a t i c a l i n f e r e n c et ob er a i s e d ml e v e n b e r g - m a r q u a r d t ( l m b p ) w h i c hi st h ef a s ta l g o r t h m o f n e u r a ln e t w o r k sa tp r e s e n ti si n t r o d u c e di n t ot h ef u z z yr e g u l a rg r a m m a t i c a li n f e r e n c e i nt h i st h e s i s ，w ed i s c d b et h ea l g o r i t h ma n da n a l y s i st h ea d v a n t a g ea n dd r a w b a c kb y e x p e r i m e n t i ti so b f i o 瑚t h a tt h ec o n v e n g er a t ei sh i g ht op e r f o r mt h ef r g i i ti sa l s o h a st h ea b i l i t yo f p r o c e s s i n gs u p e r - l o n gs t r i n g s ，t o o b a s e do nt h ev l b pa l g o r i t h mo fn u r a ln e t w o r kf o rf u z z yr e g u l a rg r a m m a t i c a l i n f e r e n c et ob er a i s e d v l b pa l g o r i t h mi sa b a c k - p r o p a g a t i o na l g o r i t h mt h a tm a k e s f u l l b $ eo ft h eg r a d i e n ti n f o r m a t i o n ；i ti st h ec o m b i n a t i v ep r o d u c to fh e u r i s t i c si n f o r m a t i o n t e c h n i q u ea n dr t r la l g o r i t h m w eu s et h em e t h o d ss u c ha sc o m p a r i s o n , i n d u c t i o n , a n a l y s i s ，s y n t h e s i s ，e t cf o r l o g i c a lp r o o f , a n dw ed oe x p e r i m e n t st os i m u l a t ea n dg i v ee x a m p l e st ov e r i f yt h e f e a s i b i l i t yo f o u ra l g o r i t h m k e y w o r d ：f u z z yf i n i t e s t a t ea u t o m a t a , f u z z yg r a m m a t i c a li n f e r e n c e , r e c u r r e n tn e u r a l n e t w o r k i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：立! 翌童查一日期：呷年乡月多日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：燃壶： 导师签名：每兰 。日期：冲年7f 月歹日 第一章绪论 1 1 研究意义 第一章绪论 自动机理论是计算理论三大核心领域之一，论述了计算的数学模型的定义和 性质。所以说自动机是现实计算机的数学模型，或者说是现实计算机程序的模型。 作为经典计算的数学模型，自动机已成为理论计算科学中的重要研究领域，并且 在计算机科学的若干领域中有广泛的应用，如文本处理、编译程序、硬件设计、 人工智能、生物工程自动控制系统、图像处理和模式识别等。 随着模糊集理论的创立与模糊系统的快速发展，模糊有限状态自动机的数学 模型应运而生，使自动机在理论上和应用上都得到进一步的发展。二十世纪八十 年代中后期，人工神经网络理论在世界范围内迅速发展起来并成为一个前沿研究 领域，作为一种模拟人脑智能的模型，具有良好的自学习、自适应、联想记忆、 并行处理和非线形转换的能力。近几年来神经网络和模糊系统的结合又引起了众 多学者的兴趣，因为模糊神经系统结合了两种模型的优点，一是模糊系统的参数 有明确的物理意义，基于规则的和语言的信息可以系统地嵌入模糊适应系统；二 是神经网络有许多有效的训练、学习算法。于是基于神经网络的模糊自动机处理 也得到了新的发展，其应用深入到工业过程控制、地质科学、矿业科学、气象科 学等许多领域中。如果此模型继续深入研究，形成一个边缘性的研究对象，将为 计算机的智能化奠定坚实的基础。 近年来，语言识别、图像中的对象识别、蛋白质结构预测，基因结构预测等 领域引起了众多学者的关注，并在这方面做了很多工作【l 】1 2 【3 1 。解决这些问题的一 种合适的方法就是文法推导，即从一个样本集中提取出文法规则或文法对应的产 生式，或者说构造一个合适的、特制的文法，产生所有出现的每一个样本。而解 决文法推导又有多种方法，将神经网络和自动机结合起来是其中一种行之有效的 方法。具体地，将未知文法产生的字符串样本集作为神经网络的输入，通过神经 网络的学习训练，然后利用规则提取算法从训练完的神经网络提取出识别该样本 集的自动机，亦即对应的产生该样本集的文法。 而且模糊文法推导又被用于解决基于石射线的骨成熟度的句法识别、基于动脉 波的动脉损伤的检测和量化的模糊性、智能接口设计、临床检测和词法分析等问 电子科技大学硕士学位论文 题上。然而，目前提出来的大部分神经网络和模糊系统结合的模型都只能处理静 态的输入一输出关系，而不能处理具有任意长度的时序输入。模糊有限状态自动 机可以模拟那些当前状态依赖于当前输入和先前状态的动态处理。所以，基于神 经网络的模糊自动机研究有着重大的理论意义和实际意义。 1 2 研究现状 自动机表示像计算机一样的信息处理设备的抽象。实际上自动机和神经网络 有久远的渊源。1 9 6 7 年，m i n s k y 证明了每个有限状态自动机( 以下由f s a 表示) 都和某个神经网络等价并能被其模拟【4 】。也就是说，给定一个有限状态自动机m ， 可以建立一个神经网路自动机矿，若将它看做一个黑匣子，则其行为酷似m 。自 那以后，许多学者都尝试着使用不同类型的神经网络去实现各种自动机的推导。 然而，推导是一个难题，即使f s a 也不例外。结果和其他许多的算法一样，设计 用来推导自动机的神经网络要么对所要推导的自动机状态的个数有所限制，要么 需要限制文法类型等等附加条件。 w i l l i a m s ， z i p s e r ( 1 9 8 8 ) ，c l e e r e m a n s ( 1 9 8 9 ) 等和e l m a n ( 1 9 9 0 ) 等分别 讨论了用来识别有限状态语言的一阶回馈神经网络的训练方法【5 6 】【7 】，其中 c l e e r e m a n s ( 1 9 8 9 ) 第一个报道了展示回馈网络能否学会由小型有限状态语法所包 含的例外( 偶发性) 的试验。但是这些方法更侧重于使网络来预测下一个字符， 而不是用来接受或拒绝不同长度的字符串。在e l m a n 的论文中，他对网络的内部 活动( i n t e r n a la c t i v a t i o n s ) 和有限状态自动机的状态之间比较研究。自从e l m a n 等 发表了用简单回馈神经网络( s r n ) 进行学习后，有限状态自动机与回馈神经网 络的结合从此开始了。1 9 9 0 年，g i l e s 等和p o l l a c k 设计出一个二阶回馈网络来解 决从给出的语言样本推导出产生该语言的文法( 或接受该语言的自动机) 问题【8 】【9 】。 1 9 9 1 年，s i e g e l m a na n ds t o n g a g 发现了所有图灵机都可以由建立在用s i g m o i d 激活 函数的神经元上的完全连接回馈网络模拟。同年，g i l e s 等人使用完全梯度算法推 导了一种t o m i t a 语言【l o 】。自此以后，所有参考二阶回馈神经网络的网络模型都隐 含了g i l e s 描述的网络结构。通过使用与g i l e s 的算法有某种不同的完全梯度算法， w a t r o u s 在1 9 9 2 年推导出了几种t o m i t a 语言【l n 。同年，c l g i l e s 用实验证明了一 个使用实时的、前向的训练算法的二阶回馈神经网络通过学习能从肯定的和否定 的字符串训练样本中推导出正则文法。他们用了一个启发式的方法在神经网络训 练期间及以后从中提取f s a 。这种方法不仅可以提取f s a 的状态集，还能获得f s a 2 第一章绪论 本身。这就推广了c l e e r e m a n s 等人在1 9 8 9 年所做的只能提取f s a 的状态集的工 作。然而，当输入字符串越来越长的时候，稳定性问题出现了。即：当越来越长 的字符输入网络时，隐含神经元值所形成的簇( 状态) 相互渗透而最终变得不能 辨别。z h e n gz e n g , r o d n e ym g o o d m a n 和p a d h r a i cs m y t h 在1 9 9 3 年阐述了产生这 种问题的原因，那是由于构造出的网络使用聚类的簇代表状态，而实际上自动机 的状态都是离散的【1 2 1 。与之相应的训练算法是建立在完全梯度基础之上，通过修 改而得到的伪梯度算法。然而，当所要推导的自动机状态个数增大时，这种离散 网络就显得有些力不从心了。1 9 9 3 年，c l g i l e s 使用带有一个外部“连续的堆栈” 的三阶反馈神经网络实现了下推自动机( p a ) 的推导t 1 3 1 。由于上面提到的稳定性问 题，在他们的工作基础上，z h e n gz e n g 在1 9 9 4 年提出了带有外部离散堆栈的离散 网络结构【1 4 1 。然而，这两种网络都对所讨论的上下文无关文法的范围作了如下限 制：只有当前的输入字符能被推到堆栈之上；e p s i l o n 变换集( 不读入一个新的输 入字符而做状态转移和堆栈动作) 为空。1 9 9 5 年，s i e g e l m a n n 和s o n t a g 在理论上 证明了二阶回馈神经网络( s o l 心玳) 与图灵机是等价的，因此可以计算任何数字 计算机能够计算的函数。1 9 9 9 年，c l g i l e s 证明了模糊自动机、回馈神经网络和 动态模糊系统在知识表现的等价性【1 5 1 。a b l a n c o 等人在2 0 0 0 年提出了一种实编码 的基因算法来训练回馈神经网络，从而又丰富了网络的学习算法【1 6 1 。 上面主要是介绍用于文法推导的神经网络模型及其学习算法的研究现状。下 面介绍一下从训练完的神经网络中提取出自动机的研究现状【1 7 1 。从s o r n n 提取 规则( 几乎都表示为有限状态自动机) 的基本方法如下。先要把s o r n n 的连续状 态空间映射到有限个离散状态，使得这些状态与得到的机器的状态相对应。1 9 9 1 年，g i l e s 等人的算法将状态空间等分为相同大小的超立方体( 即宏状态) ，然后 将输入模式输入到网络中，用宽度优先算法对划分进行搜寻，直到没有新的划分 被访问。宏状态( 由输入模式诱导的) 间的转移是提取出来的自动机的基础。搜 寻从预先定义好了的网络的初始状态开始，然后在宏状态上对所有可能的输入模 式进行测试。每一个宏状态遇到的第一个微状态用来诱导新的状态，这保证提取 出来的是确定型自动机，因为任何的状态漂移( s t a t ed r i f t ) 都由于搜寻在重新进入 已经访问过的划分时将会被修剪而得到避免【l 引。但是，这种技术的一个明显的问 题就是，在最坏的情况下，簇的个数由于状态结点的增加而呈指数增长，从而使 得宽度优先搜寻的时间随着可能的输入符号数目也呈指数增长。实际上，真正访 问到的状态远比可能的状态要少。这种方法不仅是最早的s o r n n 规则提取算法， 也是用得最广的算法。几乎所有提出新的s o r n n 规则提取算法的文章都引用 电子科技大学硕士学位论文 g i l e s ，m i l l e r ，c h e n 等人的文章。1 9 9 3 年，z e n g 等人提出了另一种简单的等分量 化方法，使用k 一均值算法对微状态进行聚类【1 9 1 。聚类中心( 称为标准向量) 作为 宽度优先搜寻的基础。然后对每一个标准向量状态以及所有的输入符号，对 s o r n n 进行测试( 和等分算法一样，遇到的第一个s o r n n 的状态作为进一步搜 寻的基础) 。在提出的基于搜寻的方法中，重新进入划分是修剪搜寻的基础。 a l q u e z a r 和s a n f c l i u 在1 9 9 4 年提出了一种不同的修剪策略，他们选择定义域来确 定搜寻的深度。基于在训练集中出现的肯定串和否定串构造一棵预固定树，这棵 树仅包含训练集中出现的串。s o r n n 的状态也只用预固定树里的串来产生。由预 固定树产生的状态是初始自动机的基础。空间上最靠近的状态将反复地融合在一 起直至进一步的聚类产生不一致为止。1 9 9 7 年，a l q u e z a r 将这种规则提取技术用 到各种正则文法和两种网络上去。 由于模糊有限状态自动机的研究内容很多，比如模糊自动机的代数系统和最 小问题，但是本文不对此做详细介绍，仅在此对起发展情况做一个简述。对于模 糊有限自动机的代数系统的发展历史虽然很长，但是发展速度并不是很快，起主 要理论可以参看文献 2 0 】。近年来，随着四川师范大学数学系莫智文教师将格值和 拓扑模糊自动机理论系统化后，代数系统有了新的突破。对于模糊有限状态自动 机的状态最小化问题【2 1 2 2 1 1 2 3 】在模糊有限状态自动机的理论和应用方面都占有极其 重要的地位。s a n t o s 在文献 2 4 】中对最大最小型模糊有限状态自动机的约简问题进 行过深入的探讨，并为此发展了一种最大最小代数，提出了各种不可约简和最小 化的判据。但其状态最小化的程序较难理解和实施。m a l i k 、m o r d e s o n 与s e n 也对 他们提出的模糊有限状态自动机的状态最小化问题进行了探讨，但并未给出一个 详细的状态最小化算法程序【2 5 1 。2 0 0 2 年，b a s a k 和g u p t a 提出了替代性质 ( s u b s t i t u t i o np r o p e r t y ) 的概念，从而得到一种基于商自动机方法的模糊自动机状态 最小化算法【2 6 】。2 0 0 5 年，t a t j a n ap c t k o v i d 在提出同余和同态等概念的基础上，得 到了一种对于带有输出和不带输出的模糊自动机的最小化算法暖丌。 1 3 主要工作 主要针对运用神经网络来解决模糊文法推导问题做了三个工作，概括如下： 一研究了基于l m g a 算法的神经网络在模糊文法推导中的应用。实编码基 因遗传( r c g a ) 算法训练二阶回馈神经网络进行模糊文法推导中容易出现过早成 熟和速度慢的缺陷。于是在传统r c g a 的基础上进行改进，将l e v e n b e r g - m a r q u a r d t 4 第一章绪论 算法引入到最优基因的选择过程中，提高速度并且剔除过早成熟的基因。试验现 实了l m g a 的成熟速度但是不是病态的过早成熟。 二研究了基于l m b p 算法的神经网络在模糊文法推导中的应用。用实时间回 馈( r t r i ，) 算法和实编码基因遗传( r c g a ) 算法训练二阶回馈神经网络进行模 糊文法推导表现出了精度高的良好性能，但是速度慢。然而作为目前最快的神经 网络算法即l e v e = n b c r g - m a r q u a r d t ( l m b p ) 算法在模糊文法推导中的应用却很少引 起学者们的关注。本文所做的工作就是通过实验对l m b p 算法在模糊文法推导中 的优势与缺陷等性能进行分析，实验显示了l m b p 算法在模糊文法推导中的快速 收敛能力。 三研究了基于神经网络v l b p 学习算法的模糊正则文法推导。用实时间回馈 ( r t r i ，) 算法训练二阶回馈神经网络进行模糊文法推导，具有不稳定性和时间复 杂度比较高的问题，于是有学者提出了时间复杂度更低的实编码基因遗传( r c g a ) 算法。由于r c g a 算法没有利用误差梯度信息，一方面解决了r t r l 容易陷入局 部最优的问题，另一方面却损失了误差梯度中的有用信息。为了解决两方面的问 题，本文采用一种启发式快速算法，即可变的学习速度( v l b p ) 算法，并且在文 章中给出了具体的实验效果对比。 电子科技大学硕士学位论文 第二章模糊自动机基本理论介绍 形式语言和自动机的理论是计算机科学的理论依据，来源于c h o m s k y 对自然 语言的研究、巴科斯和诺尔使用巴科斯诺尔范式( b n f ) 对a l g o l6 0 语言的语 法描述和k l e e n c 在研究神经细胞时建立的自动机模型。这些理论中，文法、语言 和自动机之间都是一一对应的关系。随着自动机理论应用领域的不断扩大，原本 高度完善的自动机理论体系已经不能完全适应新的需求，建立在模糊理论基础上 的模糊自动机理论就是为了满足不同领域的需求而诞生。 本章的内容主要集中于介绍模糊文法、模糊语言与模糊自动机的定义、种类 以及三者之间的关系，作为以后各章节的理论基础 2 1 模糊文法与模糊语言 2 i ic h o m s k y 体系下的文法 定义2 1 1 设彳是一个有限集，称彳上的所有字符串所成的集合三为么上的 一个形式语言，故三是a 4 的子集，其中彳+ 是彳的自由么半群。 定义2 1 2 一个文法是指一个四元组g = ( m 正只s ) ，其中是非终止符的 有限集，r 是终止符的有限集，p 是( u 乃、乃+ ( u 乃的一个有限子集，称为产 生式集合( t h es e to f p r o d u c t i o n s ) ，je n ，称为起始状态。 例2 i 1 设= p ，s ，r = ，则g _ ( m 正 p ，s ) 是一个文法。 对于给定的文法g ，其产生式派生出的字符串集合构成了g 生成的语言三( 回 根据文法的定义，( 回是g 的终止字符串的集合。 定义2 1 3设g = ( n ，正只s ) 为一个文法，如果p 有产生式z w ，且 冽( ud 则称x z y 直接推导( 派生) 出x w y ，记为x z y - - - x w y 。 如果勿( n ud ，- - - 1 ，2 ，撑，且忍z + i ，= 1 ，2 ，嚣一1 ，则称磊是由z l 推导 出来的，记为z - i - - z n ，并称z i jz 2 j - - - z n 为从刁到磊的推导。 定义2 1 41 ) 如果尸中的产生式的形式没有任何限制，则称文法g 为0 型 文法，又称无限制文法( u n r e s t r i c t e d ) ； 6 第二章模糊自动机基本理论介绍 2 ) 如果p 中的产生式的形式均为工一y ， 其中工的长度不超过y 的长度，即 k i - ，全部产生式为 $ - - a s b ，p 口6 ，s 为起始状态。则g 是上下文无关文法，且三( 6 3 = 矿矿i n = l ，2 ，) 为上下文无关语言。 例2 i 3设g = ( ，正p ，s ) 为一个文法， n = s ，s ，t = 和，6 ) ，p = p 一6 墨 p 口墨p 蝇p 6 ) ，s 为起始状态。则g 是正则文法，且易得三( g ) = b a b l n = o ，1 ，2 ，m = l ，2 ， 为正则语言。 2 1 2 模糊文法 定义2 1 6一个模糊文法是指一个五元组g = ( m 正p ，s ，) ，其中是非 终止符的有限集，丁是终止符的有限集，p 是( ud d + ( ud + 的一个有限子集， 称为模糊产生式集合( t h es e to f f u z z y p r o d u c t i o n s ) ，s ，称为起始状态，是尸 到 o ，1 】的映射。 如果产生式一p 在尸中，则 一p ) _ c o ，l 】，通常记为口专。c 为p 依赖 0 的程度。具体计算规则如下： 如果a l ，0 c 2 ，槐e ( n uz ) + ，且掣，掣，一。一( r m - i ，h , ( r i ) o ， = 1 ，2 ，m 一1 ，则称a 小可由0 c l 推导出。 模糊y 文法导出模糊语言的规律为： 若，：口专p ，则对任意的6 ，t e ( i n u 功，有，：? a 6 专f f l 8 ，称彬是脚 7 电子科技大学硕士学位论文 的推导，称掣。写。写专( r m - i 为经产生式，2 ，l 从0 【l 到0 c m 的产生式 链，简记为q 一，其中似垆 t ( r 1 ) a 八肛( 1 ) 。 定义2 1 71 ) 如果尸中的产生式的形式均为么_ 五4 专妇或彳专人，其中 踟，a ，b e n ，x ( u 乃，a 为空字符串，则称文法g 为模糊3 型文法，又称模 糊正则文法； 2 ) 如果p 中的产生式的形式均为4 j 口，c 0 其中a ，a e ( ud + ，则称文 法g 为模糊2 型文法，又称模糊上下文无关文法或前后文无关文法( c o n t e x t - f r e e ) 。 3 ) 如果p 中的产生式的形式均为石1 ，其中工的长度不超过y 的长度，即k i m ， 而y ( u 功，则称文法g 为1 型文法，又称上下文有关文法( c o n t e x t - s e n s i t i v e ) ) 或定义为p 中的产生式的形式均为z a w 专z 1 ，其中乙w ( n u 乃，a e n ， v ( n ud + 人) 。 4 ) 如果p 中的产生式的形式，专w ，w ( u 乃+ ，则称文法g 为模糊0 型文 法，又称模糊无限制文法( u r t r e s t r i e t e d ) ； 从定义可以看出，可知模糊正则文法是模糊上下文无关文法，模糊上下文无 关文法是模糊上下文有关文法，模糊上下文有关文法是模糊无限制文法。 例2 1 4 设文法皑假曰) ， o ，1 ) ，p ，墨 ，其中e = - ( s30 b ，bj0 b ， 曰ji & b j o ，则g 为模糊正则文法。 定义2 1 8 【2 8 】一个模糊语言，三( g ) = ( x ，) i ：r 专 o ，1 】，xct + ) ，是字符 串石的隶属度函数。( x ) 表示一个正则模糊文法g 的串x t + 的隶属度。其计算 方法为： 厂、 ( x ) = ( x ) = 纥lj 石i = m a x m i n ( u o ( s 专) ，心( q ) ，鳓( _ 功) j = 工 其中工表示可以推导出串x 的所有产生式链。 定义2 1 9 对于模糊语言三而言，如果存在一个模糊正则( 上下文无关、上下 文有关) 文法g 使得三吒( 回，则称三是模糊正则( 上下文无关、上下文有关) 语言。 由模糊文法g = ( m 正p s ，) 生成的语言记为工( 回，其隶属度计算方法为： 饩( ，g ) ( 口) = ( s j 口) = 。 v d ( ( ) 人( 吒) ( ) ) ，其中0 y ，。 ”1 2 i “ s 口 例2 1 5 设g = ( ，zp ，s ，a ) 为一个模糊文法，r = 口，6 ) ，= 0 ，曰) ，p 中产 生式为s 专彳曰，4 哼口，曰专么，s 一4 ，彳寸6 ，b 专口，s 专曰，么召一删。求s 导出a 及 8 第二章模糊自动机基本理论介绍 口6 的隶属度。 o 80 50 80 - 2o 80 40 s 解：因为s 寸彳j 口；s 专b 专a ；s 专b _ 彳一a ， 所以p u f g ) ( 口) ：( o 8 a 0 5 ) v ( 0 8 a 0 2 ) v ( o 8 a 0 4 a 0 5 ) = 0 5 v 0 2 v 0 4 - - 0 5 。 0 50 50 40 60 50 40 50 6 因为s 一仰j 柏专叫寸口6 ；s 斗船寸州专利一口6 ； 0 50 40 20 60 50 0 40 5o 6 s 专艘专删一刎j 口6 ：s 一砧专剐专州专鲥j 口6 ； 所以 l x t ( m ) ( a b ) = ( o 5 a 0 5 a 0 4 a 0 6 ) v ( o 5 a 0 4 a 0 5 a 0 6 ) v ( o 5 a 0 4 a 0 2 a 0 6 ) v ( o 5 a 0 4 a 0 4 a 0 5 a 0 6 ) = o 4 v 0 4 v 0 2 v 0 4 = 0 4 2 2 模糊自动机 2 2 1 模糊自动机 定义2 2 1 【2 9 】确定型有限状态自动机( d f a ) 是一个五元组： m = ( q ，万，q o ，) 其中，q 是非空的有限状态集；是有限的输入字母表；艿：q - - q 称为状态转 移函数，任意的8 ( q ，x ) = g ，这里g ，矿q ，z ，表示自动机在状态g 时，输入 字符石后到达状态q ；q o q 是开始状态；f 互q 是终止状态有限集。 定义2 2 2 【2 9 】扩展的状态转移函数万。：q x z 。一q ，任意的万( g ，w ) = g ，这里， q , q 7 q ，w ez ，表示自动机在状态g 时，输入字符串w 后到达状态g 。具体的 形式定义如下： 对于空串g ，万( g ，s ) = g ； 对于字符x ，万( g ，x ) = 8 ( q ，z ) ； 对于字符串w - 锨，其中，口，z ，万( g ，w ) = 万( g ，锨) = 8 ( 8 + ( g ，口) ，x ) 。 定义2 2 3 1 2 9 1 有限状态自动机m = ( q ，