（基础数学专业论文）几类自动机的性质探讨.pdf

几类自动机的性质探讨 基础数学专业 研究生杨静 指导教师莫智文( 教授) 论文摘要：本文研究了几类自动机的性质在第一章里，介绍了基本概念在第 二章中，给出了非确定型与确定型初始化格值有限自动机的定义根据这些定 义，讨论了这两类自动机之间的关系，并得到这几类初始化格值有限自动机的等 价性进而，给出了非确定型初始化格值有限自动机与确定型初始化格值有限 自动机等价的充分必要条件在第三章中，基于格半群上研究m i z u m o t o 确定型 格值有限自动机( 记为m i z u m o t od f a ) ，给出了状态等价关系和自动机等价关 系，并表明了一个m i z u m o t od f a 有一个与之等价的最小化m i z u m o t od f a 从这些等价关系，得到了m i z u m o t od f a 的最小化算法在本文的第四章里，给 出了模糊m o o r e 型自动机可逆、可达和完备等的定义，讨论了其相关性质进 而得到这些性质之间的关系，并研究了模糊m o o r e 型自动机的最小化最后，系 统地给出了关于它们的一些重要结果 关键词：格半群；格值有限自动机；等价；最小化；模糊m o o r e 型自动机 第i 页，共3 4 页 i n v e s t i g a t i o no ft h ep r o p e r t i e sf o rs e v e r a lk i n d so f a u t o m a t a f u n d a m e n t a lm a t h e m a t i c s w r i t e r ：y a n gj i n gs u p e r v i s o r ：m oz h i - w e n a b s t r a c t ：t h i sp a p e ri sc o n c e r n e dw i t ht h ep r o p e r t i e so fs e v e r a lk i n d so f a u t o m a t a i nc h a p t e ro n e ，s o m eb a s i cc o n c e p t sa x ei n t r o d u c e d i nc h a p t e r t w o ，t h ed e f i n i t i o n so fi n d e t e r m i n i s t i ca n dd e t e r m i n i s t i ci n i t i a ll a t t i c e - v a l u e d f i n i t ea u t o m a t aa x eg i v e n b a s e do nt h e s ed e f i n i t i o n s ，w ed i s c u s st h er e - 1 a t i o n sb e t w e e nt h e m a n dt h ee q u i v a l e n c e so ft h es e v e r a lk i n d so fi n i t i a l l a t t i c e - v a l u e df i n i t ea u t o m a t aa r eo b t a i n e d m o r e o v e r ，t h es u f f i c i e n ta n d n e c e s s a r yc o n d i t i o n sf o rt h ee q u i v a l e n c eb e t w e e ni n d e t e r m i n i s t i ca n dd e t e r - m i n i s t i ci n i t i a ll a t t i c e - v a l u e df i n i t ea u t o m a t aa r eg i v e n i nc h a p t e rt h r e e w es t u d ym i z u m o t od e t e r m i n i s t i cl a t t i c ef i n i t ea u t o m a t a ( d e n o t ew i t hm i z u - m o t od f a lw i t hm e m b e r s h i pv a l u e si nl a t t i c eo r d e r e dm o n o i d s a n dt h e s t a t e s w i s ee q u i v a l e n c er e l a t i o n sa n da u t o m a t ae q u i v a l e n c er e l a t i o n sa x eg i v e n w bs h o wt h a tam i z u m o t od f ah a sa ne q u i v a l e n tm i n i m a lm i z u m o t od f a f r o mt h e s ee q u i v a l e n c er e l a t i o n s ，am i n i m i z a t i o na l g o r i t h mo ft h em i z u m o t o d f ai so b t a i n e d i nc h a p t e rf o u r t h ed e f i n i t i o n so ff u z z ym o o r ea u t o m a t a ，s r e v e r s i b i l i t y a c c e s s i b i l i t ya n dc o m p l e t i o na x eg i v e n s o m er e l a t e dp r o p e r t i e s o ft h e ma x ed i s c u s s e d 讳乃a 右i sm o r e s o m er e l a t i o n s h i p sa m o n g s tt h e s ep r o p - e r t i e sa r eo b t a i n e d a n dt h em i n i m i z a t ，i o no ff u z z ym o o r ea u t o m a t ai sa l s o i n v e s t i g a t e d a tl a s t ，s o m es i g n i f i c a n tr e s u l t sc o n c e r n i n go ft h e ma r eg i v e n s y s t e m a t i c a l l y k e yw o r d s ：l a t t i c e o r d e r e dm o n o i d ；l a t t i c ef i n i t ea u t o m a t a ；e q u i v a l e n c e ； m i n i m i z a t i o n ；f 皿z vm o o r ea u t o m a t a 四) i i n 范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师芸室塞塾蕉：指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任 何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 j 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印刷 版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库供检 索；2 ) 为教学、科研和学术交流目的，学校可以将公开的学位论文或解密后的 学位论文作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中国学位论文全 文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 杨静 签字日期：2 d f d 年年月8 日 新张软 j 绥7、 签嬲年铲月纩日 引言 1 9 6 5 年，z a d e h 教授【1 】创立了模糊集理论，提出了用“隶属函数”这个概念来描 述现象差异的中间过渡这个理论的提出，标志着数学的一个新的分支一一模糊数 学的产生针对一个对象是否符合事物的概念难以确定时，这种由于概念的外延模 糊而造成不确定性即为模糊性用在i o ，1 】上取值的隶属函数就用于描述这种模糊 性自动机理论是算法分析和描述，计算复杂性理论，可计算性等的研究基础，它为 计算理论提供了可靠的数学模型 利用模糊集的方法来研究自动机理论在2 0 世纪6 0 年代已经开始，w 曲【2 2 0 】首 先将模糊集理论应用于自动机领域，建立了第一个模糊有限自动机随之，模糊集 理论被广泛应用于自动机领域的研究 2 2 - 2 5 在经典的自动机理论中，输入的只是 离散的字符或有限的字符串有穷自动机作为计算机理论中最简单的数学模型，它 不仅是计算机科学的理论基础，为现代计算机理论提供可靠的形式理论，而且与神 经网络等领域有密切的关系，在编译语言等方面也有着重要应用【1 7 _ 1 9 ，3 8 】模糊 自动机提供了一种研究和处理包含模糊性的自然语言的有力工具，它必将成为基于 词的软计算理论提供可靠的形式基础近几年来，随着模糊技术的飞速发展，由模 糊理论和自动机结合构成的模糊有限自动机和模糊语言【3 ，4 ，1 5 ，1 6 ，4 4 4 6 】，在其 应用及发展中，合理地将分明的有限自动机进行推广到目前为止，出现过许多对 模糊自动机和模糊语言的讨论，如见文献 9 1 2 ，2 1 最近，邱道文 1 5 】提出基于完备剩余格值逻辑的自动机理论，李永明 7 】提出取值 于格半群的自动机及其语言的理论，从而提供了多值逻辑意义下研究自动机理论的 方法在文 3 耻4 1 】中提出了格值自动机的理论，从而在更广的框架下，即在格半群 意义下研究自动机理论，把基于词的计算模型建立在更广泛的格值自动机理论之 上那么由于格值自动机和通常的自动机有许多不同之处，而且它能识别更广泛的 形式语言和模糊语言，从而构成格值自动机理论自身的特点在这个领域中，对它 的研究就显得非常重要并且在j e l e n ai g n j a t o v i d 等【5 合著的文章中，提出了初始化 模糊自动机这一概念，但在文f 5 】中，并没有对初始化模糊有限自动机作更细的研究 所以本文的第二章，将在此基础上，对初始化格值有限自动机进行更广、更详细的 第1 页，共3 4 页 引言 讨论 模糊有限自动机是有限自动机的一个推广，它的系统中的下一个状态是不确 定的模糊自动机在其应用过程中，常以设计工具的形式出现正如自动机理论为 现代计算理论提供了可靠的形式理论一样【3 5 ，模糊自动机理论也必将为基于词的 软计算理论提供可靠的保证。作为一个设计工具，对于其价值的判别关键在于是 否可以提供一种设计指引，能使设计者得到最佳的设计方案而其中最重要的一 个判别标准即是设计的最简化，即状态的最小化约简所以，模糊有限自动机的状 态约简问题在模糊有限自动机的理论和应用方面都占有很重要的位置当然，任 何一种识别工具，我们都希望它达到最优的效果，在这里也就是自动机的最小化 问题 3 1 】在文 2 6 】中，作者提出进一步的研究包括m i z u m o t o 格值自动机的最小化 由于m i z u m o t o 格值自动机有确定型与非确定型之分【6 】，因此针对这一问题，本文 展开了对m i z u m o t o 确定型格值有限自动机的研究，探讨其最小化问题，这就构成 了本文的第三章 在讨论了模糊自动机性质之一的最小化问题之后，本文作者回想起刚接触模糊 有限自动机理论这一领域时，就被它各种各样的性质 2 7 - 3 0 所迷惑，能否把它们进 行系统地研究基于此想法，在本文的第四章中，对模糊m o o r e 型自动机的主要特 性进行探讨 具体地说，我们做了如下三方面的工作： 1 初始化格值有限自动机之间的关系 首先，根据初始化格值有限自动机的状态转移函数是否为确定的，将其分为非确 定型与确定型初始化格值有限自动机其次，根据初始状态盯是否为分明的，又分别 将其划分成两类文献 6 1 已证明了几类格值自动机之间的等价关系因此，对这几 类初始化格值有限自动机之间关系的讨论也显得尤为重要本文从一个新的角度， 发现初始化格值自动机和格值自动机有许多不同之处，初始化格值自动机和初始化 模糊有限自动机也有许多不同之处，这就构成初始化格值自动机理论本身的特色 从而，揭示出这类自动机和取值为格半群的代数性质的紧密联系，并表明了这几类 初始化格值有限自动机的等价性 2 m i z u m o t o 确定型格值有限自动机( m i z u m o t o d f a ) 的最小化问题 x q q 2 0 3 1 6 3 c o r n 第2 页，共3 4 页毕业论文 引言 提出了m i z u m o t o 确定型格值有限自动机( m i z u m o t o d f a ) 的概念，给出了模 糊状态转移函数的扩张接着由m i z u m o t o d f a 识别的模糊语言定义状态等价关 系，并给出了自动机的等价关系这些讨论为研究最小化的问题打下了基础，表明 一个m i z u m o t o d f a 有一个与之等价的最小化m i z u m o t od f a 从这些等价关系， 得到了m i z u m o t o d f a 的最小化算法最后，举出阐述这种算法的例子 3 模糊m o o r e 型自动机的性质 首先给出了模糊m o o r e 型自动机的一些基本概念，并概括了模糊m o o r e 型自动 机的性质进而，详细地研究了模糊m o o r e 型自动机的主要特性，如可逆性，可达 性，完备性，最小化等等由此得到了一些重要结果：这些性质之间的关系由等价 关系，得到了模糊m o o r e 型自动机的最小化算法最后用一个例子对该算法进行了 说明 x q q 2 0 3 1 6 3 t o m 第3 页，共3 4 页毕业论文 第一章预备知识 首先给出本文要用的一些基本概念 1 1 格半群及模糊矩阵 定义1 1 1 【8 】设l 为格，v ，a 分别为上确界与下确界运算，0 , 1 分别为最小元与 最大元，为l 上的二元运算( 半群运算) ，且( l ，e ) 为有单位元的半群，若满足 ( i ) l ，a 0 = 0 a = 0 ， ( i i ) v a ，b l ，a b 号v x l ，a z b z 且x a z b ， 则称l 为序半群若满足 ( i i i ) v a ，b ，c l ，a ( bvc ) = ( a b ) v ( a c ) ，( 6vc ) a = ( b a ) v ( c o ) ， 则称l 为格半群进一步，若三为完备格，且 ( i v ) a ( v t b t ) = v t ( a b t ) ，( v t b t ) a = v t ( b t n ) ，则称l 为q u a n t a l e 定理1 1 1 【7 】设( 厶，v ) 为格半群，l 7 为l 的有限子集则由l 7 生成 的( l ，v ) 的子代数l 是有限集的充分必要条件为集合i = 他。z “il i ， l 7 ，1 k 钆，扎0 ) 是有限集 定义1 1 2 ( 【3 2 】) 设l 为格，0 ，1 分别为l 的最小元最大元，v 和a 各自代表l 上 的上确界运算和下确界运算，如果对任意的a ，a l ，a 2 ，a n l 满足以下分配律， 其中n 是一个确定的整数： 冗nn佗 a 八( va i ) = v ( a 八a i ) ，o v ( 八a i ) = 八( avo ) ， 那么称l 是分配格 定义1 1 3 ( 【3 3 】)任意的m 他阶矩阵a = ( n 巧) ，对所有t 歹的值使得o a i j 1 ，那a a 就叫做模糊矩阵 定义1 1 4 【3 1 】设a = ( ) m 佗是mx 几阶的矩阵，如果。巧l ，那么a 就叫 做l 一模糊矩阵 第4 页，共3 4 页 第一章预备知识 1 2 格值自动机及模糊m o 凹e 自动机 定义1 2 1 【6 】格值自动机( 记为l a ) 是五元组虬= ( q ，正仃，t ) ，其中q 为非 空有限状态集，为非空有限输入字符集，5 ：q e f ( q ) 为模糊状态转移函数，其 中f ( q ) 表示q 的格值模糊子集，仃，t f ( q ) 分别为模糊初始状态与模糊接受状态 若5 ：q q _ l 三为格半群，那么心为非确定的格值自动机，若6 ： q _ q ，那么现= ( q 矿，品，o a ，乃) 为确定的格值自动机( 记为d l a ) 定义1 2 2 3 1 】设( 厶，v ) 是格半群，五元组 m 7 = ( q ，f ，i ，t ) 叫做m i z u m o t o 格值有限自动机( 记为m i z u m o t o l f a ) ，其中q ，分别是有限非 空状态集合和输入字符集；f = f o i r = ( 嘞( o ) ) ，口e ，q ，p q ，5 印 ) 三) 是一模糊转移矩阵工一模糊行向量i = ( z 1 ，1 2 ，k ) 是m 的初始状态分布， l 一模糊列向量t = ( z ：，砭，吃) 7 是终止状态的分布 直观地讲，如果用6 ( q ，a ，p ) = ( 口) 来定义5 ：q xq lf 是q ，和q 之 间的l 一模糊关系而且，两个向量i 和t 相当于q 里的元素z f ( ) l ，代表了当前状 态q i ，i = 1 ，2 ，他 设表示在上的所有有限长度的字符集，a 表示空字那么+ 是由产生的相 关双运算的自由幺半群对任意的z e + ，蚓表示z 的长度 m i z u m o t o 格值有限自动机m = ( q ，eq o ，丁) 是确定型的自动机，其中9 0 q 是初始状态，丁是模糊终止状态集，那么m 就叫做m i z u m o t o 确定型格值有限自动 机( m i z u m o t od f a ) 定义1 2 3 ( 【3 4 】) 模糊m o o r e 型自动机是一个五元组： m = ( q ，x ，f ，g ) 其中q = ( 口l ，q 2 ，) 是有限状态集，x = p l ，x 2 ，z m ) 是输入字符集， y = 掣l ，y 2 ，驮) 是输出字符集，f = f ( x ) t f ( x ) = ( 岛( z ) ) ，z x ，q ，p q ) 是 模糊转移矩阵( 也叫做模糊转移函数) ，g = g ( x i y ) i g ( x l y ) = ( 跏( z 1 秒) ) ，z x ，y kq q ) 是模糊输出矩阵( 也叫做模糊输出函数) x q q 2 0 3 1 6 3 c o i n 第5 页，共3 4 页 毕业论文 第一章预备知识 如果用，( g ，z ，p ) = 岛 ) 来定义，：q x q _ l ，那么就能把，看作 是q ，x 和q 之间的模糊关系同时，g 能被看作是g 与q ，x 和y 之间的模糊关系，对 任意的( g ，z ，y ) q xxy ，g ( q ，z ，功= ( 筋扛 秒) ) 并且用( x l y ) = 扛i 芗) z x ，可y 幸，例= 蚓) 表示所有相同长度的输入字符z 和输出字符秽的输入一输出字符 对的集合 在输入字符z 后模糊转移函数，从状态q 转移到状态p 先前状态和输入共同决定 输出在状态q 下，输入字符z 后模糊输出函数输出字符y 满足以下条件： ( 1 ) v q q ，z x ，却q ，使得f ( q ，z ，力 0 号3 y y ，使得g ( q ，z ，y ) 0 ( 2 ) v 口q ，z x ，3 y y ，使得g ( q ，z ，y ) 0 号却q ，使得f ( q ，z ，p ) 0 约定记号x 和y 分别表示由具有有限长度输入集合和有限长度输出集合通过 连接运算生成的自由幺半群，其中x + 和l ，+ 中的元称为串，乘法运算为串的连接，即 是集合x 和集合y 上所有字符串的集合对z x + 和秽y ，约定i 。l 和分别表 示z 和y 的长度 定义模糊转移函数岛 ) 和模糊输出函数乳( z i 妙) 如下： ( 1 ) ， 北，a 力： 1 驴奶 10 ，q p 因为l 是分配格，易得以下重要的关系，对任意，g q ，z = 2 ：1 x 2 x ，有 f ( q ，z ，p ) = v 口，q f ( q ，x l ，q 1 ) af ( q l ，x 2 ，p ) 】 对任意的g q ，z x + 和o x ，转移函数，可以扩张至1 j f + ：q x 一q ，( g ，a ) = q ， ，+ ( q ，z n ) = f ( f 。( q ，z ) ，n ) ( 2 ) 对所有的g q 声x + ，d x ，b y 和y y ，有 x q q 2 0 3 1 6 3 。c o r n 第6 页，共3 4 页毕业论文 g ：q x q _ 三 g ( q ，z ，秒) = 1 ，z = y = a ， 0 ，z a ，y = a ；z ；a ，y a 第一章预备知识 夕奉( 垡，z 口，y b ) = v g ( q ，a ，b ) af ( q ，o ，c ) a 夕4 ( c ，z ，v ) l c q ) x q q 2 0 3 1 6 3 c o i t i第7 页，共3 4 页毕业论文 第二章初始化格值有限自动机之间的关系 以下均假设格半群( 三，v ) 局部有限 2 1 几类初始化格值有限自动机的定义 有限自动机可划分为两类：确定型自动机和非确定型自动机，以下对初始化格值 有限自动机进行定义，研究它们的区别和联系 定义2 1 1 非确定型初始化格值有限自动机( 简记为n i ) 是四元组n = ( q ，正盯) ，其中q 为非空有限状态集，为非空有限输入字符集，6 ：qx _ f ( q ) 为模糊状态转移函数，盯为初始状态，进而针对盯是否为分明的，把分为两 类： ( i ) 如果盯= q o q ，也就是盯为分明初始状态，则称，为1 型非确定初始化格 值有限自动机( 简记为 ) 在分明状态下，把q o 看做为e q o ( i i ) 如果盯f ( q ) ，也就是仃为模糊初始状态，则称j 为2 型非确定初始化格值 有限自动机( 简记为如) 假设l 是格半群，f ( q ) = a ：q l i a 是l 值模糊集) 定义2 1 2 确定型初始化格值有限自动机f 简记为d i ) 是四元组d = ( q ，叩，7 ) ，其中q 为非空有限状态集，为非空有限输入字符集，7 ：qx _ q 为 状态转移函数，7 i 为初始状态，进而由7 是否为分明的，把d 1 分为两类： ( i ) 如果7 - = q o q ，也就是7 - 为分明初始状态，则称d i 为1 型确定初始化格值有 限自动机( 简记为d 1 1 ) ( i i ) 如果丁f ( q ) ，也就是7 为模糊初始状态，则称d i 为2 。型确定初始化格值有 限自动机( 简记为d 1 2 ) 2 2 状态转移函数的扩张 首先扩充6 到输入串p = 秒渺= x l x 2 x k ，x l ，x 2 ，x k ，k2o ) 上 去，乘法运算为串的连接，扩张到模糊集合f ( q ) xf ( ) 上去 第8 页，共3 4 页 第二章初始化格值有限自动机之间的关系 因为( a ，b ) f ( q ) f ( ) ，( a ，j e 7 ) ( 口，z ) = a ( q ) b ( z ) 把f ( q ) f ( ) 映 射到f ( qx ) 上，那么得到扩张6 ：f ( q ) f ( ) 一f ( q ) ，定义6 ( a ，b ) ( p ) = v 口q 艇e 陋( g ) b ( z ) 6 ( q ，z ) p ) 】，j ( g ，z ) ) 表示在状态q ，输入字符z 后状态转移 到p 的隶属度，简记为6 ( g ，z ) 0 ) 圭5 ( g ，z ，力 设x ，y 为任意集合，9 ：x f ( y ) 为映射，f ( y ) 表示y 上的所有l 值模糊集的 集合，其中l 为任意q u a n t a l e 定义2 2 1f 7 】v a f ( x ) ，v y y ，给出如下定义 g ( a ) ( 秽) = v a ( x ) g ( x ) ( v ) l x x ) ( 2 1 ) 由( 2 1 ) 知，扩张映射扩可作如下表示： ( i ) p q ，若p = g ，贝u 6 ( 口，a ，p ) = e ，否贝0 6 。( g ，a ，p ) = 0 ( i i ) 0 + ，z ，扩( g 妇，p ) = v ：q 【扩( 口，0 ，z ) 6 ( z ，z ，p ) 】 进而，由于是格半群，对v p ，q q ，0 = x l x 2 2 惫 ，可 得扩( g ，x l x 2 z 詹，力= v 口。，啦，乳一。q i 6 ( q ，x l ，q 1 ) 6 ( q k 一1 ，x k ，p ) 】 2 3 初始化格值自动机之间的关系 定义2 3 1 对于一个初始化格值自动机n = ( q ，6 ，口) ，如果存在终止状 态t f ( q ) ，使得模糊自动机n 7 = ( q ，最伊，r ) 识别模糊语言f f ( s ) ，则称识 别， 定义2 3 2 令1 = ( q ，正q o ) 为n i l ，如果存在终止状态r ，则其可接受的格值 语言风f ( e + ) ，定义为 枷，= v q e q 6 * ( q o , o , q ) ( q o 】? 】雾嬲t 篙i 兰；：】， t 为分明的，= 小q ) 定义2 3 3 令n 2 = ( q ，6 ，a ) 为n 1 2 ，如果存在终止状态r ，则其可接受的格值 语言，2 f ( + ) ，定义为 脚，=做愁d5*(qa,0,q2)嚣*tvt a ( q l ( q l0 9 2 i 霈t 篙t ：i t 蒜 【口。q ，q 2 ) 扩，口2 ) 】， t 为分明的，= q ) x q q 2 0 3 1 6 3 c o i l l 第9 页，共3 4 页 毕业论文 第二章初始化格值有限自动机之间的关系 两个自动机等价是指输出函数相同，那么初始化格值有限自动机等价即为二者 所接受的格值语言相同 定理2 3 1 ( 1 ) n i i 氟j n l 2 等价 证明 设m = ( q ，6 ，口0 ) 为一个 ，则可以得到一个n 2 ，n = ( q ，e ，正盯) 事实上：q ，6 同m 中的定义一样， ( 7 - - = q o ， 10 ，否则 则易证得v p ，都有n ( 口) = f m ( p ) 反之，设n = ( q ，毋矿) 为一个n 2 ，存在n 7 = ( q ，蠡盯，砷，则可以得 到 ，m = ( r ，叩，t o ) ，在此假设终止状态均为分明的取两个不同的状态 元7 o 和n ，使r = t o ，r t u e q l q q ) ，r ：rx _ f ( r ) ，定义如下， ，7 ( r l ，z ，r 2 ) ：o ， r l - - r t ；r 2 - - t o , 【v 9 1 9 2 q ( r l ( q 1 ) 扩( q l ，z ，口2 ) r 2 ( q 2 ) ) ，否则 若7 1 = r 0 时，则有r o ( q 1 ) = 盯( q 1 ) ；若r 2 = r t 时，则有r t ( q 2 ) = t ( q 2 ) 扩张映射矿有 如下定义，任意的r ，7 7 r ，矿( n a ) = e r 对于护= x l x 2 x k + ， 矿( r 7 ，p ，r ) = v 叽r ( 7 7 ( r 7 ，x l ，r 1 ) r ( r k - l x k ，r ) ) = v r 女一1 r 一 r o ，r ( v 礼 口1 2 ，知，纰q ( r ( q 1 1 ) 6 ( q l l ，x l ，q 1 2 ) r l ( q 1 2 ) r k l ( q k l ) 6 ( q k x ，z ，q k 2 ) 7 ( g 昆2 ) ) ) 易知r i r 一 ， o ，n ) ，r i = e q i ，对v q i q ，p = x l ；t 2 x k ，有 ? 7 ( r 7 ，目，r ) = v 口0 ，瓠q ( r 7 ( q o ) 6 ( q o ，x l ，q 1 ) 6 ( q l ，x 2 ，q 2 ) 6 ( 铷一1 ，x k ，q k ) r ( 吼) ) = v 口0 - 一，口。q ( r 7 ( q o ) 6 ( q o ，口，q 缸) r ( 瓠) ) 若0 = a ，那么加( a ) = v r e r ( t o ，a ，r ) ) = 矿( r 0 ，a ，r o ) = e = ，( a ) 若口a ，则加( p ) = v ，r ( n 。( t o ，p ，r ) ) = 矿( t o ，p ，n ) = v 口。q 2 q p o ( q 1 ) 扩( q l ，玩9 2 ) r t ( 9 2 ) 】= v q 。，9 2 q p ( g i ) 扩( q l ，秽，q 2 ) t ( q 2 ) 1 由假设知终止状态 为分明的，所以i m ( o ) = v g ，q p ( q 1 ) 矿( q l ，p ，q 2 ) 】= i n ( o ) 所以 和如等价 对终止状态均为模糊的，可进行类似证明口 x q q 2 0 3 1 6 3 c o r n 第1 0 页，共3 4 页 毕业论文 第二章初始化格值有限自动机之间的关系 例2 3 1 设l = 0 ，1 】，为数的乘法运算，设有j 1 2 ，n = ( q ，6 ，仃) ，其中q = q l ，q 2 ，= 1 z ) ，6 ：q _ f ( q ) ，g ( q l ，z ，q 2 ) = 0 5 ，5 ( q 2 ，z ，q 1 ) = o 5 ，盯= o 8 ：1 + o 1 x 2 ，那么存在五，m = ( s ，7 ，8 0 ) ，其中s ，意义和中的q ，相 同，y ( s l ，z ，8 2 ) = 0 4 ，y ( s 2 ，z ，8 1 ) = 0 2 显然，对v 0 ，知p ) = 瓜( 口) 定义2 3 4 令m = ( q ，叩，7 - ) 为d h ，如果存在终止状态r ，则其可接受的格值 语言i m f ( + ) ，定义为 ，m ： v g q g ) 订( 叩弋g ，) 】舡值模糊集j 旧乩， i 1 ，t 为分明的，t = t i t q 定理2 3 2 【5 】设n = ( q ，6 ，盯，r ) 为三a ，那么存在一个确定的格值 自动机d 盯= ( q 口，靠，o a ，马) ，其中，d 盯所接受的格值语言分别记 为l ( ) ，( 以) ，贝j j l ( n ) = l ( d 盯) 定理2 3 3 设n = ( q ，正口) 为一个初始化格值有限自动机，则以下两者条件 等价： ( i ) 确定的格值自动机d 口是有限的； ( i i ) 任何被识别的模糊语言能被一个确定型格值有限自动机所识别 定理2 3 4 设任意的2 一型非确定初始化格值自动机如，当且仅当对己的任意有 限子集l 1 ，由l 1 生成的格半群的子代数是有限的，那么存在与如等价的d 1 1 证明 构造如，n = ( q ，瓦仃) ，存在n 7 = ( q ，6 ，盯，r ) ，l 1 = 6 ( qx q ) u 盯( q ) ，令l 2 = ( l i ，l 1 = ( 6 ( q ，z ，p ) i p ，q q ，z u 口( g ) i g q ) ，其中l 2 为格半 群的由1 生成的子代数因格半群局部有限，故l 2 有限，所以能得到一个d 1 1 ，m = ( s ，卵，s o ) ，其中s 为非空有限状态集，8 0 s ，存在m 7 = ( se ，叩，8 0 ，j d ) 在此假设终 止状态正p 为模糊的 事实上：s = 箩= s i q l 2 】，叩：s xe s ，则s 有限7 7 ( s ，z ) ( g ) = v p q i s ( p ) 6 ，z ，q ) 】v s s ，z ，口q ，8 0 = 1 肛) ，将它看作单点模糊集 仃) x q q 2 0 3 1 6 3 c o m p ( s ) = v s ( q ) z ( g ) 】 q e q 第1 1 页，共3 4 页 ( 2 - 2 ) 毕业论文 第二章初始化格值有限自动机之间的关系 下证如j ，= 加厶，当输入字符串p = x l x 2 ，x l ，x 2 + 时，矿：sx 4 一s ， 矿( s ，p ) ( q ) = v p q 8 0 , ) 扩 ，口，口) 】 = v p r q 【s 函) 扩x l ，7 ) 扩( 7 ，x 2 ，q ) 】 用归纳假设，若n = o ，矿( s ，a ) = s ，令i p l i = 礼一1 且矿( s ，口1 ) ( g ) = v p e q p ) 扩p ，p 1 ，g ) 显然成立，则对秽= o i x ，z e ， 7 7 + ( s ，p ) = 叩+ ( 8 ，0 i x ) = ，7 ( 矿( s ，e 1 ) ，z ) = v ”q 【( s ( p ) 扩，口1 ，r ) ) ( 扩( r ，z ，口) ) 】 = v p ，r q 【s ) 扩0 ，0 1 ，r ) 扩( 7 ，z ，g ) 】 = v p , r e d s ) ( 扩( p ，p 1 ，r ) 扩( r ，z ，口) ) = v p ，刁q 【s ) 6 + p ，8 1 x ，g ) 】 = v p ，口q 【s p ) 扩p ，口) 】 所以m 即) = v 。s 【8 0 ( s ) p ( 矿( s ，口) ) 】 - - - - v s e s 陋( 矿( 8 0 ，口) ) 】 = v 。s p ( v p ，口q ( s o ( p ) 扩( p ，口，g ) ) ) 】，由( 2 - 2 ) 可知， m ，( 9 ) = v p , q e q p o j + 慨p ，q ) z ( g ) 】 = v p , q 6 q p ) 扩，p ，q ) t ( g ) 】- ，( p ) 贝u , - i 得加( p ) = 瓜( p ) 反之，构造d 1 1 ，m = ( s ，叩，s o ) ，得到一个n h ，n = ( q ，6 ，盯) ， 地z ，g ) = 1 , r ( p , x ) 2 g ， 实际上：q = s 仃= 1 s o ，表示单点模糊集 s o ，它在s o 点取值1 ，而在其它点取值 为o 容易验证v 口，知( 9 ) = 加( p ) 对终止状态? ，p 为分明的情况可进行类似证明口 x q q 2 0 3 1 6 3 c o i n 第1 2 页，共3 4 页 毕业论文 第三章m i z u m o t od f a 的最小化 3 1 模糊状态转移函数的扩张 本章是在格半群上展开讨论的，为了给出由m i z u m o t o d f a 所接受的语言形 式，对模糊状态转移函数进行扩张，见第二章2 2 节 定理3 1 1设m = ( q ，f ，q o ，7 - ) 是m i z u m o t o 确定型格值有限自动 机( m i z u m o t o d f a ) ，其中f = 【冗i r = ( ( o ) ) ，o e ，g ，p q ，( a ) l ， 那么6 = 扩i q x s x q 证明设p ，那么扩( p ) = 扩( a e ) = 5 ( a ) 0a ( o ) = 磊n oa ( o ) = j ( 口) 口 定理3 1 2设m = ( q ，e q o ，r ) 是m i z u m o t o d f a ，对任意的q q ，z e ，彰幸，那么j 爹q ，使得6 ( g ，z ，p ) 0 当且仅当扩( q ，秽，p ) 0 证明“# ”显然结论是成立的 “专”用数学归纳法证明这个结果 设q q ，z ，y 4 ，如果i v i = 0 ，那么秒= a 设p = q ，那么扩( g ，a ，p ) = e 0 假设对i v i = k l ( k 1 ) ，结论是成立的那么对i v i = k ，证明6 + ( q ，秒，p ) o 也 是成立的 ，设y = z ，其中i 可7j = k 一1 , x e ，y + ，那么扩( q ，矽，p ) = 矿( q ，可7 z ，p ) = v r q 【矿( g ，矽7 ，r ) 6 ( 7 ，z ，p ) 】扩( g ，y ，s ) 6 ( s ，z ，p ) 通过归纳假设存在s q 使得扩( g ，y ，8 ) 0 进而，根据条件6 ( s ，z ，p ) 0 ，所 以扩( g ，y ，8 ) 占( s ，z ，p ) 0 因此，扩( 口，可，力 0 口 3 2m i z u m o t od f 4 s 间的等价性 定义3 2 1 设m 7 = ( q ，e ，f ，j ，t ) 是m i z u m o t o 格值有限自动 机( m i z u m o t o l f a ) ，对任意的口+ ，那么被m 所接受的语言加，f ( r + ) 可以 表述为如下形式， 知，( 口) = v m q p ( g ) 扩( 口，p ，p ) t ) 】 第1 3 页共3 4 页 第三章m i z u m o t o d f a 的最小化 定义3 2 2 设m = ( q ，f ，q o ，7 - ) 是m i z u m o t o 确定型格值有限自动 机( m i z u m o t od f a ) ，对任意的9 + ，那么由m 识别的语言表示为 加( 口) = 7 - ( 矿( q o ，咿) ) 对两个m i z u m o t o d f a s ，尬和，如果它们接受相同的语言，也就是饥= 舭，那么它们是等价的 定义3 2 3 设尬= ( q ，r ，吼，氕) 是m i z u m o t o d f a ，( 工，v ) 是格半群， 吼q i ，i = 1 ，2 ，3 ，那么： ( 1 ) 9 1 和q 2 是等价的( q 1 兰q 2 ) 兮w + ，丁1 ( 研( 口1 ，p ) ) = 亿( 蠼( q 2 ，p ) ) ； ( 2 ) v 忌 0 ，g l 和q 2 是k - 等价的( q 1 - - kq 2 ) w 且k ，丁1 ( 醒( q l ，口) ) = 仡( 定( 口2 ，p ) ) ； ( 3 ) 尬和尬是等价的( 姬三m 2 ) v q l q l ，s q 2 轨，使得q l 三q 2 ；或 聂j v q 2 q 2 ，3 q l q 1 使得口2 三q l ； ( 4 ) v k 0 ，舰和物是k - 等价的( 尬兰奄尬) 营v q a q l ，3 q 2 q 2 ，使得q l 三知q 2 ； 或对v q 2 q 2 ，3 q l q 1 使得口2 三七q l ； 定理3 2 1如果m 7 = ( q ，f , x ，t ) 是m i z u m o t o l f a ，而m = ( q ，毋，厶，2 1 ) 是m i z u m o t o d f