（基础数学专业论文）格值有限自动机的分类及其最小化问题.pdf

格值有限自动机的分类及其最小化问题 基础数学 研究生汪洋 指导教师莫智文( 教授) 论文摘要：近年来，得益于格值文法及其语言的深入发展，研究和完善格值有 限自动机理论日益成为热点问题本文研究了取值于格半群的格值有限自动机的分 类和格值有限自动机的状态最小化算法，主要采用比较与类比、分析与综合、归纳 与反证等理论推导方法并进行实验仿真和实例验证具体工作概括如下：提出格值 有限自动机的分类，并分别讨论了不同形式的m e a l y 格值有限自动机和m i z u m o t o 格值有限自动机的最小化算法 关键词：格半群；格值有限自动机；分类；最小化 第i 页 t h ec l a s s i f i c a t i o no fl a t t i c ef i n i t ea u t o m a t aa n dt h e i r m i n i m i z a t i o na l g o r i t h m s 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 ：w a n gy a 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 ：i nr e c e n ty e a r s ，r e s e a r c h i n ga n dc o m p l e t i n gt h et h e o r yo fl a t t i c e f i n i t ea u t o m a t ah a si n c r e a s i n gb e c o m eh o ti s s u e sd u et ot h ed e e pd e v e l o p m e n to f l a t t i c e - v a l u e dg r a m m a r sa n dt h e i rl a n g u a g e s t h i st h e s i si sc o n c e r n e dw i t ht h e c l a s s i f i c a t i o no fa u t o m a t at o o kv a l u ei nl a t t i c e - o r d e r e dm o n o i d sa n dt h em i n i - m i z a t i o na l g o r i t h m so fs u c ha u t o m a t a w eu s et h em e t h o d ss u c h8 sc o m p a r i s o n a n da n a l o g y , a n a l y s i sa n ds y n t h e s i s ，i n d u c t i o na n dc o u n t e r e v i d e n c e ，e t cf o rt h e - o r e t i c a ld e r i v a t i o n ，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 o v e r i f yt h ef e a s i b i l i t yo fo u ra l g o r i t h m m o r es p e c i f i c a l l y , t h em a i nr 髑u l t sa r e s h o w nb e l o w ：w o r ko nt h ec l a s s i f i c a t i o no fl a t t i c ef i n i t ea u t o m a t a ，a n dw o r k o nt h em i n i m i z a t i o na l g o r i t h m so fm e a l yl a t t i c ef i n i t ea u t o m a t aa n dm i z u m o t o l a t t m ef i n i t ea u t o m a t a k e yw o r d s ：l a t t i c e - o r d e r e dm o f i o i d ；l a t t i c ef i n i t ea u t o m a t a ；c l a s s i f i c a t i o n ； m i n i m i z a t i o n 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师墓蟹塞熬援指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何 其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印刷 版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库供检 索；2 ) 为教学、科研和学术交流目的，学校可以将公开的学位论文或解密后的 学位论文作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 论文作者签名： 2 0 0 9 年4 月 己i 吉 ji 目 1 9 6 5 年z a d e h 教授提出了模糊集合论f 4 6 】4 7 】，首次用“隶属函数”这个概 念来描述现象差异的中间过度，从而突破了古典集合论中属于或不属于的绝对 关系这一开创性的工作，标志着数学的一个新的分支一模糊数学的诞生模 糊数学所研究的事物的概念本身是模糊的，即一个对象是否符合这个概念难以 确定这种由于概念外延的模糊而造成的不确定性称为模糊性用在f 0 ，1 上取 值的隶属函数就描述这种模糊性模糊集合是客观存在的模糊概念的必然反映 模糊概念就是边界不清晰，外延不确定的概念 伴随着计算机和信息网络技术的发展在我们用计算机进行问题求解时，需 要用适当的数据进行问题表示，再通过适当的算法分析数据以获得问题的结果 在这一过程中，形式语言与自动机理论给出了对问题进行抽象和形式化表示的 模型，并且通过研究这些模型的性质及其变化方法来对这些问题进行讨论，因 而自动机理论与形式语言在计算机科学的文本处理、编译程序、硬件设计、程 序设计语言与人工智能等应用领域发挥着重要作用有穷自动机作为计算理论 中最简单的数学模型，它是计算机科学的理论基础，为现代计算理论提供可靠 的形式理论，而且与神经网络、数学模型等领域密切相关 模糊集理论率先由w e e 【3 8 】在1 9 6 7 年应用于自动机领域，第一个模糊有 限自动机的数学模型随之诞生s a t o n s 在文献f 3 1 】中定义了一种最大最小型模 糊有限自动机，l e e 和z a d e h1 9 】在1 9 6 9 年也提出了确定型和非确定型模糊有 限自动机的概念，具有模糊初始状态的模糊有限自动机首先是由m i z u m o t o 等 人f 1 8 1 提出并且利用模糊矩阵和模糊向量的工具进行研究的同年w 砘和f u 1 3 9 】定义了有模糊输出函数的模糊有限自动机，a s a i 和k i t a j i m af 1 1 于1 9 7 1 年 提出了m e a l y 型和m o o r e 型模糊有限自动机并证明了它们的等价性，近几年来 m a l i k 等人【1 9 】也给出了另一种模糊有限自动机的定义( f u z z ys w i t c h i n ga n d a u t o m a t a ：t h e o r ya n da p p l i c a t i o n s ) ) f 7 1 ，( 0 ，b 0 使得a b = 0 ，则称( l ，e ) 含有零因子例如当 l = 0 ，1 】且= ( a + b 一1 ) v0 ，v a ，b l ，即取l u k a s i e w i c z 扣模时，容易验证 此时( 【0 ，1 】，v ) 为格半群，且易知该格半群含有零因子，如取a = 0 2 ，b = 0 3 ， 此时a ，b 0 ，而a b = 0 特别注意我们后几章只涉及该定义的前三条，即要求 l 为有限格半群 ( 3 ) 对于取值于格半群( l ，v ) 的矩阵a = ( ) m n 和b = ( b o ) n l 定义 矩阵的乘积运算为s u p 一复合，即a b = ( ) m l 其中= v ( a i k ) ，因 为乘法运算满足结合律，容易验证矩阵乘积满足结合律，即x n ，玩x l ，g x d ， ( a b ) c = a ( b c ) 第顶 毕业论文 第一章预备知识 例1 2 1 【1 1 】( 1 ) 设( l ，v ，a ) 为分配格，取= a ，则l 成为格半群，单位 元为1 ( 2 ) 设( l ，v ) 为格半群，以l ( n ) 表示取值于l 的n 孔维矩阵全体，其 上的乘法运算( 记为o ) 规定为矩阵的s u p 一合成，而avb = d = ( d o ) ，应f = vb o ，则( l ( n ) ，o ，v ) 为格半群，单位元为e = d i a g ( e ，e ，e ) ，即主对角线 上的元素为e 的对角矩阵l ( n ) 上的乘法运算一般不可换，即使l 上的乘法运 算是可换的 口 下面我们看看完备格值矩阵先约定l 为一个有限格，用l = ( l ，v ) 表 示一个格半群，且( l ，s ) 是无零因子的序半群 定义1 2 2 【1 6 】设a = ( 口玎) m n 是一个m 扎矩阵，如果a 玎l ，则称a 为格值矩阵 口 定义1 2 3 【l6 】设a = ( n 订) m 竹，b = ( 七) n p 分别是m n 和礼xp 的格 值矩阵定义a 和b 的乘积为c = ( c 詹) m p = a b ，其中q 七= ( n 巧啄) 口 定义1 2 4 【1 6 】设a = ( n a ) m 乱是一个格值矩阵，如果v a i j l j = 1 ，2 ，n ) o ( i = 1 ，2 ，m ) ，则称a 为完备格值矩阵，简称为完备的， 否则称a 为不完备的 定理1 2 1 【1 6 】任意两个完备格值矩阵的乘积仍为完备格值矩阵 第8 页 口 口 毕业论文 第一章预备知识 1 3 格半群意义下模糊集、映射及等价关系的模糊扩张 定义1 3 1 1 1 】设x 是经典集合，格值模糊集是集合x 到格半群l 上的 一个映射，记作a ：x l ，比x ，a ( z ) l 口 以下假设l 是格半群，y ( x ) = a ：x l i a 是l 值模糊集】，即以 y ( x ) 表示x 上格值模糊集的全体 我们仍根据z d a h e 扩张原理来考虑格半群意义下映射的扩张问题先来回 顾一下扩张原理，这时，模糊集的真值集是l = 【0 ，1 ( 完备的分配格) ，我们关心 的是它的v ，a 运算 定义1 3 2 【1 1 】 ( 扩张原理) 设x ，y 为非空经典集合，映射f ：x 一 比x ，z 一，( z ) ，f ( x ) y 可以诱导出一个y ( x ) 到，( y ) 的映射， ，：厂( x ) 一厂( y ) ，v a 芦( x ) ，a 卜，厂( a ) ，f ( a ) 厂( y ) ， 以及一个，( y ) 到y ( x ) 上的映射， f - 1 ：芦( y ) 一厂( x ) ，v b 厂( y ) ，b f - 1 ( b ) ，f - 1 ( b ) ，( x ) 这里f ( a ) 和f - 1 ( b ) 的隶属函数分别定义为 即 v y ey , f ( a ) ( y ) = 心刖鞴j , - 1f 沪- l ( y 彩) 细 v y y ，( a ) ( v ) = v a ( z ) ， 和 v z x ，y - 1 ( b ) ( z ) = b ( ，( z ) ) 以上两个映射通常称为扩张映射，本文只关心厂( x ) 到厂( y ) 上的映 射另一方面，我们可将映射，：x y 看成是x 到y 的二元关系，即 v ( z ，y ) x y ，若z y - 1 ( ) ，则f ( x ，y ) = 1 ，否则，( z ，y ) = 0 这时第一个扩 张映射可以表示为 ，( a ) ( y ) = v a ( x ) a ，( z ，秒) 1 0 1 3 w a n g y a n g 1 6 3 c o m 第9 页 口 毕业论文 第一章预备知识 以此为基础，以下设( l ，v ) 为格半群，e 是乘法单位元，x ，y 是任意非空 经典集合，尸( x ) ，芦( y ) 是格半群l 上格值模糊集的全体我们进一步来考虑格 半群意义下映射的模糊扩张问题 定义1 3 ，3 【1 1 】设叉，y 是非空经典集合，映射9 ：x y 为通常的 映射，夕可诱导一个户( x ) 到尸( y ) 的格值模糊映射仍记为g ：厂( x ) 一 厂( y ) ，v a 厂( x ) ，a 一夕( 4 ) ，g ( a ) 厂( 1 ，) 这里g ( a ) 的隶属函数可定义为： 夕( a ) ( 矽) = va ( z ) ，v y y 毒g 一1 ( ) 同样，我们可将夕看成是x 到y 的二元关系，但因我们关心的是格半群l 上的，v 运算，因此，我们定义v ( x ，y ) x y ，若z g - 1 ( 可) ，则g ( x ，y ) = e ( e 是己中乘法运算的单位元) ，否则g ( x ，y ) = o 此时有 9 ( a ) ( 可) = v 【a ( x ) 9 ( z ，可) ，v y y x e x 口 进一步，我们来考虑模糊映射的模糊扩张问题 定义1 3 4 【1 1 】 设x ，y 是非空经典集合，模糊映射g ：x 一厂( y ) 可诱 导一个丁( x ) 到厂( y ) 的映射，这个扩张映射仍记为g ：芦( x ) 一歹( y ) ，比 x ，z 一9 ) ，g ( x ) 户( y ) 为简单起见，我们可将夕看成x 到y 的二元模糊 关系，即v ( x ，y ) xxk g ( x ，y ) = 夕( z ) ( 可) ，v a 厂( x ) ，g ( a ) 厂( y ) ，其隶属函 数定义如下： 9 ( a ) ( ) = vm ( z ) 9 ( z ，3 ，) 】，v y y x e x 口 最后，我们来考虑模糊等价关系的模糊扩张问题 定理1 3 1 设( l ，v ) 为格半群，r 是q 上的格值等价关系，我们用 r = ，q ) l z r ( p ，口) 入，p ，口q ) 来定义r 的k 截集，则凡是q 上的等价 关系，这里冗 o ，入l 证明显然瞰满足自反、对称、传递性 1 0 1 3 w a n g y a n g 1 6 3 c o m 第1 0 页 口 毕业论文 第二章m e a l y 格值有限自动机的最小化算法 按照程伟、莫智文【2 提出的模糊有限自动机的分类思想：自然我们提出格 值有限自动机的分类：一种是具有输出字符功能而没有初始状态的m e a l y 格值 有限自动机；另一种是具有初始状态而没有输出字符功能的m i z u m o t o 格值有 限自动机于是第二、三章主要研究了它们的最小化问题就对应于m e a l y 模 糊有限状态自动机的一类格值有限自动机m e 出格值有限自动机而言，最重 要的是获得合理的格值状态转移函数和格值状态输出函数之间的关系 本章主要研究了三个不同形式的m e a l y 格值有限自动机，探讨了相应的最 小化形式，并给出了对应的最小化算法 第一节研究了标准形式的m e a 匆格值有限自动机m = ( q ，x ，y ；p ，u ) ，其中 q ：有限状态集；x ：有限输入字符集；y ：有限输出字符集；p ：qxx xq l 是格值状态转移函数；u ：qxx x y 一三是格值状态输出函数满足以下条 件： ( 1 ) v p q ，a x ，3 q q ，s t p 0 ，口，q ) 0 考q b y ；s t u 0 ，a ，b ) o ； ( 2 ) v p q ，口x ，3 b y ；s t u ，n ，b ) 0 号3 q q ，s t p ，n ，q ) 0 第二节研究了格值有限序列机m = ( q ，x ，y 6 ) ，其中q ：有限状态集；x ： 有限输入字符集；y ：有限输出字符集；6 ：q xxy q 一三是格值状态转 移一输出函数 第三节研究了基于格值模糊字符串的m e a l y 格值有限自动机的扩张模型 m = ( q ，( x ) ，p ，u ) ，其中q ：有限状态集；x ：有限输入字符集：厂( x ) ：输入 字符集x 的格值模糊字符的集合；y ：有限输出字符集；p ：q 歹( x ) x q l 是扩张的格值状态转移函数；u ：qx ，( x ) y 一是扩张的格值状态输出 函数 第1 1 页 第二章m e a l y 格值有限自动机的最小化算法 2 1 基于强等价状态的m e a l y 格值有限自动机的最小化 对m e a l y 模糊有限状态自动机，因其具有模糊状态输出函数，文f 3 1 f 4 】f 1 9 1 往 往利用输出函数的隶属度相等来定义两状态等价，进而定义两自动机等价，从 而得到状态等价类，最后得到此m e a l y 模糊有限状态自动机的最小化算法本 节重新引入了强等价，等价，弱等价三种状态等价关系，使其具有更广泛的应用 性并在强等价条件下，给出m e a l y 格值有限自动机的最小化形式及相关算法。 定义2 1 1 6 】设( l ，v ) 为格半群，标准形式的m e a l y 格值有限自动机 是五元组m = ( q ，x ，卢，u ) ，其中q ：有限状态集；x ：有限输入字符集；y ：有 限输出字符集；弘：q x q 一己是格值状态转移函数；u ：q x y l 是格值状态输出函数满足以下条件： ( 1 ) 坳q ，a x ，j g q ，s t 肛 ，a ，g ) 0 昌3 b s t u 0 ，a ，b ) 0 ； ( 2 ) v p q ，a x ，3 b es t u 0 ，a ，b ) 0 = 专刍g q ，s t 肛 ，a ，口) 0 扩张格值状态转移函数和输出函数分别记为矿和u ，x ( y ) 表示集合 x ( y ) 上的自由么半群，空字a 是其单位元 p + ：q x 。q l ， 。旷p ， ，g ，= ，若妻丢q 卢。，g ) = v 扩 ，z ，r ) p ( r ，o ，口) 】 u ，x a ，u b ) = vp 0 ，z ，秽) 矿0 ，2 ，r ) u ( r ，a ) r q v p ，g q ，z x ，a x 第1 2 页 口 毕业论文 ， = l 可它 一 一其 r 若叽 ， e x fl j j q 奶 z 矿 ” 护 第二章m e a l y 格值有限自动机的最小化算法 定义2 1 2 设( l ，v ) 为格半群，舰= ( q t ，x ，k 地，姚) 是m e a l y 格值有 限自动机，其中q i q i ，i = 1 ，2 ，对任意z x 。，y y ，例为字符串z 的长度， l y l 为字符串y 的长度下面定义m e a l y 格值有限自动机的强等价，等价，弱等 价三种状态等价关系： ( 1 ) q l 和9 2 强等价( q l 圭q 2 ) 号比x ，y y ，vp ；( 9 1 ，z ，p ) = v 店( q 2 ，z ，p ) 且u ；( 9 1 ，z ，y ) = 呓( 口2 ，z ，y ) ； ( 2 ) 对每一个正整数k ，q l 和9 2k - 强等价( 9 1 q 2 ) 车号v x x ， k ，y y 。，vp ：( 口1 ，z ，p ) = v 成( 9 2 ，z ，p ) 且u ；( 口l ，z ，y ) = 咙( 口2 ，z ，s ，) ； ( 3 ) 尬和m 2 强等价( 尬圭) 号v q l q 1 ，3 q 2 q 2 ，s q 1 圭q 2 且 v q 2 q 2 ，2 q l q 1 ，s t 9 2 圭q l ； ( 4 ) 对每一个正整数k ，m 1 和尬k 强等价( 尬- - km 2 ) 净v q l q i ，3 q 2 q 2 ，s t q l - - kq 2 且v 口2 q 2 ，q q l q 1 ，s t q 2 - - kq 1 口 定义2 1 3 q l 和口2 等价( q l 兰9 2 ) 等号比x ，y y ，u ；( q 1 ，z ，y ) = 以( 9 2 ，z ，y ) 定义2 1 4q l 和q 2 弱等价( q l q 2 ) 净v x x ，y y + ，s l z x ，s t i z i = 且u ；( 口l ，z ，y ) = 嵯( 口2 ，z ，秒) ；同时3 1 2 7 x ，s = 且啦( 9 2 ，z ，y ) = u ；( 口1 ，z ，可) 口 若尬= 尬= m ，则强等价壶，等价三，弱等价及其相应k 强等价气， k 等价三七，k - 弱等价知都是等价关系，满足自反性，对称性，传递性q 上的 等价关系唯一决定一个q 上的划分，我们记对应于强等价关系圭和k - 强等价 关系- - k 的划分依次为q 圭和q 圭知，其余类似文【3 】【4 】分别研究了等价状态 下和弱等价状态下的m e a l y 模糊有限自动机及其最小化算法，基于等价状态和 第1 3 页毕业论文 第二章m e a l y 格值有限自动机的最小化算法 弱等价状态的m e a l y 格值有限自动机可以作类似研究以下重点讨论基于强等 价状态的m e a l y 格值有限自动机的最小化 定义2 1 5 设( l ，v ) 为格半群，m = ( q ，x ，y p ，u ) 是m e a l y 格值有限 自动机，p ，g q ，则 ( 1 ) 若p 圭g 哥p = q ，则m 是一个状态最小化格值自动机； ( 2 ) 若存在一个输出字符串y 。，使得“，函，x ，y ) u ( g ，z ，y ) 且存在一 个状态r q ，使得矿，z ，r ) 旷( g ，z ，) ，则称字符串z x 。可以强区分状 态p 和g 口 定理2 1 1 【6 】设序半群( l ，e ) 不含零因子，m = ( q ，x ，y p ，u ) 是一个 m e a l y 格值有限自动机，则l ( a ) 和2 ( a ) 相互等价；当为格半群( 五，v ) ，郎乘 法对有限上确界运算v 有分配律，且跏q ，a x ，vp 妇，a ，r ) = l 时：l ( b ) 和2 ( b 1 相互等价： l ( a ) v 扫q ，z x ，3 q q ，s t 弘 ，。，q ) 0 号3 y y ：s t ，u 0 ，z ，暑，) o ； l ( b ) 坳q ，z x ，3 y r s t u ( p ，z ，y ) 0 = 令3 q q ，s t p ，x ，q ) 0 2 ( a ) v p q ，z x ，3 q q ，s t p p ，z ，口) 0 毒j 矽y 。，s t u p ，z ，y ) 0 ； 。 2 ( b ) 印q ，z x ，3 y y ，s t 甜+ ，2 ，y ) 0 砖王窜q ，s t 芦0 ，z ，q ) 0 口 定理2 1 2 设( l ，v ) 为格半群，m = ( q ，x ，y ，弘，u ) 是一个m e a l y 格值 有限自动机，则存在一个状态最小化的m e a l y 格值有限自动机和m 强等 价其中= ( q 奎，x ，k ，) ，我们定义： 弘( 嘲，z ，【翻) = v p ( s ，z ，t ) ， s , t e q ，8 圭p t 白 ：；l ( 纠，z ，y ) = v ( s ，z ，) _ q ，8 ：- p 第1 4 页 毕业论文 第二章m e a l y 格值有限自动机的最小化算法 证明 首先证明是一个m e a l y 格值有限自动机设嘲q 圭 ，z x ，存在【g 】q 圭，使得p ( 嘲，z ，【g 】) 0 ，由的定义，存在 s ，t q ，s 圭p ，t 圭q ，使得旷( s ，z ，t ) 0 ，由于m 是一个m e a l y 格值有限自动 机，故存在y y 。，使得u ( s ，z ，y ) 0 所以( 渊，z ，y ) u + ( s ，z ，y ) 0 故 定义2 1 1 条件( 1 ) 成立 设嘲q 圭，z x 4 ，存在y y ，使得u ：( 嘲，2 ，y ) 0 由的定义， 存在8 q ，s 圭p ，使得u ( s ，z ，y ) 0 ，由于m 是一个m e a l y 格值有限自动机， 故存在t q 使得矿( s ，z ，t ) 0 所以p 毛( 嘲，z ，【t 1 ) 旷( s ，z ，t ) 0 故定义 2 1 1 条件( 2 ) 成立 所以，m m = ( q 圭，x ，y ；，u m ) 是一个m e a l y 格值有限自动机 下面证明是状态最小化的m e a l y 格值有限自动机 设纠， q 】q 未且设捌圭【g 】，则对任意z x ，可y + ，存在 【d 】q 壶，渊圭【口】乍旁( l o ，z ，y ) = 蠊( 【g 】，z ，可) 且vp 毛( 纠，z ，【d ) = o e q - v 弘( 【g 】，z ，【d 】) 即存在s 圭p ，t 圭g ，7 圭0 ，使得u + ( s ，z ，y ) = u ( 厶z ，y ) 且 o e q - v 旷( s ，z ，7 ) = v 旷( t ，z ，- ) 由定义2 1 2 ，s 圭t ，所以p 圭g ，故捌= g 】所以 是状态最小化的m e a l y 格值有限自动机 对任意p q ，z x + ，y y ，由定义2 1 2 ，u + 函，z ，y ) = vu ( s ，z ，耖) = ( 嘲，z ，彭) 且vp ，z ，q ) =vvp ( s z ，t ) = v弘麓( 嘲，z ，【口】) ，故p 圭m ，所以m = 口 设( l ，v ) 为有限格半群，其中i l i = k 给定一个m e a l y 格值有限自动 机m ，我们可以获得一个与之等价的状态最小化的m e a l y 格值有限自动机 m m = ( q 圭，x ，f ，) 设现，z 2 ，z n x ，q 圭可以由以下算法求得： s t e p l ：( 初始化)令 = 1 ，由u ( 2 1 ) ，u ( z 2 ) ，一( z n ) 和 p ( z 1 ) ，肛( z 2 ) ，p ( z n ) ，我们可以获得相对于圭1 的等价类q 圭1 ； s t e p 2 ：( 循环) i ：= 2 ，3 ，由定义2 1 1 ，矿( z l z 2 瓤) = u ( 孔) p ( z i ) u ( z l z 2 戤一1 ) 和p ( x l x 2 x i ) = p ( z i ) p x l x 2 z 一1 ) 计算出 扩( x l x 2 黾一1 戤) 和矿x l x 2 戤) ，进而由等价类q 圭i 一1 求得等价类q 气 1 0 1 3 w 蛆g y a n g 1 6 3 c o r n 第1 5 页 毕业论文 第二章m e a l y 格值有限自动机的最小化算法 若i q 气 = 死或者i = ( k 一1 ) n ，转第3 步； s t e p 3 ：( 输出结果) i q 圭tl = i q 圭1 2 2 基于行为映射的格值有限序列机的最小化 文【4 1 中定义了基于完备剩余格的格值有限序列机，本节修改了格值有限序 列机的真值域一即在格半群意义下定义并讨论了其相关性质，进而提出格值有 限序列机的行为映射，给出计算行为映射像的算法最后定义状态等价关系，基 于此得到格值有限序列机的最小化算法 首先给出基于格半群的格值有限序列机的定义： 定义2 2 1设( l ，v ) 为格半群，格值有限序列机( 记为l - f s m ) 是 四元组m = ( q ，x ，6 ) ，其中q = 口1 ，q 2 ，) 是有限状态集；x = 口1 ，a 2 ，) 是有限输入字符集；y = b l ，b 2 ，轨) 是有限输出字符集； 6 l q x x x y x q 是q xxyxq 的格值模糊子集，称为格值状态转移一输出 函数 对单