（运筹学与控制论专业论文）模糊有限自动机及其最小化问题.pdf

模糊有限自动机及其最小化问题 运筹学与控制论专业 研究生洪晓蕾指导教师莫智文( 教授) 论文摘要：本文在模糊自动机理论的基础上，讨论了模糊自动机的最小化问题。 首先，介绍了经典模糊集、自动机和模糊自动机的一些相关基础理论。其 次，重新定义t m e a l y 型模糊有限自动机中状态等价的概念，这种等价状态被扩 展到了依赖字符串长度面非字符串本身的一神弱等价状态，使其具有更广泛的应 用性。并在弱等价条件下，讨论 m e a l y 型模糊有限自动机的性质，进而确定了 它的最小化自动机的形式，最后给出了相关算法。再次给出了m e a l y 型模糊有 限自动机在输入模糊字符串意义下的概念，即对模糊转移函数和模糊输出函数做 了相应的扩张，然后通过讨论它的一些性质，得到了当输入模糊字符串时的状态 最小化方法。最后，给出了一种新的m i z u m o t o 有限自动机，它不同于m a s a h a r u m i z u m o t o 定义的经典形式，其重要的区别在于将终止状态赋予模糊隶属度。在 此基础上建立了m i z u m o t o 有限自动机与标准模糊有限自动机的等价关系。& 口把 具有模糊初始状态m i z u m o t o 有限自动机等价成一种初始状态为单一且分明的标 准模糊有限自动机，随之得到了它在标准形式下的最小化算法 关键词：模糊有限自动机im e a 2 y 型模糊有限自动机；m i z u m o t o 有限自 动机；弱等价；状态最小化；模糊字符串；标准模糊有限自动机 第i 页，共：均页 f u z z yf i n i t ea u t o m a t aa n dt h e i rm i n i m i z a t i o n s o p e r a t i o n sr e s e a r c ha n dc y b e r n e t i c s w r i t e r ：h o n gx i a o l e i 。 s u p e r v i s o r ：m oz h i w e n a b s t r a c t ：i nt h i sp a p e r ，b a s e do nf u z z yf i n i t ea u t o m a t a ，t h ea l g o r i t h m so f m i n i m a lf u z z ya u t o m a t aa r ec o n c e r n e d a tf i r s t ，t h ec o n c e p t i o n so ff u z z ys e t ，a u t o m a t aa n df u z z ya u t o m a t aa r e g i y e n s e c o n d l y , w ed e f i n et h ec o n c e p to fe q u i v a l e n c es t a t ei nm e a l yf u z z y f i n i t ea u t o m a t o n t h ee q u i v a l e n th a sb e e ne x p a n d e dt ot h ea l p h a b e t i cs t r i n g s e l fb e i n gd e p e n d e n to nt h ea l p h a b e t i cs t r i n gl e n 垂hb u tb e i n gn o to n ek i n d w e a ke q u i v a l e n t w h i c hh a sam o r ew i d e s p r e a da p p l i c a t i o nt h e nb e f o r e s o m e p r o p e r t i e so fm e a l yf u z z yf i n i t ea u t o m a t o na r ed i s c u s s e d f u r t h e rm o r e ，t h e e x p r e s s i o no fm i n i m i z a t i o ni sd e t e r m i n e d a tl a s t m i n i m i z a t i o na l g o r i t h mi 8 s h o w n 0 n e em o r e ，t h ec o n c e p to fm e a l yf u z z yf i n i t ea u t o m a t o nw h o s ei n p u t s a r ew o r d si se s t a b l i s h e d n a m e l yw eh a v em a d et h ec o r r e s p o n d i n ge x p a n s i o n t ot h ef u z z ys t a t e sf u n c t i o na n dt h ef u z z yo u t p u tf u n c t i o n p r o p e r t i e so fm e a l y f u z z yf i n i t ea u t o m a t o n 础d i s c u s s e d w ed e s c r i b ei t s l i n i m i z a t i o na l g o r i t h m o nt h eb a s i s o ff o r e g o i n ga n a l y s i sb e i n gs h o w na b o v e f i n a l l y , w ei n t r o d u c e an e wm i z u m o t o6 血t ea u t o m a t o n w h i c hi s 出e r e n tf r o mg e n e r a lf o r l n m a s a h a r um i z u m o t od e f i n e d t h ei m p o r t a n td i f f e f e n c el i e si n6 n a ls t a t w i t h m e m b e r s h i pd e g r e e f u r t h e rm o r e ，t h ee q u i v a l e n c eo ft h et y p eo fm i z u m o t o f i n i t ea u t o m a t o na n dc a n o n i c a if u z z yt i m t ea u t o m a t o nw i t hs i n g l ei n i t i a ls t a t e a n dd e t e r m i n i s t i ct r a n s i t i o nf u n c t i o ni se s t a b i s b e d t h e nw ep r e s e n tam e t h o d t om i n i m i z et h es t a t e so fa u t o m a t o ni nc a n o n i c a lf o r i l l k e yw o r d s ： f u z z y f i n i t ea u t o m a t a ；m e a l yf u z z yf i n i t e a u t o m a t o n ； m i z u m o t of i n i t ea u t o m a t o n ；w e a ke q u i v a l e n t ；m i n i m i z a t i o n ；w o r d ；c a n o n i c a l f u z z yf i n i t ea u t o m a t o n 四j i i ! l i 面范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师墓鳖塞：指导下，独立 袭韬夫 进行研究工作所取得的成果。除文中已经注明引用的内容夕卜，本论文不含任何 其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献 的个人和集体，均己在文中以明确方式标明。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为串请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印 刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库进 行检索：2 ) 为教学和科研目的，学校可以将公开的学位论文或解密后的学位 论文作为资料在图书馆、资料室等场所或在校园网上供校内师生阅读、浏览。 论文作者签名：诌0 冕唐 御7 年f 月沙日 引言 随着科学研究的不断深入，数学已不再仅作为一门基础学科被研究。其 应用范围广至科学研究的各个领域。研究的对象越来越复杂，变量越来越 多，要求对系统的控制精度越来越高而复杂的系统工程是难以精确化的， 这些不确定性与数学的精确性就形成了十分尖锐的矛盾，甚至当一个系统的 复杂性增大时。使它精确化的能力将减小。不确定性已达到一定的阀值之上 时，具有精确性的数学理论将在系统控制方面完全失效。 针对这一问题，1 9 6 5 年，z a d e h 教授发表了模糊集合论【5 0 5 1 ，提出 了用”隶属函数”这个概念来描述现象差异的中间过度，从而突破了古典集合 论中属于或不属于的绝对关系。这一开创性的工作，标志着数学的一个新的 分支模糊数学的诞生。模糊数学是研究模糊现象及其概念的新的数学分支学 科，所研究的事物的概念本身是模糊的，即一个对象是否符合这个概念难以 确定，这种由于概念外延的模糊而造成的不确定性称为模糊性用在1 0 ，1 】上 取值的隶属函数就描述这种模糊性。模糊集合是客观存在的模糊概念的必然 反殃。模糊概念就是边界不清晰，外延不确定的概念。以模糊集合代替原来 的经典集合，把经典数学模糊化，便产生了以模糊集合为基础的模糊数学。 模糊集理论率先d q w e e 4 4 在1 9 6 7 年应用于自动机领域，第一个模糊 有限自动机的数学模型随之诞生e s s a t o n s 在文献【3 8 】中定义了一种最 大最小型模糊有限自动机。e t ，l e e 和l 。a z a d e h 2 0 在1 9 6 9 年也提出了一 种模糊有限自动机的概念具有模糊初始状态的模糊有限自动机首先 是由m m i z u m o t o 、j t o y o d a 和k t a n a k a 2 7 提出并且利用模糊矩阵和模糊 向量的工具进行研究的。k a s a i 和s k i t a j i m a 2 研究了与经典的m e a l y 型 和m o o r e 型自动机相对应的两种模糊有限自动机：m e a l y 型模糊有限自动机 和m o o r e 型模糊有限自动机。d s ，m a l i k 、j n m o r d e s o n 与m k s e n 2 5 也定义了 一种模糊自动机 f u z z ys w i t c h i n ga n da u t o m a t a ：t h e o r ya n da p p l i c a - t i o m ) ) f 1 6 1 、 f u z z yd i s c r e t es t r u c t t t r e s f 2 6 和 f u z z ya u t o m a t aa n dl a n g u a g e s ：t h e o r ya n da p p l i c a t i o n s ) 2 8 1 x 口模糊自动机理论的研究和发展作了一 第1 页，共j 9 页 引言 个全面的总结和展望。另外，程伟、莫智文【8 】就当时的所有模糊有限自动机 做了一个分类。雷红轩、李永明2 2 1 对其中一类模糊自动机作了详尽的讨论。 近几年来，随着模糊技术的飞速发展，由模糊理论和自动机结合构成的 模糊有限自动机和模糊语言，在其应用及进一步发展中，不仅合理地扩展了 分明有限自动机和语言理论，而且已被应用于更广泛的领域，如学习系统。 模糊有限自动机在其应用过程中，常以设计工具的形式出现。作为一个设计 工具，对于其价值的判别关键在于是否可以提供一种设计指引使设计者可以 得到最佳的设计方案而其中最重要的一个判别标准即是设计的最简化，即 状态的最小化约简。由此可见，模糊有限自动机的状态最小化约简问题在模 糊有限自动机的理论和应用方面占有及其重要的地位。 最小化问题几乎是伴随着自动机的诞生而产生的。3 9 1 是收集到的最早 的系统讲述自动机最小化约简问题的。后来，人们在模糊自动机及最小化 问题上做了大量的工作【1 】【5 】f 1 1 】【1 4 】【1 5 】 17 】 1 9 j 2 4 】 4 1 j 4 2 】【4 6 】 5 2 j 程伟和莫智 文【9 1 改良t m e a l y 型模糊有限自动机的输出函数的定义，避免了一个未经证 明的关键假设，给出了状态最小化算法。近年来，随着模糊有限自动向着 格和量子方面的发展，邱道文 3 l 】【3 6 】对完各剩余格值逻辑的自动机及量子 自动机及其文法都做了相应的刻画。k p e e v a ( 2 9 1 讨论了模糊l 一自动机的等 价约简和最小化问题及其相关算法紧接着，t a t j a n ap e t k o v i c 3 0 利用格 自动机的同余和同态对模糊有限自动机的最小化问题做了讨论雷红轩和李 永明f 2 3 1 就格序列自动机的最小化闯题做了深入讨论。随着模糊自动枫岛着 模糊一自动机和模糊。一自动机的发展，这又将把我们带入一个新的学习领 域。k k r i t h i v a s a n 、j a n 和k s h a r d a 1 8 介绍了模糊u 一自动机的相关概念并对 不同类型的模糊u 一自动机及其所识剐的相应类型的模糊形式语言作了深入讨 论。从另一方面来讲，模糊有限自动机和一些现代算法相结合，让我们嗅到 了时代的气息【4 】 6 1 0 】【1 2 】 4 3 】，这使得我们的最小化算法更简单易行。 作者在总结前入工作的前提下，尽量完善各种典型模糊有限状态自动机 的状态最小化问题；针对一些经典的模糊有限自动机，提出扩张后模糊有限 自动机的定义以及相关性质，使其具有更广泛的应用性，同时研究扩张后模 型的状态最小化问题；对于不属于通常的状态约简概念范畴的模糊限自动 h x l e i g 1 6 3 c o r n 第2 页，共3 9 页毕业论文 机，提出新的状态最小化方法。 具体来说，作者做了以下几个方面的工作： 1 m e a l y 型模糊有限自动机在弱等价条件下的最小化方法 受到d s m a l i k ，j n m o r d e s o n ，m k s e n ( 2 5 的启发，并在程伟和莫智文f 9 j 的研究基础上，重新定义了状态等价的概念。这种等价状态被扩展到了依赖 字符串长度而非字符串本身的一种弱等价状态。并在弱等价条件下，讨论 了m e a l y 型模糊有限自动机的性质，进而确定了它的最小化自动机的形式，最 后给出了相关算法。 2 基于模糊字符串的m e a l y 型模糊有限自动机的最小化方法。 前人在模糊有限自动机的工作中几乎都只考虑输入单个字符或字符串。 从知识系统中来看，输入字母表中的字符可以看作是待处理的信息因此， 我们可以考虑这样一种模糊t j 动机，不仅它的下一个状态是模糊的，而且能 识别模糊的字符或字符串。2 0 0 2 年，应明生 4 9 】率先应用z a d e h 教翥t 5 1 】的模糊 扩张原理把输入字符串扩张到了输入模糊字符串。按照程伟、莫智文【8 】提出 的模糊有限自动机的分类思想，f 4 9 r 扩张到了其中的一类，即有初始状态无 输出字符的模糊有限自动机。 在此基础上，作者讨论了另一类模糊有限自动机，即无初始状态有输出 字符的模糊有限自动机一m e a l y 型模糊有限自动机。最后还给出了当输入模糊 字符串时的状态最小化方法。 3 m i z u m o t o 有限自动机的最小化问题。 m i z u m o t o 有限自动机的最小化问题有一个难点，即该类型模糊有限 自动机的初始状态是模糊的，因而不属于我们通常的状态约简的概念的 范畴。所以要求设计者必须提出一种新的模糊有限自动机状态约简的方 法2 0 0 2 年，n c ，b a s a k 和a o u p t a 3 提出了一种基于商自动机形式的状态最 小化问题2 0 0 5 年徐芳、舒兰、程伟和莫智文【4 7 】定义了一种新的约简概念。 讨论了m i z u r n o t o 有限自动机在此定义下的最小化算法。作者在本文中给出了 一种新的m i z u m o t o 有限自动机，它不同于m a s a h a r um i z u m o t o 【2 7 1 定义的经 典形式其重要的区别在于将终止状态赋予模糊隶属度。受到h s u s a n - s h i h h x l e i 9 1 6 3 c o n l 第3 页 盘3 一i 页毕业论文 引言 l e e 【2 1 】的启发，建立了m i z u m o t o 有限自动机与标准模糊有限自动机的等价关 系，即把具有模糊初始状态m i z u m o t o 有限自动机等价成一种初始状态为单一 且分明的标准模糊有限自动杌，随之得到了它在标准形式下的最小化算法。 h x l e i 9 1 6 3 c o r n第4 页洪翩页 毕业论文 第一章预备知识 1 1 模糊集合理论基础 模糊集合是没有精确边界的集合，它是以逻辑真值为【o ，1 】的模糊逻辑为 基础的，它表示的是元素属于集合的程度。 定义1 1 1 【4 8 】设在论域u 上给定了一个映射以：矿一1 0 ，l 】，“一以( ， 则称a 为，上的模糊集，称为a ( ) 的隶属函数。我们用f ( 表示【，的所有 模糊子集的全体。 口 定义1 1 2 【4 8 】设a ，b 是同论域u 上的两个模糊集合 含、相等关系定义如下： a 包含于b ，记作a b 营a ( 日( “) ，u a 等于b ，记作a = b a ( 甸= 日( u ) ，v u u 它们之间的包 口 定义1 1 3f 4 8 1 设a ，b 是同一论域c 厂上的两个模糊集合。它们之间的交、 并、补运算定义如下： 与b 的交，记作a n b 有( a n b ) m ) = a ( u ) 日( “) = m 伽( n ) ，b o o ) ，u u ： a 与b 的并，记作a u b 有( a o b ) ( ) = a c u ) v b ( u ) = m ( “) ，b ( u ) ) ，t e u ： a 的补，记作a 。有a 。( u ) = 1 一a ( t 1 ) ，t u 。 口 1 2 有限状态自动机 定义1 2 ，1 【1 3 】一个有限状态自动机是一个五元组m = ( q ，a ，仍i ，t ) 所表 示的系统，其中： q 是一个有限状态集： a 是一个有限的输入符号集或字母表； 第5 页共3 9 页 第一章预备知识 i 是初始状态： ? 是终止状态集； 妒：q a q 是状态转移函数( 妒可以自然扩张为妒：q a 一q ) 口 我们说有限状态自动机m 识别( 或接受) 一个字u 岔，如果沁t 我们 把m 所识别( 或接受) 字的全体称为有限状态自动机m 所识别( 或接受) 的语言， 记作l ( m ) ： l ( m ) = 扣a l 妇研 换一种方式，我们可以扶矩阵和向量韵观点来看待一个有限状态自动 机。 定义1 2 2 一个有限状态自动机是一个由四元组m = ( q ，以 f ( 口) f 口 a ，t 7 r ) 所表示的系统，其中： q = q l ，9 2 ，弧) 是一个有限状态集； a 是一个有限的输入符号集或字母表； i 是初始状态； w = ( 7 r q 。，7 r ，霄h ) 是一个n 维行向量其中： l1 ，如果吼= i ， “一10 ，如果啦t r 是终止状态集； 矿= ( 啦、，。f “) 是一个n 维列向量，其中： l1 ，如果魏互 地一l0 ，如果瓠暮z f ( 0 1 是一个n n 阶状态转移矩阵：如果输入字母口a ，存在从状态k 到 状态j 的状态转移，那么f ( 口) 】材= 1 ；否则，垆( a ) k = 0 口 我们说m 识别( 或接受) 一个字w a ，如果霄xf ( w ) 矿= 1 我们 把”所识别( 或接受) 字的全体称为有限状态自动桃m 所识黝( 或接受) 的 语言，记作l ( m ) ： ， l ( m ) = u a l r ，( ) 矿= 1 ) h x l e i 9 1 6 3 c 嘲 第6 页，共3 9 贞 毕业论文 第一章预每知识 定义1 2 3 4 0 j 一个m e a l y 型有限自动机是一个由五元组m ：m = ( q ，最a ) 所表示的系统，其中： q 为有限状态集； 为有限输入字符集； 为有限输出字符集； 6 ：q 一q 为转移函数： a ：0 x e 一为输出函数。 口 如果设m 现在处于状态q ，此时输入字符口e ，那么下一步将转入状 态5 ( g ，口) q ，同时有一个输出a ( 口，c ) 。 1 3 模糊有限状态自动机 定义1 3 1 【2 0 一个确定型模糊有限状态自动机是一个五元组m = ( q ，e ，d ，q o ，f ) 所表示的系统，其中： q 是有限状态集； 是有限输入符号集； 6 ：q 一q 【o 1 】是状态转移函数： 6 ：q 一q 【0 ，1 】 ( q ，a ) 一6 ( q ，a ) = ( g ，“) ，【o ，1 】： q o ( 是初始状态； f q 是终止状态集。 口 定义l 3 21 2 0 一个非确定型模糊有限状态自动机是一个五元组肘= ( a ，玩如，f ) 所表示的系统，其中： q ，q o ，f 与确定型模糊有限自动机相同，而： 6 ：q e 一2 q 。【o ，1 1 是状态转移函数。 口 确定型和非确定型模糊有限自动机都称为模糊有限自动机。 定义1 3 3f 2 5 】一个m e a l y i p j 模糊有限自动机是个五元1 4 i m m = ( q ，e ，6 。a ) ，其中： h x l e i 9 1 6 3 c o m 第7 页，共3 f 顷 毕业论文 第一章预备知识 口 q 为有限状态集； 为有限输入字符集； 为有限输出字符集： 6 ：q x 一f ( q ) 为模糊转移函数； a ：q 一，( ) 为模糊输出函数。 满足以下两个条件： ( 1 ) v q q ，z ，却q ，s t 6 ( q ，z ) ( 0 = 3 y ，s t a ( g ，z ) ( 暑，) 0 ； ( 2 ) v 鼋日，z e ，却a ，s t a ( 吼z ) ( 掣) 0 = 劫q ，o ，t 6 ( g ，z ) ( 力 0 我们用p 和分别表示和上所有有限长度的字符串的集合表示空 字符串，对任意z e ，y p ，和酬分别为字符串七和y 的长度。 就输入字符串而言f 9 】 ：q p r ( o ) 2 i ，： d ( 口，z n ) ( q ”) = v ( q ，z ) ( q ) a6 ( 吼d ) ( ，) 】。 a ：q p f ( z x + ) a c 。，c ”，2 ：三：i ；。或矽。，七。 a 。( g ，z 口) ( 可6 ) = vp ，( g 。，z ) ( y ) ( f ，。) ( g ) a x ( q ，( 6 ) l = a ( q ，士) ( ) a v 【扩( 口7 ，z ) ( g ) aa ( q ，口) ( 6 ) 】) 。 其中g ，口”q ，o ，b a ，z e + ，y a + 。 定义1 3 4 【2 7 】一个字母表上的m i 2 u m o t o 自动机是一个系统a = ( s 霄， f ( a ) l a ) r c ) ，其中： s = s 1 ，8 2 ，s 。 是一个非空的有限状态集： 7 r 是一n 维模糊列向量，即是7 1 = 竹( s d ，7 r ( 勋) ，丌( s 。) ) ，其中：0 r r ( s i ) 1 ，1 isn ，称为模糊初始向量； h x l e i 9 1 6 3 c o r n第8 页洪3 9 页毕业论文 第一章预备知识 g 是s 的一个子集( 终止状态集) ； ，7 g = ( 町( 5 1 ) ，7 ( s 2 ) ，叼( s 。) ) 是一n 维行向量，它的第i 个元素为1 若s g ，否则为0 ； 任意口e ，f ( 盯) 是n 阶模糊矩阵( 称为a 的模糊转移矩阵) 满足f ( a ) = i i 正 ，( 盯) ，1s i n ， j ，l 设f ( 口) 的元素厶。“( 口) 为厶( 5 “以勺) ，其中勺s 口e 。， 是一个映 射， ：s exs i o ，1 1 称为模糊转移函数。对任意5 ，墨f ，厶( s ，仃，t ) 表示从状态s 到状态t 当输入字符口时的转移值。 口 h x l e i g 1 6 3 c o m 第9 页，共3 9 页 单业论文 第二章 m e a l y 型模糊有限自动机在弱等价条件下的最 小化方法 2 1 问题的产生 模糊有限自动机的状态最小化问题在模糊有限自动机的理论和应用方面 都占有极其重要的地位。m e a l y 型模糊有限自动机即是一类有输出没有初始状 态的模糊有限自动杌，它的最小化问题可能被应用到理论物理和计算机科学 中【7 】迄今为止。已有几种不同的m e a l y 型模糊有限自动机，它们都已获得 相对合理的模糊转移函数和模糊输出函数之间的关系。 受到d s m a l i k ，j n m o r d e s o n ，m k s e n 【2 5 】的启发，并在程伟和莫智文 9 1 的研究基础上，重新定义了状态等价的概念这种等价状态被扩展到了依赖 字符串长度而非字符串本身的一种弱等价状态，使其具有更广泛的应用性。 并在弱等价条件下，讨论了m e a l y 型模糊有限自动机的性质，进而确定了它的 最小化自动机的形式，最后给出了相关算法。 2 2 在弱等价条件下的m e a l y 型模糊有限自动机 定义2 2 1 m e a l y 垂d 有限自动机。详见第一章。 定义2 2 2 m e a l y 型模糊有限自动杌。详见第一章。 口 口 定理2 2 11 9 m = ( o ，e ，a ，民a ) 是- - m e a l y 型模糊有限自动机，则任 意q o ，f a + ，z + ，若iz i 1 分l ，那么”( 口，z ) ( 们= 0 。 口 也即是说”( q ，。) ( g ) 1 3 , 那么i 。i = lyf 。鉴于此，本章讨论的都是 zf = fl 的前题下，自动机的模期输出函数。 定义2 2 3 设m = ( q ，最，九) 是m e a l y 型模糊有限自动机，i = 1 ，2 ，口i 0 f ，i = 1 ，2 ，则： 第l o 页，共3 9 页 第2 - im e a l y 型模糊有限自动机在弱等价条件下的最小化方法 ( 1 ) q a 和口2 弱等价( 9 1j - - 啦) 铮任意z ，存在唯一z p 和z 对 应，使l l = i 。l 且a ：( 啦，z ) ( 3 ，) = a ：( 啦，z ) ( ) ，同时存在唯一伽p 和z 对应， 使izl - i i 且是( 仍，z ) ( ) = x ( 口l ，t j ) ( ) ( 2 ) 对每一个正整数量，q l 和驰七一弱等价( g l 兰啦) 甘任意z p ，izi k ，y ，存在唯一z + 和z 对应，使lzi 1zi 且a ：( 口l ，z ) ( 可) = a ：渤，z ) ( ) ， 同时存在唯一”p 和z 对应，使f 。| _ i ”i 且砖( 9 2 ，。) = 墨( q l ，”) ( 分) ( 3 ) 和弱等价( ea 如) 营任意q l p t ，存在q 2 q 2 ，使吼；如并且 任意q 2 q 2 ，存在q l q 1 ，使q 25q t ( 4 ) 对每一个正整数k ，m 1 和m j 一弱等价( m 暑女肘j ) 铮任意q l q 1 , 存 在啦口2 ，使9 1 三i 啦，并且任意口2 q ，存在q l 0 1 ，使口25 q 1 口 若竭= 磊岛= m ，则弱等价；和蠡一弱等价5 女都是等价关系，满足自反 性、对称性和传递性。自反性和对称性显而易见。以下证明传递性是成立 的。 定理2 2 2 设m = ( q ，最a ) 是m e 出型模糊有限自动机，任 意q l ，q 2 ，9 3 q ，q le 口2 ，q 2 暑q a 。则有9 1 5q a 。 证明： q x 2 q 2 ，则任取z p ，y ，存在唯一o 和对应，使izl = i zi 且( q l ，z ) ( ) = ，z ) ( ! ，) ，又q 2 兰q a ，则存在唯一口和z 对应， 使i 口i = i ：i 且( 口2 ，2 ) ( y ) = ( 驰，口) ( ) ，所以，任取z p ，可，存在唯 一a p 和石对应，使izi = iai 且( q l ，$ ) ( ) = a 7 ，q ) ( y ) 。 同理铅5 啦，则任取z p ，y ，存在唯一p p 和z 对应，使lzl = i pl g ( ( q 3 ，z ) ( ) = ( q 2 ，p ) ( 掣) 。又口2 暑q l ，则存在唯一7 p 和口对应， 使i1i = i 卢i 且( q 2 ，卢) ( ! ，) = ( q l ，7 ) ( 掣) ，所以，任取z p ，存在唯 一，y p 和。对应，使i 霉i = i7i 且a ( q 3 ，霉) ( 9 ) = ( q l ，1 ) ( 口) 因此q l 兰q a ，故 传递性成立口 弱等价；和一弱等价；t 都为等价关系，我们记对应于等价关系三和兰k 的 划分依次为q 三和0 三i 。 t 1 ) c i i e i 9 1 6 3 c o m 第1 l 页，共3 0 页单韭论文 第二章m e a l 3 型模瑚有限自动机在弱等价条件下的最小化方珐 定义2 2 4 设m = ( q ，e ，正a ) 是m e a l y 型模糊有限自动机，设p i q 口，那么： ( 1 ) p 和q 是不可区分的营p 三q 。否则p 和q 称为是可区分的 ( 2 ) 如果任意p ，口q ，p 三q 号p = q ，则m 是一个状态最小化的自动机。 ( 3 ) 如果存在一个输出字符串妒，任取z ，使得izl = i2l ， 有，。) ( y ) ( g ，z ) ( f ) 或( g ，z ) ( ) a ( p ，2 ) ( y ) 成立，则称字符串z + 可 以区分状态p 和q 口 2 3 最小化m e a l y 型模糊有限自动机及其算法 定理2 3 11 9 设m = ( q ，e ，6 ，入) 是一个m e a l y 型模糊有限自动机 则1 ( a ) 与2 ( a ) 等价，1 ( b ) 与2 ( b ) 等价： 1 ( 8 ) v q q ，z e ，却q ，5 t j ( 吼。) 0 = 争3 y ，s t 4 ( q ，z ) ( 0 ： 1 ( b ) q ，z ，3 y ，s t 4 ( q ，z ) ( 1 ，) = 劫q ，s t 6 ( 口，z ) 0 ) o ； 2 ( a ) v 口q ，z e ，却q ，s t ( 吼z ) 0 ) 0 兮b y ，& t ( 甄z ) 0 ) 0 ： 2 ( b ) 均q ，z e ，j f a ，s t a ( g ，z ) ( y ) = 争3 p q ，s ( 口 o ) f r ) 0 口 所以，我们在讨论和证明一个模糊有限自动机是m e a l y 型模糊有限自动机 的时候，可以用2 这种形式。 定理2 3 2 设m = ( q ，e ，5 ， ) 是一m e a l y 型模糊有限自动机，那么存 在一个状态最小化的m e a l y 型模糊有限自动机和m 弱等价，其中 k = ( q 三，e ，靠，a 。) ，对任意 q 】，纠q 三，z p ，可，我们定义： 靠( m ，g ) ( 纠) = v ( 5 ，z ) ( 亡) ls ，t q ，g 三8 ，p 兰t ，存在难一； + 和x 对应，使lxi - i ：i ，( 口，) ( f ) = a ( s ，z ) ( ) ，存在唯一叫e + 和z 对应， 使jzi = iwi ，a 0 ，z ) ( ) = a ( g ，叫) ( g ) ， h x l e i 9 1 6 3 锄 第1 2 页，共3 9 页毕业论文 第= 章m e a l y 型横期有限自动机在弱等价条件下的最， 化方法 a ，仇( 【口】，2 7 ) ( y ) = v ( 5 ，2 ) ( ) ls 0 ，g 三s ，存在唯一2 和z 对应， 使l 霉i = 1zi ，a ( 口，z ) ( ) = ( s ，z ) ( y ) ，存在唯一 和z 对应，使izi = 1 枷 ，( s ，2 7 ) ( y ) = ( 吼w ) ( 口) ) 。 证明： 首先证明j l 是一个m e a l y 型模糊有限自动机。 设【口】q i ，2 7 p ，存在纠q 三，使得矗( i 叮】，2 7 ) ( 1 p ) 0 ，由 的 定义，存在s ，t q ，j 三口，兰p ，使( s ，：) ( t ) 0 ，i 正i = l2j ，。p 和z 唯 对应，对于任意可。有a ( q ，z ) ( 可) = ( s ，。) ( 口) ，由于肘是- - m e a l y 理j 模糊有限自动机，所以存在，使一( 5 ，2 ) ( 鲈) 0 ，所以矗( m ，2 7 ) ( u ) 2 ( s ，：) ( g ) 0 。 设【q 】q ，。p ，存在使得a ，m ( 【g 】，窭) ( g ) o ，由 的定义，存 在5 q 8 兰g ，唯一存在z 与z 对应，使izj = i2 ，且( s ，z ) ( 萝) 0 ，对 于任意，有( q 2 7 ) ( u ) = ( 5 ，2 ) ( f ) ，由于m 是一个m e a l y 型模糊有限自 动机，所以，存在t q ，使( s ，2 ) ( f ) 0 ，所以矗( 【口l ，z ) ( 2 ( s ，z ) ( ) e 。 所以， 是一个m e a l y 型模糊有限自动机 下面证明 是状态最小化的m e a l y 型模糊有限自动机。 酬，q 兰，嘲i 【讲。设p 三8 2 ，则任意，9 a ，存在唯 一免p 与z 对应，使lzi - iz 2j ，且( s 2 ，z ) ( ”) = ( 矶。2 ) ( ) 由a 。的 定义，存在s l q ，s lip 且a 二( 嘲，勿) ( f ) = ( s 1 ，卢- ) ( g ) ，i2 2i = l 口ii ， 且勿和岛难一对应。在s 1ip 的条侔下，由钇和p l 对应的难一性，我们 有扫，勿) ( 9 ) = ( s l ，风) ( y ) 又已知训em ，存在唯一丸e 和砘对 应，使iz 1l = i 7 2l 且a l ( 酬，勿) ( y ) = 矗( 【叮】，乱) ( 可) ，由a 。的定义，存在t l 口，t l iq ，且a ，m ( ，卸) ( ! ，) = ( t l ，卢) ( g ) ，i z li = ipi 且2 l 和口唯一对应， 所以，任意z p ，a ，存在唯一p p 和z 对应，使i 正i = lpl ， 且a ( 8 2 ，z ) ( ) = ( t l ，卢) ( ) a 同理，由于t 1 兰口，则任意z p ，f 。，存在唯一幻p 与z 对应， 使lzi = iz 3i ，且( l 2 7 ) ( u ) = ( 口，幻) ( ) 由a 。的定义，存在2 q ，屯e b x l e i 9 1 6 3 锄 第1 3 页，共3 9 页 毕韭论文 第二章m e a l y 型横棚有限当动机在弱等价条等下的最小化方洼 口且a 二( 口】，幻) ( 暑，) = ( t 2 ，饥) ( ) ，iz 3 | _ l7 li ，且铂和7 - 唯一对应。在t 2 三g 的条 件下，由幻和7 l 对应的唯一性，我们有( 口。幻) ( ) = a ( t 2 ，饥) ( 3 ，) 。又已知嘲三 【q 】存在唯一锄p 和对应，使f 加f _ l i 且矗( 【9 1 ，忽) ( 可) = a 二( 纠，埘) ( ) ， 由k 。的定义，存在8 2 q ，8 2 三p ，且a ，m ( 嘲，铷) ( v ) = x ( s 2 ，1 ) ( ，l i = 叫i 且7 和叫唯一对应，所以，任意z p ，y ，存在唯一7 e 和z 对 应，使lzf = i7i ，且a 。( t l ，z ) ( y ) = x ( 3 2 ，7 ) ( p ) 因此t 1 三8 2 ，进而p 兰q ，纠= m 故尬。是状态最小化的m e a l y 霆d 模糊有限 自动机。 对任意q q ，z e ，! ，a ( 叮，z ) ( ! ，) = v a ( 以2 ) ( y ) is q ，q 三 s ，存在唯一= p 和z 对应，使l 孑j - 121 ，( 吼z ) 【= ( s ，：) ( 们，存在嚯 一t ，p 和对应，使l 工i = i 加i ，a 7 ( s ，z ) ( ) = ( q ，叫) ( y ) ，= a ，m ( m ，。) ( ) 。所 以口兰【口】，即：m = m 。 口 定理2 3 3 设m = 旧，五a ) 是一m e a l y 型模糊有限自动机，iqi = n ，l | _ m ，则任意两个可分的状态能够被某个长度至多为( m n 2 ) 舻+ 1 的字符 串所区分。 证明： 任取吼，口j q ，那么任意z p ，暑，x + ，存在唯一。和x 对应， 使ixi = jzj 且慨，$ ) ( ) = a ( 口j ，：) ( 功，同时存在唯一卸+ 和。对应， 使l 士l = 【”i 且( 劬，z ) ) = a ( 啦，叫) ( 挈) t 吼三口j 争( 啦，石) ( ) = ( 彩，z ) ) 且( 田，z ) 0 ) = a ( 吼，埘) b ) 设z = 一z ，暑，= 矿姚，2 = ，埘= w h ，其中z 7 ，t ，e ，矿 ，z h ，z h ，t e ，溉，l = ft l = l l = izi l ，l 矿i = ly l 一1 由定义： a ( g ，z ) 0 ) = a ( 岱，一) ( 暑，) a v ( 吼，z ) ( r ) aa ( z ) ( 讹) jr 口， = ( 儡，一) ( 矿) ( 一) oa ( z ) 】讷， 父( 承， ) b ) = 强，t l ，) ( 矿) ( ) 。天h ) 】诡， ( 劬，z ) ( g ) = a ( 毋。一) ( 矿) a ( 一) oa ( “) 】批， ( 劣，z ) ( 暑，) = ( 劬，一) ( 矿) ( 一) oa ( 钰) 】弘。 h x l e i 9 1 6 3 c o i n 第1 4 页洪3 1 j 页 毕业论文 第二章m e a l y 型模期有限自动机在弱等价条件下的最，卜化方法 则哦兰g j 曹( 叮 ，z 7 ) ( 可) = ( 毋，2 ) ( 掣) 且( 毋，一) ( y 7 ) = a 。( g i ，埘) ( 3 ，) ，同 时【矿( z ) oa ( z ) 】。h = 陋( 一) oa ( 铂) 】衲且【( 2 ) oa ( 研) l j = 【( t ，) oa ( t t ， ) 】l 。