（运筹学与控制论专业论文）两类自动机的乘积研究.pdf

f 1 1 1111i ii ii iii ii i iiil ly 17 4 0 2 13 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：迦避l 军 日期：加，d 年占月艿日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：磁7 j 哗 导师签名： 彦z 叼 够易 日期：7 ot o 年，月以侣 乘积是自动机理论中的基本运算之一，在理论和应用方面都占有重要的地位。 模糊自动机的乘积理论，就是用代数手段去研究模糊自动机乘积的转移( 输出) 结构，即模糊状态转移( 输出) 函数的特征。本文构造了模糊有限自动机新的乘 积一k r o n e c k e r 积，讨论k r o n e c k e r 乘积意义下转移函数性质。 自动机主要由转移结构和输出结构这两大部分组成，转移结构是自动机的内 部成分，而输出结构是自动机的外部成分。输出结构依赖于转移结构，而转移结 构却独立于输出结构，所以输入结构可以独立地被研究。由于不带输出函数的模 糊有限自动机研究成果已经很多了，本文主要研究带输出函数的模糊有限自动机 - m e a l y - 型模糊有限自动机一些代数性质。 本文主要工作有如下两个方面： 1 在矩阵理论框架下，引进了模糊有限自动机转移矩阵、变换矩阵半群、矩 阵直和、矩阵和以及覆盖概念。利用矩阵的k r o n e c k e r 积，给出了模糊有限自动机 的新的乘积。进一步地，证明了矩阵直和覆盖矩阵和，k r o n e c k e r 积对矩阵直和， k r o n e c k e r 积对矩阵和的分配性质，k r o n e c k e r 积与矩阵和满足结合律，但是矩阵直 和不满足结合律。 2 对m e a l y 一型模糊有限自动机覆盖关系作了细致的刻画，推广了原有的覆盖 概念。针对m e a l y 一型这类模糊有限自动机，通过性质考察了此概念的合理有效性， 新的覆盖概念在乘积自动机间建立了更多的联系。特别证明了直积、级联积、圈 积三种乘积之间的覆盖关系，得到了一些乘积自动机覆盖关系的传递性质。 关键词：模糊有限自动机，k r o n e c k e r 积，覆盖，m e a l y 模糊有限自动机，直积 一 a b s t ra c t a b s t r a c t p r o d u c ti so n eo ft h eb a s i co p e r a t i o n so fa u t o m a t at h e o r y , w h i c hp l a y sa p r o m i n e n t r o l eb o t hi nt h e o r ya n da p p l i c a t i o n t h ea l g e b r a i cm e t h o d si s u s e di nt h et h e o r yo f p r o d u c to ff u z z ya u t o m a t at os t u d yt h et r a n s f e r ( o u t p u t ) s t r u c t u r eo ff u z z yf i n i t es t a t e a u t o m a t a ，t h a ti s ，t os t u d yt h ec h a r a c t e r i s t i c so ff u z z ys t a t et r a n s i t i o n ( o u t p u t ) f u n c t i o n t h i sp a p e rc o s t r u c t st h en e wp r o d u c to ff u z z yf i n i t e s t a t ea u t o m a t a kr o n e c l ( e r p r o d u e t i s ，w h i c hd i s c u s s e st h ep r o p e r t i e so ft r a n s f e rf u n c t i o n a u t o m a t ac o n s i s t so ft w o m a i n s t r u c t u r e s ，t h et r a n s f e r s t r u c t u r ea n do u t p u t s t r u c t u r e t h et r a n s f e rs t r u c t u r ei si n t e r n a lp a r to fa u t o m a t aw h i l et h eo u t p u ts t r u c t u r ei s e x t e r n a lp a r t t h eo u t p u ts t r u c t u r ei sd e p e n do nt h et r a n s f e rs t r u c t u r ew h i l et h et r a n s f e r s t r u c t u r ei si n d e p e n do nt h eo u t p u ts t r u c t u r e h e n c et h et r a n s f e rs t r u c t u r ec a n b es t u d i e d s e p a r a t e l y t h i st h e s i si ss t u d i e sb yf u z z yf i n i t es t a t ea u t o m a t aw i t ht h e o u t p u t f u n c t i o n m s o m ea l g e b r a i cp r o p e r t i e so ff u z z yf i n i t es t a t ea u t o m a t a b e c a u s et h e r ea r e r e s e a r c hr e s u l t so ff u z z yf i n i t es t a t ea u t o m a t aw i t h n o n - o u t p u tf u n c t i o n m o r es p e c i f i c a l l y , t h em a i nr e s u l t sa r es h o w nb e l o w ： 1 i nt h ef r a m e w o r ko fm a t r i x t h e o r y , t h ec o n c e p t so ft r a n s i t i o nm a t r i x ， t r a n s f o r m a t i o nm a t r i xs e m i g r o u p ，m a t r i xd i r e c ts u m ，m a t r i xs u m ，a sw e l la sc o v e r i n gf o r f u z z yf i n i t es t a t em a c h i n e sa r ei n t r o d u c e d t h ed e f i n i t i o n so fn e wp r o d u c t so ff u z z v f i n i t es t a t em a c h i n e sa r eg i v e nb ya p p l i c a t i o no fk r o n e c k e r p r o d u c t f u r t h e r m o r e ，t h e c o v e t i n gp r o p e r t i e so f m a t r i xd i r e c ts u ma n dm a t r i xs u m ，t h ed i s t r i b u t i o nl a wk r o n e c k e r p r o d u c ta n dm a t r i xd i r e c ts u m ，k r o n e c k e rp r o d u c ta n dm a t r i xs u i na r ep r o v e d f i n a l l y , k r o n e c k e rp r o d u c ta n dm a t r i xs u mo fm e a l y t y p ef u z z yf i n i t e s t a t em a c h i n e sa r e a s s o c i a t i v e h o w e v e r , i tc a ne a s i l yb es h o w nt h a tm a t r i xd i r e c ts u mo fm e a l y t y p ef u z z y f i n i t es t a t em a t h i n e sw a sn o ta s s o c i a t i v e 2 t h er e l a t i o n s h i p so fc o v e r i n ga m o n gp r o d u c tm a c h i n e sf o rm e a l y - t y p ef u z z y f i n i t e 。s t a t em a c h i n ea r es t u d i e di nd e t a i l t h ec o n c e p to fc o v e r i n gi s g e n e r a l i z e d t h i s n e wc o n c e p ti sr e a s o n a b l ea n dv a l i dw h i c hi s e x a m i n e db yp r o p e r t i e s t h em o r e c o v e r i n gr e l a t i o n s h i p sh a v eb e e ne s t a b l i s h e di nt h ep r o d u c tm a c h i n e st h a nb e f o r e s p e c i a l l y , t h ec o v e r i n gr e l a t i o n s h i p sa m o n gt h ed i r e c tp r o d u c t ，c a s c a d ep r o d u c t ，w r e a t h l i a b s t r a ( 了r p r o d u c ta r ep r o v e d s o m et r a n s i t i v ep r o p e r t i e so fc o v e r i n gr e l a t i o n s h i p sa r eo b t a i n e di n t h ep r o d u c tm a c h i n e s k e yw o r d s ：f u z z yf i n i t es t a t em a c h i n e ， f i n i t ea u t o m a t a ，d i r e c tp r o d u c t k r o n e c k e rp r o d u c t ，c o v e r i n g ，m e a l y - t y p ef u z z y i i i ， 目录 第一章引言，1 第二章预备知识5 2 1 模糊集合理论基础5 2 2 有限状态自动机5 2 3 模糊有限状态机6 第三章模糊有限自动机的k r o n e c k e r 积8 3 1 矩阵k r o n e c k e r 积及基本性质8 3 2 转移矩阵和变换矩阵半群一9 3 3 模糊有限自动机的k r o n e c k e r 积和覆盖性质1 2 3 4 结论2 0 第四章m e a l y - 型模糊有限自动机的覆盖性质2 2 4 1m e a l y - 型模糊有限自动机的基本定理和性质2 2 4 2m e a l y 型模糊有限自动机的覆盖2 4 4 3m e a l y - 型模糊有限自动机的性质2 7 4 4 结j 沧3 5 第五章结束语3 6 致谢3 8 参考文献3 9 攻硕期间取得的研究成果4 2 i v 在计算机科学中，自动机用作计算机和计算过程的动态数学模型，用来研 究计算机的体系结构、程序设计、计算复杂性的理论。在语言学中，自动机作为 语言识别机器( 如有限状态自动机识别的语言识别正则语言) ，用来研究各种形式 语言。在数学中，则用自动机定义可计算函数，研究各种算法。现代自动机的一 个重要特点是能与外界交换信息，并根据交换所得的信息改变自己的动作，即改 变自己的功能，甚至改变自己的结构，以适应外界环境的变化。也就是说现代自 动机在一定程度上类似于生命有机体，具有记忆能力和识别判断能力，能够适应 周围环境的变化。因此，自动机适宜于作为信息处理系统的数学模型。自动机可 按其变量集和函数的特性分类，也可按其结构和联结方式分类。主要有：有限自 动机和无限自动机、线性自动机和非线性自动机、确定性自动机和不确定性自动 机等。自动机理论的研究对象是有限状态自动机，有限状态自动机( f s m ”f i n i t e s t a t em a c h i n e ”或者f s a ”f i n i t es t a t ea u t o m a t o n ”) 是为研究有限内存的计算 过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的 状态，每个状态可以迁移零个或者多个状态，输入的字符串决定执行哪个状 态的迁移。 1 9 6 5 年，美国自动控制专家、加利福尼亚大学教授j a z a d e h 发表题为模 糊：集合( f u z z ys e t s ) 的论文，首次把数学应用到模糊现象领域，标志着模糊数 学这门学科的诞生。模糊数学是研究模糊现象新的数学分支，所研究的事物的概 念本身是模糊的，即一个对象是否符合这个概念难以确定，这种由于概念外延的 模糊而造成的本身是确定性称为模糊性。以模糊集合代替原来的经典集合，把经 典数学模糊化，便产生了以模糊集合为基础的模糊数学。模糊数学是运用数学方 法研究和处理模糊性现象的- - f 数学新分支，它以模糊集合论为基础，提供了一 种处理不肯定性和不精确性问题的新方法，是描述人脑思维处理模糊信息的有力 工具。作为- - i 新兴学科，模糊数学得到了广泛应用。 模糊集与自动机理论结合产生了新的自动机一模糊自动机。1 9 6 7 年，w e e 率 先将模糊集理论用于自动机领域，第一个模糊有限状态自动机( 非模糊初始状态 和非模糊输出) 的数学模型随之诞生。1 9 6 8 年，s a n t o 定义了一种最大最小型模 糊有限状态自动机，并深入研究了模糊自动机识别的模糊语言及在各种算子下的 电子科技大学硕士学位论文 封闭性乜1 。1 9 6 9 年，m i z u m o t o 等人，提出了具有模糊初始状态的模糊有限自动机， 并且还利用模糊矩阵和模糊向量工具对其进行研究口1 。同年，w e e 和f u 定义了有 限模糊输出函数的模糊有限自动机h 1 。a s a i 和k i t a j i m a 于1 9 7 1 年研究了m e a l y 型 模糊有限自动机和m o o r e 型模糊有限自动机，并证明了它们的等价性璐】。程伟、莫 智文就当时出现的模糊有限自动机作了一个分类：第一类是具有输出字符功能而 没有初始状态的模糊有限自动机，第二类是具有初始状态而没有输出字符功能的 模糊有限自动机哺1 。 随着模糊技术的飞速发展，模糊自动机研究也得到了许多学者的关注，取得了 丰硕的成果。1 9 8 0 年，k a n d e l 和l e e 出版的专著对当时模糊有限状态自动机的研 究进展工作进行了介绍 7 】。m a l i k ，m o r d e s o n ，s e n 定义了一种模糊有限状态自动 机，并在文献雎j j0 “1 2 1 中系统地研究了模糊有限自动机的五种乘积自动机的构造方 式，模糊有限自动机半群性质，模糊有限自动机的笛卡尔合成、有限自动机的子 系统和强子系统以及模糊有限自动机的分离性、可分性、连通性、分解性、循环 性等众多性质。同时，在他们合著的专著n 3 j 中详细介绍了模糊有限自动机的乘积， 并对模糊有限自动机理论的研究和发展作了全面的总结。k i r i t h i v a s a n 和s h a r d a 又 引入了模糊6 2 自动机的概念，并对不同类型的模糊6 2 自动机及其所识别的相应类 型的模糊形式语言作了深入的讨论们。 自从模糊自动机这一概念提出以后，其理论研究和实际应用都引起了广泛的 关注。模糊有限状态自动机在语言学、计算机科学、生物学、数学和逻辑性等方 面都有重要应用。自动机是计算理论里基本而简单的数学模型，而乘积是自动机 理论中的基本运算之。因此，自动机的乘积研究在理论和应用方面都占有重要 的地位，具有极大的应用价值。 1 9 8 2 年，h o l c o m b e 对经典自动机的代数性质进行了系统的研究，定义了经典 自动机的半群、覆盖、级联积、圈积等概念，这些概念在自动机的研究中起了重 要作用 1 5 o 模糊自动机可以看着经典自动机的特殊情况，m a l i k 、m o r d e s o n 并1 s e n 推广了经典的代数自动机，开始了模糊自动机代数研究。文献 8 】定义了有限情形 下的乘积( 直积、级联积、圈积) ，覆盖，弱覆盖等概念；文献 9 研究了模糊有限自 动机的半群性质以及笛卡尔合成；文献 1 0 研究了有限自动机的子系统和强子系 统，介绍了循环系统和简单强子系统及其基本性质；文献 1 l 】讨论了模糊有限子自 动机在有限群上的性质。这些理论建立了代数模糊自动机理论的基本框架，为乘 积自动机研究做了理论铺垫。1 9 9 8 年，k i m 等人引入了t 广义状态机和t - 广义变换 半群n 们，得到了相应的乘积性质。t - 广义状态机不同于一般的模糊自动机，它是一 2 第一章引言 个泛化的概念比模糊自动机更模糊化。p d a s 于1 9 9 9 年提出了一种基于模糊拓扑的 模糊有限状态机，分析了模糊有限自动机的分离性，其模糊子系统的连通性、弱 连通性，讨论了自动机和拓扑之间的部分关系u 刀。2 0 0 2 年，h vk u m b h o j k a r 等定 义了模糊自动机的一般和与和，证明了圈积覆盖级联积、一般和覆盖和n 引。同年， b a s a k 和g u p t a 研究了模糊有限自动机的商自动机和极小自动机n 钉。2 0 0 6 年，t a t j a n a 与p e t k o v i c 讨论了模糊有限自动机的同余和同态口们。 在国内，对模糊自动机代数性质研究起步较晚，并且模糊有限自动机研究方向 向格方向发展，也取得了一些很有价值的研究成果。2 0 0 1 年，邱道文等提出了基 于完备剩余格值逻辑的自动机理论，延拓了状态转移关系，得n t 模糊( l 值) 自动 机对剩余格的一个刻画；讨论了模糊( l 值) 子机，s u c c e s s o r 和s o u r c e 算子的基本 性质及它们相互的等价关系，并由此推出这两类算子是模糊( l 值) 闭包算子。他还 给出了模糊自动机l 值双模糊拓扑刻画，说明了基于完备剩余格值逻辑的自动机 ( 称l 值自动机) 与真值格( 剩余格) 之间的一些等价关系旺“2 2 矧。2 0 0 4 年，邱道文研 究了模糊有限自动机由b i f u z z ys o u r c e 和s u c c e s s o ro p e r a t o r s 导出的双模糊分离性， 收敛性，同态及双模糊拓扑性质心们，模糊有限自动机的双模糊特征方面性质基本 框架初步建立起来了。莫智文，陈乾讨论了模糊有限自动机的b i f u z z ys u c c e s s o r 算 子和b i f u z z ys o u r c e 之间的基本性质及关系3 ，进一步深化了模糊有限自动机的双 模糊特征的研究。2 0 0 3 年，李永明引入格值自动机及其语言的概念，在格半群意 义下研究自动机心们。以往的模糊自动机只是对经典自动机的简单推广，格值自动 机在更广的框架下一格半群意义下研究自动机理论，所得结果表明了格值自动机 比经典自动机有更强的计算能力，能识别更广泛的形式语言与模糊语言，这就是 格值自动机本身的特色。2 0 0 6 年，雷红轩、李永明在格半群的框架下，研究具有 相同长度的输人字符和输出字符功能的模糊自动机，详细地研究了它的性质和它 的同态性，揭示出格值有限自动机与格半群的代数性质有紧密联系瞳 。刘军、莫 智文在格半群框架下讨论了自动机的乘积，建立了与模糊自动机相对应的乘积定 理和覆盖关系晗引。 乘积作为自动机理论的基本运算之一，并且在理论和应用方面都有着重要的 地位，那如何构造乘积自动机呢? 学者们从状态集合和输入字母表出发，利用拓 扑结构，代数手段去研究模糊自动机乘积的转移结构，即模糊状态转移函数的特 征，构造了一些典型的模糊有限自动机的乘积，讨论了各种乘积意义下的转移函 数的性质，并进一步研究各种乘积意义下的模糊有限自动机的分离性等。但有关 乘积方面的研究文献并不多，原因在于在多个自动机组成的系统中，我们必须要 电子科技大学硕士学位论文 解决复杂性、冗余性等的问题。 本文将主要研究模糊自动机乘积的各种构造方式，讨论各种乘积意义下的转 移函数的性质，研究各种乘积意义下的模糊有限自动机的分离性，进一步研究新 的乘积自动机之间的覆盖关系，达到进一步完善模糊自动机的乘积理论的目的。 其次，针对m e a l y - 型这类模糊有限自动机，对覆盖概念做了细致的刻画，通过性 质考察了覆盖概念的合理有效性，新的覆盖概念在乘积自动机间建立了更多的联 系。 本学位论文共分五章： 第一章是引言，主要介绍模糊自动机的发展历史与发展现状。 第二章主要介绍了模糊集合理论基础，有限状态自动机，模糊有限自动机。 本章的概念和结论是展开全文的基础，也是诸多证明技巧的来源所在。 第三章提出模糊有限自动机的k r o n e c k e r 积。 第一节引用文献乜耵距阵的k r o n e c k e r 积定义和性质，这是本章定义模糊有限自 动机的k r o n e c k e r 积基础来源。 第二节定义转移矩阵和变换矩阵半群，为后面的性质作好铺垫。 第三节给出了模糊有限自动机的k r o n e c k e r 积、矩阵直和、矩阵和以及覆盖 概念的定义。进一步地，证明了矩阵直和覆盖矩阵和，k r o n e c k e r 积对矩阵直和， k r o n e c k e r 积对矩阵和的分配覆盖关系，k r o n e c k e r 积与矩阵和满足结合覆盖关系， 但矩阵直和不满足结合覆盖关系。 第四章给出m e a l y 型模糊有限自动机覆盖性质。 第一节引用文献臼m e a l y - 型模糊有限状态自动机乘积的3 种构造方式。 第二节m e a l y - 型模糊有限自动机覆盖关系作了细致的刻画，推广了原有的覆 盖概念。针对m e a l y - 型这类模糊有限自动机，通过性质考察了此概念的合理有效 性，在新的覆盖概念在乘积自动机间建立了更多的联系。 第三节给出了m e a l y - 型模糊有限自动机直和与m e a l y - 型模糊有限自动机和的 定义。最后证明了直积、级联积、圈积三种乘积之间的覆盖关系，得到了一些 乘积自动机覆盖关系的传递性质。 第五章总结了全文的工作。 4 第二章预备知识 第二章预备知识 2 1 模糊集合理论基础： 模糊集合是没有精确边界的集合，它是以逻辑真值为 o ，l 】的模糊逻辑为基础 的，它表示的是元素属于集合的程度。 定义2 1 1m 3 设在论域x 上给定了一个映射a ：x 寸 0 ，1 ，x a ( x ) ，则称么 为x 上的模糊集，称a ( x ) 为么的隶属函数。我们用f ( x ) 表示x 上的所有模糊子 集的全体。 定义2 1 2b 门设a ，b 是同一论域z 上的两个模糊集。它们之间的包含、相 等关系定义如下： b 包含彳，记作彳b 彳( z ) b ( 石) ，v x x a 等于b ，记作a = b 彳( 工) = b ( z ) ，v x x 定义2 1 3 n 设a ，b 是同一论域上的两个模糊集。它们之问的交、并、补 运算定义如下： 彳与b 的交，记作a r 、b ，有 ( a n b ) ( x ) = 彳( z ) a b ( x ) = m i n a ( x ) ，召( x ) ) ，v x x a 与b 的并，作彳u 召，有 ( 彳u b ) ( x ) = 彳( z ) v b ( x ) = m a x a ( x ) ，b ( z ) ) ，v x x 彳的补，作a 。，a 。( 工) = 1 一彳( z ) ，v x x 。 定义2 1 4 妇设有两个经典集合x 和y ，定义x 和y 的直积为： x x y = ( 石，y ) ix x ，y y ) 定义2 1 4 口妇直积x xy 上的模糊关系是x y 的一个模糊子集r ，r 的隶属 函数r ( x ，y ) 表示了x 中元素z 与y 中元素y 具有这种关系的程度。x 到z 的模糊 关系称为x 上的模糊关系，x y 上的全体模糊关系记为，( x y ) 2 2 有限状态自动机 定义2 2 1 b 2 1 一个限状态自动机是一个五元组m = ( q ，a ，f ，i ，t ) 表示的系统， 其中 q 是一个有限状态集； 电子科技大学硕士学位论文 么有限的输入字符集； f ：q xa q 是状态转移函数( fn - - 丁以自然扩张为f ：q xa jq ) ； f 表示初始状态； 丁表示终止状态。 有限状态机m 识别( 或接受) 一个字国a + ，若i c o t ，我们就把m 所识别 ( 或接受) 字的全体称为有限状态机m 所识别( 或接受) 的语言， l ( m ) ：三( m ) = a li c o r ) 定义2 2 2 。3 1 一个m e a l y 型有限自动机是一个由五元组必= ( q ，万，五) 所表 示的系统，其中： q 是一个有限状态集； 有限的输入字符集； 为有限输出字符集； 万：q 专q 为转移函数； 兄：q 专a 为输出函数。 如果设m 现在处于状态口，此时输入字符a ，那么下一步将转入状态 a ( q ，口) q ，同时有一个输出a ( q ，口) 2 3 模糊有限状态机 定义2 3 1 阳1 模糊有限自动机由一个三元组m = ( q ，x ，t ) 组成，其中：q 、x 分 别是非空有限状态集，非空有限输入字符集，是q x q 上的模糊子集( 即： q x x q 专 o ，1 】) 。 在本文中，定义模糊有限自动机的矩阵形式，z = ( q ，x ，m ) ，其中q 、x 是非空 有限状态集合和非空有限输入字符集合。m 表示q x 与q 的模糊关系，称为转 移矩阵。 定义2 3 2 m e a l y 一型模糊有限自动机由一个五元组m = ( q ，x ，y ，万) 组成， 其中：q 彳，】，分别是非空有限状态集，非空为有限输入字符集，非空有限输出字 符集，是q x q 上的模糊子集( 即：q z q 一 o ，1 ，称为模糊状态转移函数) 万是q x y 上的模糊子集( 即：q xx xy 专【o ，1 】，称为模糊输出函数) 。并且对 于一个d e a l y - 型模糊有限自动机满足下列条件： ( 1 ) v q q ，工x ，3 p q ，s t 4 q ，x ，p ) 0 = 3 y y ，5 t a ( q ，工，y ) 0 ( 2 ) v q q ，x x ，3 y y ，s j a ( q ，x ，y ) 0 = j p q ，s t ( g ，x ，p ) 0 ， 6 第二章预备知识 i 。1 。1 。1 一 就输入字符串而言： 定义：q x x x q 一 o ，1 】如下： 旷 三! 黧i ： t + ( g ，x 口，p ) = v ( g ，戈，r ) a 1 t ( r ，口，p ) l ，q ) 定义万：q x x 】，寸 o ，1 o n t 双彬川_ l 篆罨孟扒一 万+ ( g ，x 口，y b ) = v 8 + ( g ，x ，y ) a p ( g ，x ，r ) a s ( r ，口，b ) i ，q ) = 万+ ( g ，x ，y ) a v 伽( g ，x ，r ) a 6 ( r ，以，6 ) ) i ，q ) 其中：v q ，p q ，a y ，x x + ，b y ，y y 在本文中；如不特别说明，我们记x 和y 分别表示z ，y 上字为有限长度的 集合，人表示空字，ixl ，ly1 分别表示字符串z 与y 的长度，iqi 表示状态q 的个 数。e 表示元素全为1 的矩阵，表示对角线为的1 的方阵。 电子科技大学硕士学位论文 第三章模糊有限自动机的k r o n e c k e r 积 本章在矩阵理论框架下，引进了模糊有限自动机转移矩阵、变换矩阵半群以 及覆盖概念。利用矩阵的k r o n e c k e r 积，定义了模糊有限自动机的乘积，进一步地， 讨论了模糊有限自动机k r o n e c k e r 积的转移矩阵性质，并研究了其对应的变换矩阵 半群k r o n e c k e r 积间的覆盖关系。 3 1 矩阵k r o n e c k e r 积及基本性质 定义3 1 1 汹1 设彳= ( ) c 雕”，b = ( 6 ： ) c 肿，则下列分块矩阵 f b a b 1 aob ：lj ； i c m p 翱q 称为a 和b 的k r o n e c k e r 积，记为 i a 。l 八b 口。 b ，j 定义3 1 2 设彳= ( 口驴) c m 。p , b = ( ) c ”nc = a b ，其中 c = ( 勺) c ”“，c i j = v 是l ( a i k 八) ，i = 1 2 ，m ，= 1 2 埘 性质3 1 1 瞳们设彳= ( 口扩) c “”，b = ( ) c “”，c = ( c ：c ) c 脒”， d = ( d f ，) c 。”，则( 彳ob ) ( c 圆d ) = ( a c ) ( b d ) 推论3 1 1 设4 = ( 口7 ) c 删“，局= ( 6 7 扩) c m x m ，= 1 ，2 ，n ，则 ( a 10 b 。) ( 4o 马) ( ap 氐) = ( 4 4 a n ) o ( b i b 2 b u ) 定义3 1 3 设么= ( ) c n l x n ，b = ( ) c 舭“ ( 1 ) 如果口 ，f = 1 ，2 ，m ，= 1 ，2 ，z ，则彳b ( 2 ) 如果= b o ，i = 1 2 mj = l 2 ，l ，则彳= b a b ，则 性质3 1 3 设么= ( ) c 肼4 ，b = ( ) c “”，c = ( c ：f f ) c “”，若a b ， c a c 圆b 证明：由于a 曰，则勺八彳q 人召，所以有c q 彳c 圆b 性质3 1 4 设彳= ( 口f ) c “，b = ( 岛) c p x qc = ( 勺) c 州，则 彳 ( b p c ) = ( 彳0 b ) o c 证明：结论是平凡的。 3 2 转移矩阵和变换矩阵半群 定义3 2 1 模糊有限自动机( 简称f f s a ) 是一个三元组m = ( q ，x ，m ) ，其中 q 和x 是非空有限集，分别称为状态集和输入字符集，m 为转移矩阵，其定义如 下： m = m ( a ) i m ( a ) = ( 心，。，( 口) ) ，v q ，q ，q aex ，以，钉( 口) 0 ，1 ) ，其中a q , 町( 口) 表示m 在状态g f 输入字符口时转移到下一个状态g ，的程度。 定义3 2 2 设m = ( q ，x ，m )f f s a ，设q = q l9 2 ，q 。) ，则有： ( 1 ) m ( ) = l ( 单位矩阵) ， q i = q ，a q , ，( 人) = l 否则心，( ) = o ( 2 ) m ( x a ) = m ( x ) m ( a ) ，其中v x x ，a x 定理3 2 1 设研= ( q ，x ，m ) 是f f s a ，设q = q lq 2 ，吼) ，v u z ，v x + ，则 m ( u v ) = m ( “) m ( 1 ，) 证明：假设= ，2 若，z = o ，1 ，= a ，则m ( u v ) = m 八) = m 似) 而 m ( “) m ( ) = m ( u ) l = m ( u ) ，即当n = 0 ，结论成立。根据定义3 2 2 可以证明n = 1 ， o 电子科技大学硕士学位论文 结论成立。假设当ivl o ，1 】。丁称为变换矩阵且满足 下列条件： ( 1 ) t ( u v ) = r ( “) 丁( y ) ，v u ，1 ，s ( 2 ) 如果s 包含单位元e ，丁( e ) = l ( 单位矩阵) 。另外，如果下列条件满足， 则( q ，s ，t ) 称为是一一的。 电子科技大学硕士学位论文 ( 3 ) 设“，v s 如果丁( “) = r ( 力，则”= 1 ， 定理3 2 3 设忉= ( q ，z ，m ) ；是f f s a ，设e ( m ) 定义如前，q = g 。，9 2 ，吼) ，则 ( q ，e ( m ) ，t ) 是一个一一的t m s ，其中r ( 【z 】) = 肘( x ) ，x x 证明：根据定理3 2 2 ，e ( m ) 是一个带有单位元 人 的有限半群。设 x ： y e ( m ) ，则丁( x 木 y 】) = r ( 砂 ) = m ( x y ) = m ( x ) m ( y ) = r ( x ) r ( 夕】) ， 丁( 八 ) = m ( 八) = l 。r ( x 】) = r ( 少 ) ，则m ( x ) = m ( y ) 所以x = - y 或 x _ y ，因而 ( q ，e ( m ) ，d 是一个一一的变换矩阵半群。 设聊= ( q ，z ，必) f f s a ，则根据定理3 2 3 知( q ，e ( m ) ，2 3 是一个变换矩阵半 群，记为t m s ( m ) ，我们称t m s ( m ) 是与m 相伴的变换矩阵半群。 3 3 模糊有限自动机的k r o n e c k e r 积和覆盖性质 定义3 3 1 设惕= ( q ，五，m ) 是f f s a ，i = l ，2 f 是一个五至岘函数，扩张孝到 f + ：义_ 一叉：如下：f ( ) = 且f ( x ) = 孝( 五) 孝( 恐) 善( h ) 其中v x = 五屯h z ? ， 毛五，f - 1 ，2 ，n 则称孝是一个m ：对m 。的覆盖( 记作m 。m 2 ) 的充要条件是 l ( z ) m 2 ( 孝+ ( z ) ) ，v x 五 定义3 3 2 设f ，= ( q ，墨，互) 是t m s ，i = l ，2 善是s , 至u s ：函数，扩张孝成一个从 耳到墨上的函数f ，其中f ( 人) = 人，v s = 而j ：知矸，墨s i ，i = 1 ，2 ，n ， 孝( j ) = 孝( 墨) f ( s ：) 孝( ) ，则称孝是r ：对r 。的一个覆盖( 记作f 。f ：) 的充要条件 是互( s ) 互( 善0 ) ) ，v s 墨 例3 3 1 设历= ( q ，z ，m ) 是f f s a ，定义上的一个关系董： v x ，y x ，x 三y m ( x ) = m ( 少) 构造一个新的模糊自动机m = ( a ，x 毫，m ) 满足 m ( 【x 】) = m ( 工) 定义f ：石一z 兰，善( 功= x 】，v x x ，显然f 是朋对m 的覆盖。 定义3 3 3 设m i = ( q ，五，m i ) ，i = l ，2 是f f s a 彳是有限集，厂是艇峨xg 上 的函数，瓦是z 五到z ，f _ 1 , 2 上的满上的映射。 设g = 锄，吼，吼) ，q = 幻，q q m ) ，定义吩【o ，l 】”，m r = ( 刀z f ) 。硼 m o ：( q l q 2 ) x x ( q l q 2 ) 专 0 ，l 】，v a x 如下： 1 2 第三章模糊有限自动机的l ( r o n e c k e r 积 m ，( 口) = m 。( 万。( 厂( 口) ) ) 0 m ：( 乃( 厂( 以) ) ) 则( ( q l q 2 ) ，霄，m ，) 称为强和的广义 k r o n e c k e r积，记 1 7 1 lq m 2 = c c q , q 2 ) ，x ，m ，) 。 若彳竭五且厂是恒等映射，则聊i 圆聊2 称为铂和掰2 满k r o n e c k e r 积，记为 现，他； 若墨= 五，x = ( 口。，口：) l a ，墨，江1 ，2 ，q = a ：) ，厂是恒等映射，则m 。 m ：称为 砚和限制k r o n e c k e r 积，记为铂 引理3 3 1 设m i = ( q f ，置，m i ) ，江l ，2 是f f s a q l = q l , 9 2 ，q 。) ， 0 2 = q l , 9 2 ，q 。) ，考虑广义k x o n e c k e r 积碍幸，则 ( 1 ) m ，( 八) = m 。( 八) ) m ：( ) ( 2 ) m ，( 瓦砭瓦) = m 。( 刀。( 厂( 瓦) ) 万。( 厂( 瓦) ) ) 0 m ：( 乃( 厂( 互) ) 7 ：( 厂( 瓦) ) ) 其中j ，i = 1 ，2 ， 证明：( 1 ) m ，( 八) o ，1 】”跏m ，m ，( ) = l 。由于 m l ( ) 【0 ，1 y l x ? 1 1 1 m 2 ( 八) 0 ，l 】”。”，所以m i ( ) o m 2 ( 人) 【0 ，1 “”。”， m l ( a ) o m 2 ( ) 1a m ：( 八) 0 17 i 一1 n m x n m 01a 尬( 八) j n m m 即证。 ( 2 ) 由推论3 2 1 知，左边= m r ( 瓦瓦瓦) = m r ( 瓦) m ，( 乏) m r ( 瓦) ，而 肘r ( 弦) o ，1 】”。”，f = 1 ，2 n ，则m r ( 互瓦a n ) o ，l 】”。” 又m 。( j r 。( (