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

模糊有限自动机及其最小化算法研究 运筹学与控制论专业 研究生：胡红莉指导教师：莫智文 摘要 本文在模糊自动机理论的基础上，研究了模糊自动机的最小化约简问题和 模糊属性自动机识别过程。 本文第一章给出了经典模糊集、自动机和模糊自动机的一些相关基础理论。 第二章提出了一种新的不完全的增加结构算法，该算法结合了非循环确定模 糊自动机的性质。由于该算法与隶属度有关，因此算法给出了与传统方法不同 的运算函数，而且通过构造模拟状态使该算法可在有多输入状态( 混淆状态) 的条件下运行。所以这个新的不完全增加结构算法较传统算法更可行和实用。 第三章对应于一般的推广化自动机，新建立了关于推广化模糊有限状态自 动机f g a 的概念；而且根据这类模糊自动机的相关性质，给出与自动机的最小 化算法。这个新算法包括两部分：第一部分是合并模糊自动机中的等价状态； 第二部分是移出模糊自动机中的最大非循环子图中的状态。 第四章根据分明自动机的等价分类，通过重新定义模糊自动机识别过程， 使得模糊自动机的识别过稷与一个合成模糊变换( c f 变换) 一致，而且得到了 尊重合成模糊变换的最粗分类即为状态集的最粗等价分类这一重要结沦。在对 尊重合成模糊变换的最粗分类的讨论中，给出了找到尊重合成模糊变换的最粗 分类的有限步算法，也即是状态集的最粗等价分类和最小化模糊自动机的算法。 该算法不仅给出了最长运算时间，而且还给出可终止算法的条件。使得运算更 为可行和简便。 1 第五章首先介绍了属性文法与模糊埔性自动机的相关理论，而且给出模糊 属性文法的新定义及与其对应的模糊属性自动机，其对字符串进行识别的过程 为：首先建立了以标准字符串为核的隶属函数，通过模糊属性自动机将标准串 中有各字符的隶属度用给定的隶属函数求出，而对于有多个识别结果的识别过 桴，可通过财其隶属度进行格比较，从而得到最佳的识别结果，在实际应用中 是切实可行。能达到识别过程中识别率高、识别结果精确的目的， 关键词：模糊集理论；隶属度；模糊语言：模糊自动机；状态最小化算法； 状态等价：不完全增加结构：推广化模糊自动机：菲循环状态；最大菲循环子 图；模糊变换，合成模糊变换：分类；模糊属性文法；模糊属性自动机；欧几 里德贴近度 2 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 ( f a ) ，t h en e wa l g o r i t h mo f m i n i m a l f u z z ya u t o m a t a a n d f u z z ya t t r i b u t i v ea u t o m a t a a r ec o n c e r n e d i nc h a p t e r1 ，t h ec o n c e p t i o n so f f u z z ys e ta n d f u z z ya u t o m a t a a r e g i v e n i nc h a p t e r2 ，w ep r e s e n tan e ws e m i i n c r e m e n t a la l g o r i t h m ，w h i c hc o m b i n e d w i t hp r o p e r t i e so fa c y c l i cd e t e r m i n i s t i cf u z z ya u t o m a t a b e c a u s et h ea l g o r i t h mi s r e l a t e dw i l hf u z z ym e m b e r s h i p 、w ew o u l dp r e s e n ts o m en o v e lf u n c t i o n sw h i c hm a k e t h en e w m g o f i t h r nd i f f e r e n tt og e n e r a la l g o r i t h ma n dm o r e o v e ri tc a l lb eu s e di nt h e c o n d i t i o nw h i c ht h e r ea r e m u l t i i n c o m i n g ( t r a n s i t i o n s ) s t a t e sb ya p p l y i n g b m l d - i m i t a t es t a t e s ot h en e ws e m i i n c r e m e n t a la l g o r i t h mi sm o r eu s e f u la n d p r a c t i c e d i nc h a p t e r 3 ，w ee s t a b l i s hs o m ec o n c e p t si nf u z z yg e n e r a l i z e da u t o m a t a ( f g a ) w et h e n p r e s e n t an e w a l g o r i t h m ，w h i c hw o d d c a l c u l a t et h em i n i m a lf u z z y g e n e r a l i z e da u t o m a t a ( f g a ) t h e n e w a l g o r i t h m i sc o m p o s e do f t w o p a r t s ：t h ef i r s ti s c a l l e de r e d u c t i o n ，w h i c hc o n t r a c t ss t a t e st h a ta r ee q u i v a l e n ta n dt h es e c o n di sc a l l e d r e - r e d u c t i o n ，w h i c hr e m o v e s s t a t e sw h i c ha r ei nt h em a x i m a l a c y c l i cs u b g r a p h i nc h a p t e r4 ，w en o to n l yg i v ean e wd e f i n i t i o no ff u z z yf i n i t ea t t t o m a t a , o f w h i c ht h es t a t et r a n s i t i o na c c o r d sw i t hac o m p o u n d f u z z yt r a n s i t i o n ，b u ta l s op r e s e n t a ni m p o r t a n tc o n c l u s i o nt h a tt h ec o a r s e s t r e s p e c t i n gc o m p o u n df u z z yt r a n s i t i o n p a r t i t i o no fs t a t e si ss a m ew i t ht h ec o a r s e s te q m v a l e mp a r t i t i o n i nt h ed i s c u s s i o no f c o a r s c s tp a r t i t i o n ，w e 百v ea na l g o r i t h mr e s p e c t i n gc o m p o u n df u z z yt r a n s i t i o nw h i c h w o u l db ea p p l i e dt og e tt h ec o a r s e s tr e s p e c t i n gc o m p o u n df u z z yt r a n s i t i o np a r t i t i o n o f c o u r s e ，t h ea l g o r i t h mg i v e st h er u n n i n gt i m ea n dt e r m i n a t i n gc o n d i t i o n s oi ti s m o r eu s e f u la n d e a s y t oi m p l e m e m i nc h a p t e r5 ，t h ec o n c e p t so ff u z z ya t t r i b u t i v e r e g u l a rg r a m m a ra n df u z z y 1 a t t r i b u t i v ea u t o m a t aa r ci n t r o d u c e d i n r e c o g n i z i n gp r o c e s s t h ef u z z ya t t r i b u t i v e a u t o m a t ac a nd e p i c tt h ed i f f e r e n c eb e t w e e nk n o w ns e n t e n c e sa n d u n r e c o g n i z e d s e n t e n c e s t h e r e f o r e ，i th a sw i d ea p p l i c a t i o n k e yw o r d s ：f u z z ys e t ；d e g r e eo fm e m b e r s h i p ；f u z z yl a n g u a g e ；f u z z yf i n i t e a u t o m a t a ；e q u i v a l e n ts t a t e s ；s e m i i n c r e m e n t a la l g o r i t h m ；f u z z yg e n e r a l i z e da u t o m a t a ( f g a ) ；a c y c l i cs t a t e s ；t h em a x i m a la e y c l i cs u b g r a p h ；c o m p o u n df u z z yt r a n s i t i o n ；s e t p a r t i t i o n ；f u z z ya t t r i b u t i v er e g u l a rg r a m m a r , f u z z ya t t r i b u t i v ea u t o m a t a 4 引言 随着科学研究的不断深入，数学已不再仅作为一门基础学科被研究，其应 用范围广全科学研究的各个领域。研究的对象越来越复杂，变量越来越多，要 求对系统的控制精度越来越高，丽复杂的系统工程是难以精确化的，这t ；不确 定性与数学的精确性就形成了十分尖锐的矛盾，甚至当一个系统的复杂性增大 时，使它精确化的能力将减小，不确定性已达到一定阈值之上时，具有精确性 的数学理论将在系统控制方面完全失效。 针对这一问题，1 9 6 5 年，z a d e h 教授发表了模糊集合论，提出了用“隶 属函数”这个概念来描述现象差异的中间过渡，从而突破了古典集合论中属于 或不属于的绝对关系。这一开创性的工作，标志着数学的一个新的分支模 糊数学的诞生。模糊数学是研究模糊现象及其概念的新的数学分支学科，所研 究的事物的概念本身是模糊的，即一个对象是否符合这个概念难以确定，这种 由于概念外延的模糊而造成的不确定性称为模糊性。用在 o ，1 】上取值的隶属函 数就描述这种模糊性。模糊集合是客观存在的模糊概念的必然反映。模糊概念 就是边界不清晰，外延不确定的概念。以模糊集合代替原来的经典集合，把经 典数学模糊化，便产生了以模糊集合为基础的模糊数学。 句法模式识别在文字识别、语言识别以及人工智能等领域起着重要作用， 有限状态自动机不仅是完成这工作的重要工具，更是描述许多重要硬件和软 件的有用模型。如：字符串匹配算法( k m p ) ；词法分析器；设计和检验数字电 路行为的软件；其他一些软件，如通信协议验证。近几年来，随着模糊技术的 e 速发展，由模糊理论和自动机结合构成的模糊有限状态自动机和模糊语言， 在其应用及进一步发展中，不仅合理地拓展了分明有限自动机和语言理论，而 且已被应用于更广泛的领域，如学习系统( 神经网络) 和数据库理论( 心电图 识别) 等。 模糊有限自动机是模糊集理论和自动机理论成功结台的一个较为典型实 例。模糊有限自动机在其应用过程中，常以设计工具的形式出现。作为一个设 计工具，对于其价值的判别关键在于是否可以提供一种设计指引使设计者可以 得到最佳的设计方案。而其中最重要的一个判断标准既是设汁的最简化，即状 态的最小化约简。由此可见，模糊有限自动机的状态最小化约简问题在模糊有 限自动机的理论和应用方面占有极其蘑要的地位。迄今为止，这方面的研究文 献却有一定的局限性。b s s a t o n s 4 在他的文献中曾对最大最小型模糊有限自 动机的约简问题进行过深入的探讨，并为此发展了一种最大最小代数，提出了 各种不可约简和最小化的判据。但由于其状态最小化的算法较难理解和实施， 使研究结论在应用领域中有很大的局限性。d s m a l i k 、j n m o r d e s o n 与m k s e l l 5 也对他们提出的那种模糊有限自动机的状态最小化问题进行了讨论，但著 未给出一个详细的状态最小化算法。而且随着模糊理论和自动机更为广泛的应 用，以上讨论的模糊自动机已不能完全满足其应用的需求。k k i r t h i v a s a n 和 k s h a r d a 1 8 就提出了模糊w 自动机的橛念( 带输出的扩张化模糊自动机) ， 却未涉及到对其最小化问题，而且对无输出的扩张化模糊自动机亦未讨论。 针对以上问题，本文的总体目标如下：总结以前工作的前提下，尽量完善 各种典型模糊有限状态自动机的状态最小化约简问题，在改进算法的过程中， 将面向其应用的广泛性，使算法更易操作和解读；将目前一些新的设计工具运 用到最小化算法中，将模糊自动机识别过程推，。到一个动态的领域【1 3 ，1 4 l ；针对 目前新提出的模糊w 一自动机和其他模糊自动机，提出了扩张化模糊自动机的定 义及一些相关性质，同对还给出了这类模糊自动机最小化算法0 8 。最后作者还 对模糊属性自动机进行了一些研究，并定义了新的属性算法。具体工作如下简 介： 众所周知，作为一个设计工具，模糊自动机不仅要求能达到最小化，而且髓着 待以别集的不断更新，这就要求模糊自动机在不断增加结构的时候仍要保持其 最小化的性质。第二章中提出了两种算法：增加模糊字符串到非循环确定性模 糊自动机和最小化前者得到的模糊自动机【1 2 】。为了构造最小化模糊自动机 ( a d f f a s ) ，在算法中运用了不完全增加结构技术，增加结构算法是以最小化 为前提的，所以称其为不完全增加结构算法。这种算法曾在一些论文中引用过 1 3 ，1 4 ，但这些文章一般只考虑传统的分明自动机，为了得到增加结构后的最小 化模糊自动机，文中将传统的不完全增加结构技术和模糊集性质结合起来讨论。 天于不完全增加结构算法的工作，在以前总是要限定避免多输入状态的问题( 在 些文中称为混淆状态) 【1 5 l ，但在实际问题中，这种多输入的状态总是存在的， 特别是在最小化臼动机中，奉章中的新方法却能应用于有多输入状态的自动机。 因此文中的方法不仅可被广泛应用，而且也易_ 丁操作。新算法南两部分构成： 增加模糊字符串到最小非循环确定模糊自动机( a d f f a s ) 和最小化增加模糊字 符串后得到的自动机。在增加模糊字符串到最小非循环确定模糊自动机的过程 中，运用了一些相关的新函数，其可使模糊自动机仍然是确定的，而且没有增 加任何无关的字符串到自动机的可识别语言中。 第三章中给出了推广化模糊自动机的定义和一些相关性质，并通过对浚类模 糊自动机的仔细研究，我们发现对这类自动机的最小化问题显然比其他自动机 的要复杂的多。由于其状态转移不再仅局限于单个字符之中，其状态转移已推 广到字符串。从这里就可知，最小化问题不再只局限于寻找等价状态，而是要 推广到寻找最大非循环予图中的状态。也既是说，完成这模糊类自动机的最小 化约简算法要包括对这两类状态的合并和转移。对等价状态我们用等价约简算 法将他们合并；最大非循环予图中的状态我们用非循环约简算法将他们从模糊 自动机中移出。同时，本章中还证明了最小化约简后的模糊自动机所能识别的 语言小变。 通过对已提出的模糊自动机的仔细研究，作者发现模糊集理论在自动机r l 的运用一直都局限于隶属度函数与状态转移函数的结合，面对于其他的模糊集 理论的运用一直都未得到关注。但就实际情况来看，一些模糊集理论的运用对 模糊自动机的研究是很有实践价值的。通过重新定义模糊自动机，使得模糊自 动机的识别过程与一个合成模糊变换( c f 变换) 一致，而且得到了尊重合成模 糊变换的最粗分类即为状态集的最粗等价分类这一重要结论 2 7 1 。在对尊重合成 模糊变换的最粗分类的讨论中，给出了找到尊重合成模糊变换的最粗分类的有 限步算法，也即是状态集的最粗等价分类和最小化模糊自动机的算法。该算法 不仅给出了最长运算时间，而且还给出可终止算法的条件，使得运算更为可j r 和简便。 属性文法与自动机在句法模式识别中有着广泛的应用，利用模糊属性自动 机肘由模糊属性正则文法产生的字符串进行识别，在整个识别过程中建市了以 标准字符串为核的隶属函数，由函数求出的待识别串在标准串中各字符的隶属 度可让我们直观地得到各字符与标准字符的差别，由此可找出待识别串与标准 串差芹最大的标准字符f 3 6 1 。向对多个串的识别结果，又可利用格比较得到与标 准串最相符的待识别串，从而提高字符串的识别率和识别效果。 第一章预备知识 1 1 模糊集合理论基础 1 1 1 模糊集合的概念 模糊集合是没有精确边界的集合，是以逻辑真值为【o ，1 的模糊逻辑为基础 的，它表示的是元素属于集合的程度。其定义为： 定义1 1 ：设z 是对象x 的集合，x 是朋任一元素。肚的模糊集合a 定义为一 组有序对： a = ( x ，。c 如( x ) ) 工x 其中，心( x ) ) 被称为模糊集合a 的隶属函数( m e m b e r s h i p f t m c f i o n l 简称, m f ) 。 瓣为论域，它或者是离散的( 有序或无序) 对象集，或者是连续空间。 定义1 2 ：称a 中满足如下的所有点集为一的核： c o r e ( 爿) 2 t i 以( x ) = 1 ) 如果模糊集合的支集是a 的核并且只有单独的一个点，则称a 为模糊单点。 定义1 3 ：设，( v ) ，丁( d 为集合u 和v 上的模糨集，称映射，：f ( u ) _ f ( y ) 为从到v 的一个模糊变换。 1 1 2 模糊集合的基本运算 定义1 4 ：设a ，b 是同一论域u a ：的两个模糊集合。它们之间的包含、相等 关系定义如卜： a 包含b ，记作a b a ( u ) b ( u ) 以 0 ( 2 ) 任取学q ，a ，若( 毋口) o ，则存存p q 满足万( 玑仃) = p ， j 的扩张函数6 ：q x e _ q 定义如下： j 6 ( 目，8 ) = q为字字符 6 ( g ，a x ) = 6 + ( 6 ( g ，口) ，工)v a e ，石 的扩张函数p ：q x y + - 1 0 , 1 1 定义如下： i r ( q ，8 ) = 1为空字符 l p + ( g ，a x ) = “q ，d ) ( 6 ( g ，口) ，工)v a e ，x + 定义1 3 2 一个模糊有限状态自动机是一个五元组 f a = ( q ，万， i 口 ，g ，叩g ) 其中： q = ( q l q 2 q 。 是一个非空的有限状态集； = q ，心 是一个方船笋觥 z = ，y e q ：，7 r q 是一个聆维模糊向量，称为模糊初始状态，其中 0 1 ，i = 1 ” g q 终止状态集： 刁6 = ，：r q 是一个n 维向量，其中，q ，g 则= l ，否则= o ； 乃= ( a ) 】。是一个露阶模糊矩阵； 称为f a 的模糊变换矩阵，的元素( 4 ) 为“( 吼，口，吼) ，其中吼，q ，q ， 甜，表示当输入字符口时，f a 由宁，状态转到吼状态的隶属度为“口( d ) 。 对于任意个单输入字符a ，自动机的b q 另l j 结果为 “( 口) j 。= ， “( 卯，) ) ，v q ie q ，( 日) = “( 口) 对于任意a ，x + 而言： “4 ( 枷) f 。3 函，) “( 工) “j ( 一) k2 。昌忸4 ( 一) i 。 。 定义1 3 3 模糊有限状态自动机是一个六元组：f a = ( q , z ，e ，q o ，f ) ， 其中： q = ，q 2 q 。) 是一个非空的有限状态集； = f a l , a 2 a 。j 是一个芎蕊笋彩i 每 q o q 为初始状态； f q 为终止状态集； e 9 x q 为状态转边集： ：e f o ，1 1 为状态转移边的模糊函数； 满足以卜条件： ( 1 ) 任取q q ， a ，若存在p q 满足e = ( g ，a ，p ) ，则有 p ( e ) = ( g ，a ，p ) 0 ： ( 2 ) 任取g q ，a ，若1 2 ( q ，a ，p ) 0 ，则存在p e 使得e = ( g ，a ，p ) 。 状态转边集e 的扩张集e + q q 定义如下： e 2 f q t , a ，壤霸+ ； 岛，e n ) ，为e a 中一个长度为”的路径，由一系列边 构成e t = ( 聃，a 。，g j + i ) e ，i = l ，m 字符a i ，n 。边q ，e n 的标注。若q ， 吼f 和p ( p + ) ) 0 则( q ，e 。) 称为= a i ，a n 被f a 识别的路径。 的扩张函数p + ：q = q - - * o , t l 定义如下： f 肛+ ( 吼，g ) = l为空字符 p + ( g ，( ，纠2 z o m ，口，r ) i ( r ，t 力 v 口，x 。 定义1 3 4 模糊属性有限自动机一个七元组：m ，= ( ，g 。，q ，万，“，r ，q 。) 其中： 是具有属性的有穷输入字母表， 即= ( d ，缸) ，( 呜l a 2 ) ( 口，l a , ) ( t a d ； q = 吼，吼，一q 。 是状态有穷集； 万是q 到q 的状态转移函数； q 。q ，为初始状态； q 。q ，为终止状态； u 是变量集，即u = ( “，“：“。) “，( i f 门) 代表标准串的第i 个标准 字符所接受的字符数的隶属度； r ：寸u ，是计算输入串在标准串中各字符的隶属度的隶属词义函数， 即求u 中各变量的值。 第二章增加结构非循环模糊自动机 及最小化算法 在本章中，我们提出了一种新的不完全的增加结构算法，该算法结合了非循环 确定模糊自动机的性质。由丁该算法与隶属度有关，因此算法给出了与传统方 法不同的运算函数，而且通过构造模拟状态使该算法可在有多输入状态的条件 下运行。所以这个新的不完全增加结构算法较传统算法更可行和实用。 2 1 问题的产生 作为一个设计工具，模糊自动机不仅要求能达到最小化，而且随着待识别集 的不断更新，这就要求模糊自动机在不断增加结构的时候仍要保持其最小化的 性质。在本章中，提出两种算法：增加模糊字符串到非循环确定性模糊自动机 和最小化前者得到的自动机。为了构造最小化自动机( a d f f a s ) ，在算法中运 用了不完全增加结构技术，增加结构算法是以最小化为前提的，所以称其为不 完全增加结构算法。这种算法曾在些论文中引用过，但这些文章一般只考虑 传统的自动机，为了得到增加结构后的最小化模糊自动机，文中将传统的不完 全增加结构技术和模糊集性质结合起来讨论。关于不完全增加结构算法的工作， 在以前总是要限定避免多输入状态的问题( 在一些文中称为棍淆状态) ，但在实 际问题中，这种多输入的状态总是存在的，特别是最小化自动机，但本章中的 新方法却能应用于有多输入状态的自动机。因此文中的方法不仅可被广泛应用， 而且也易于操作。新算法由两部分构成：增加模糊字符串到最小菲循环确定模 糊自动机( a d f f a s ) 和最小化增加模糊字符串后得到的自动机。因为在增加模糊 字符串到最小非循环确定模糊自动机的过程中，运用了一些相关的新函数，所 以得到的自动机仍然是确定的，而且没有增加任何无关的字符串到自动机的町 识别语言。 2 2 非循环确定性模糊有限自动机 虽然本章只讨论非循环确定性模糊有限自动机，但它的一些相关算法将，i j 推广到循环不确定性模糊自动机，这些推广在本文中暂不给予讨沦。首先我们 将要给出的是确定模糊自动机的相关定义。 定义2 2 1 个确定模糊有限状态自动机是一个六元组 d f f a = ( q ，巧，麒 7 0 ，) ，其中，q = ( q l 敏，吼 足一个非空的有限状态集；是 一个秀儡户形藉iq 。q 为初始状态；f q 为终止状态集；占：q 哼9 为 状态转移函数；：q x x 斗【0 ，i 】为模糊转移函数；并且满足以下条件： ( 1 ) 任取q q ，口，若存在p q 满足6 ( q ，a ) = p ，则有( q ，a ) 0 ， ( 2 ) 任取q e q ，口，若( q ，日) o ，则存在p q 满足d ( q ，a ) = p ， 其d 的扩张函数6 ：q 。q 定义如下： f 6 国，e ) = q 为空字符 1 6 + ( q ， l r ) 二6 + ( 6 ( q ，口) ，j )v a ，t 其一的扩张函数p ：q x _ 【o ，1 l 定义如下： f p + ( g ，) = 1 1 p + ( g ，m ) ：“9 ，。) 仙+ ( 戳q ，d ) ，x ) 定义2 2 2 设a d f f a = ( q , z ，8 , 1 a ，吼，f ) 是确定模糊有限状态自动机，则其接受 或可识别的模糊语言记为 l ( a d f f a) ，其中集 l ( a d f f a ) 2 ( n ) ，“) f ，6 ( q o ，0 ) ) f ，i t * ( q o ，) = 甜0 。 定义2 2 3 非循环确定模糊有限状态自动机a d f f a = ( q , i ；，6 ，p ，q o ，f ) 为完全 模糊自动机，若6 和“为完全转移函数。 定理2 2 1 设a d f f a = ( q ，6 ，q 。，f ) 是确定模糊有限状态自动机，则必然存 在一个完全模糊自动机a d f f a = ( q u 上，6 ，疋q 。，f ) ，使得l ( a d f f a ) = l ( a d f f a ) ，其中上为吸收状态。 证明：假设a d f f a 。中的8 + 和h 对于吸收状态_ 的定义如下 f6 ( q ，口) = 上 j6 ( - l ，口) = lp ( 啊) = 0 f ( i ，= 0 6 ( g ，口) 未定义 v 6 ( g ，未定义 v 口 显然，如果我们按照这种方法去改进原自动机中的6 和p ，则l ( a d f f a ) 必 然不会改变。这个定理也告诉我们任何自动机都存在一个完全自动机与其等价， 所以在本章及后面几章中，我们只需考虑完全自动机即可，这样我们所得算法 不仅不失一般性而且有利于算法的实现。 2 3 a d f f a 的不完全增加结构 不完全增加结构算法包括两部分：增加模糊字符串到模糊自动机和最小化 增加字符串后的模糊自动机( a d f f a s ) 。 一般而言，增加模糊字符串到模糊自动机有两种方法，第种方法：在模糊 自动机中简单地从初始状态吼构造全新路径。这样得到的自动机将不利于我们 在第二步中对自动机运用最小化运算。第二种方法：对应m 在自动机中的路径 构造( c o ，声( x ) ) 的新路径。这种方法可相对减少新状态的产生，但在与缈相对应的 路径中若出现了多输入状态的情形，第二种算法往往就会出错。在多输入状态 这种情形下，错误的结果便是会使模糊自动机识别一些不属于l ( a d f f a ) 和 ，芦( z ) ) 的语言。 现在，将要提出的这种新算法不仅包括了传统算法的优点，同时也排除了传 统算法的不利因素。新方法是先从初始状态吼开始对应出在自动机中的路径构 造新路径，他将不会产生新状态( 新路径) ，直到多输入状态出现。为了保证自 动机的确定性和避免多余模糊字符串被接受，当多输入状念9 出现时，可构造一 个命名为模拟状态q 的新状态，模拟状态q 将模仿多输入状态q 以后的所有路 径。具体算法如下： f u n c t i o n a d d f i t z z ys t r i n g ( c o = a t a ：吼，i ，( m ) ) ，+ - l g _ w h i l ei l d o l 矿1 埘“m 一”。m 1 “g5 t e ( q ， 一i ) j ( 可， ) 上 ( q ，气) 一( 棚) b u i l d i m i t a t i n g ( q ) i fq c f f 一f ub u i l d i m i t a t i n g ( q 、 j ( q o ，a i q j ) _ b u i l d i m i t a t i n g ( q ) e l s e 归a l la a i d ( b u i l d i m i t a “n g ( q ) ，a ) * - - d ( q ，) i t ( b u i l d i m i t a t i n g ( q ) ，a ) + - - m ( q ，a ) e a f o r “d 一 q c - b u i l d i m i t a t i n g ( q ) q 七- o uq a ( q ，) t - - b u i l d s t a t e ( q ，a i ) 卢( q ，) 、( 印) q b u i l d s t a t e ( q ，d ) j t j + 1 q - q u q e l s ei f j ( 宁，0 ) 上 ( g ，0 ) ( 出) g d ( 9 ，q ) “一+ 1 e l s e d 积a i ) 。, - - b u i l d s t a t e ( q ，q ) 卢( 叮，q ) + 一( m ) q - - - q u q f 十一f + l e n d i f e n 以w h i l e f - f u q 憎。“脚一帅叫( q ，z ，万，) e n d f u n c t i o n 6 f u n c t i o nm u l t i i n c o m i n gs t a t e ( q ，d h ) 知ra l la 一a i 一1 i f | p e q ：8 ( p , a ) = q r e t u r nt r u t h e n d f o r r e l u r nf a l s e e n d f u n c t i o n 显然，结论最后所得的模糊自动机不是最小化的。 2 4 最小化自动机 在本节中，将对由上节算法得到的模糊自动机进行最小化算法。在给出具体 运算过程之前，首先给出了两个与运算相关的定义。 定义2 4 1 设a d f f a ；( q ，6 , a ，f ) 是确定模糊有限状态自动机，状态 q q 等价于状态p q ，当且仅当对于任意a ，均有占( g ，口) = a ( p ，a ) 和 f l ( q ，口) ：( p ，口) 。 定义2 4 2 设a d 阡a = ( q ，6 ，吼，) 是非循环确定模糊有限状态自动机，状 态鼋( 艿( q o ，口l a 2 q ) = q ) 称为对于模糊字符串( ，2 ( c a ) ) l ( a d f f a ) 隶属度 多余( 缈。= a l a 2 a n ) ，当且仅当可i 使得( j ( q o ，a l 哦) ，a j + 1 ) = 2 ( 0 2 ) 。 最小化由上节算法返回的自动机有以下两步：首先，由于在不完全增加算法 中得到的新自动机包含了一些新状态，所以得到的自动机一般不是最小化的， 因此总可找到与某些新状态等价的状态( 不在新状态之中) 。如果找到这样的等 价状态，则将它与新状态合并。 其次，虽然有些新状态没有等价状态，但它仍不是最小化自动机，这是因为 如果新状态q 对( 脚，2 ( x ) ) 是隶属度不必要的，并且对所有a ，能找到一个状 态p ( 不在新状态之中) ，使6 ( q ，) = 8 ( p ，d ) ，并且弘( p ，d ) 芦( g ，a ) 。新状态g 将能被状态p 代替，并且不改变自动机的识别结果。函数r e p l a c e a b l e s t a t e ( q ，p ) 将判别新状态窜是否能被状态p 代替。 算法的结构如下： f u n c t i o nm i n i m i z e ( a d f f a ) w h i l ei = l m ld o w n t ol g 。6 ( ，a 1 0 2 a i ) i f 劲9 # g “f v ( n q ) v r e p l a c a b l e ( q ，p ) m e r g e ( q ，p ) f + 一fi e n d w h i l e e n d n o t i o n f u n c t i o ne q u i v ( g ，p ) 矿( q 仨f a p e f ) v ( qe f “p 芒f ) r e t u r n f a l s e f o ra l la i f s ( q ，口) 艿( p ，a ) v a ( q ，口) 。f ( p ，a ) r e l r n 矗l s e e n d f o r r e t u r nt r u t h e n d f u n c t i o n f u n c t i o nr e p l a c a b l e ( q ，p ) f o ra l la i f j ( q , a ) = 占( p ，。) 卢( p ，4 ) 口( 珊) u n n e c e s s a r y 一删p m b p r s h i p ( q ，a i + 1 ) b r e a kr e t u r nt r u t h e n d 一如r r t u r n 如i 5 e e n d f u n c a o n f u n c t i o nu n n e c e s s a r y m e m b e r s h i p ( g ，呸“) p 9 0 k * - - 1 w h i l e = it of o l 矿( 卢r ) 2 一( 印) 量p 1 b r e a kr e l u r ut r u t h p 船 k + l p p d ( p 气) e n d i ， e n dw h i l e r e l u r n 如i s e e n d f u n c t i o n 例：设a d f f a = ( q ，6 扎q o ，f ) 是非循环确定模糊有限状态自动机，其l 卜 = d ，b ，c ，d ，其可识别的模糊语言为：( a a a c c d d ，0 9 ) u ( a a b b b d d ，0 8 ) ，j 和 的定义如图一l 所示。 图一1识别( a a a c c d d ，o , 9 ) l j ( a a b b b d d , o 8 ) 的最小化模糊自动机。 接着我们将根据增加字符串的算法增加模糊字符串 ( a a b b b c c ，0 7 ) u ( a b c c b c ，0 6 ) 到模糊自动机中。 最后，我们将运用最小化算法最 小化增加结构后的模糊自动机。具体运算过程如下图所示： 图一2 增加模糊字符串( a a b b b c c ，0 7 ) 到最小自动机a d f f a ，得到一个可识别 ( a a a c c d d ，0 9 ) 3 ( a a h b b d d ，0 8 ) u ( a a b b b c c ，0 7 ) 的非最小化自动机，其中状态5 为多输入状态，他 以后的路径将被新建的模拟状态( 口，口) 模仿。 幽一3 最小化可识别( a a a c c d d ，0 9 ) o ( a a b b b d d ，0 8 ) u ( a a b b b c c ，0 7 ) 的模糊自动机。 状态9 和 2 为等价状态，合并状态9 和1 2 。所得模糊自动机仍为罪小自动机。 、叼型吗 垭皿弘邺刖虹叫 图5 和图一6 最小化可识别( a a a c c d d ，09 ) u ( a a b b b d d 。0 8 ) u ( a a b b b f c ，o 7 ) u ( a b c c b c ，0 6 ) 的模 糊自动机。状态9 和1 7 为等价状态，合并两状态。状态1 6 可被状态1 1 代替。所得 模糊自动机仍为最小自动机。 第三章推广化模糊有限状态自动机 及其最小化算法 在这一章中，对应于一般的推广化自动机，新建立了关于推广化模糊有限 状态自动机f g a 的概念；而且根据这类模糊自动机的相关性质，给出了模糊a 动机的最小化算法。这个新算法包括两部分：第一部分是合并模糊自动机中的 等价状态：第二部分是移出模糊自动机中的最大非循环子图中的状态。 3 1 问题的产生 对丁一般的模糊自动机的最小化约简问题在一些文章都给出了相关的算法， 但是就推广化模糊自动机的最小化问题还没有人进行过研究。通过对该类模糊 自动机的仔细研究，我们发现对这类自动机的最小化显然比其他自动机的要复 杂的多。由于其状态转移不再仅局限于单个字符之中，所以状态转移已推广到 字符串。从这里就可知，最小化问题不能局限于寻找等价状态，而是要推广到 寻找最大非循环子图中的状态。也既是说，完成这类模糊自动机的最小化约简 算法要包括对这两类状态的合并和转移。对等价状态我们用等价约简算法将他 们合并：最大非循环子图中的状态我们用非循环约简算法将他们从模糊自动机 中移出。同时，本章中还给出了最小化约简后的模糊自动机所识别的语言不变。 3 2 推广化模糊自动机 定义3 2 1 模糊有限状态自动机是一个六元组f a = ( q , z ，e ，吼，f ) 其中： q = q l , q 2 q 。 是个非空的有限状态集： 是个有艰字符表； q 。q 为初始状态； f q 为终止状态集； e q x q 为状态转边集； ：占j f o ，1 i 为状态转移边的模糊函数；并且满足以下条件； ( 1 ) 仟取g o ，a ，若存在p q 满足8 = ( g ，口，) ，则有声( p ) = 声( 叽a ，p ) 0 ： ( 2 ) 任取q q ，a ，若l a ( q ，a ，p ) 0 ，则存在p 仨e 使得e = ( g ，d ，p ) 。 状态转边集e 的扩张集e + q g 定义如下： e 3 吼，q + ，】：( q ，岛) ，为f a 中一个长度为n 的路径，由一系列边 构成q 2 ( 玑，q ，q f + 1 ) e ，仁，月，字符马，口。边p ，e n 的标注。若吼e ， 吼f 及i l ( ，) 0 则( e l ，气) 称为国= a l ，q 被f a 识别的路径。 t 的扩张函数，：q 9 j i o ，1 】定义如下： i ，( g ，q ) = 1为空字符 f “+ ( 玩以力2 ，连 “( 玑岛，) “( ，丘力 v a e e ，工+ 定义3 2 2 推广化模糊有限状态自动机f g a ( f u z z yg e n e r a l i z e da u t o m a t o n ) 是一个六元组f g a = ( q , e ，e ，p ，吼，f ) 其中： q = f q l , 吼，靠) 是一个非空的有限状态集： 是一个有馒- g 搿襄， q 。q 为初始状态； f q 为终止状态集： e c q q 为状态转边集； ：e 斗【o ，1 】为状态转边的模糊函数；并且满足以下条件： ( 1 ) 任取g q ，x e e ，若存在p c ：q 满足z e = ( q ，x ，p ) ，则有( f ) = 4 q ，x ，p ) 0 ； (