（计算机应用技术专业论文）有限自动机运算后的状态最小化.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究在做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律责任由本人承担。 论文作者签名：盔鱼日期：2q q 垒生! ! 旦 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权贵，t i 大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：盈盘导师签名： 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 摘要 本文在自动机理论的基础上，研究了表示正则语言的确定型有限自动机的最小化填表 算法和确定型有限自动机经并、交运算后的最小化问题。 本文首先介绍了确定型有限自动机的一种最小化算法一填表算法 3 4 ，对该算法进行 了正确性证明和计算复杂性分析。 其次，通过对该填表算法分析、研究，发现原算法存在的两个问题：一是不能处理不 完全确定型有限自动机，二是预处理过程标记初始可区分状态对可进一步优化。基于此，分 别对余不可达状态的性质和初始标记状态对的本质进行了详细分析，进而惨改并细化原填表 算法。最后对修改后的新算法进行了正确性证明和计算复杂性分析。 随后。通过实例进一步从实践上验证新旧填表算法的正确性，且通过观察和比较不同 自动机在两种算法上的运行结果。找出了影响新旧算法运行的4 个因素，同时通过表格形式 对新旧填表算法的运行情况作一分析总结，再详述了新算法对已有算法的5 个改进之处。 最后，基于改进填表算法的输入条件，对确定型有限自动机的并、交运算分别提出了 一种合理的构造方法，使得构造后得到的自动机能通过新填表算法最小化，并对构造方法的 正确性予以了证明。 关键词；确定型有限自动机、正则语言，运算、算法。 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 a b s t r a c t i nt h i sp a p e r , b a s e do na u t o m a t at h e o r y , t h ef i l lt a b l ea l g o r i t h mw h i c hc a nm i n i m i z e d e t e r m i n i s t i cf i n i t ea u t o m a t a ( d f a ) t h a tr e p r e s e n t sar e g u l a rl a n g u a g ea n dt h em i n i m i z a t i o n p r o b l e mo nt h ea u t o m a t o nw h i c hi st h er e s u l to f t h eu n i o no ri n t e r s e c t i o no p e r a t i o no nt w od f a s h a v eb e e ns t u d i e d f i r s t l y , w eh a v ei n t r o d u c e do n em i n i m i z a t i o na l g o r i t h m , f i l lt a b l ea l g o r i t h m 【3 4 1 ，w h i c h c a nm i n i m i z eag i v e nd f a h a v es h o w nt h ec o r r e c t n e s sa n dh a v ea n a l y z e dt h ec o m p u t a t i o n c o m p l e x i t yo f f i l lt 曲l ea l g o d t h m s e c o n d l y ，t h r o u g ha n a l y z i n gt h ep r e v i o u sa l g o r i t h m ，t w op r o b l e m sh a v eb e e nf o u n d o n ei s t h ea l g o r i t h mc a n n o td e a lw i t ht h en o n - c o m p l e t ed f a ，a n dt h eo t h e ri s ，i np r o p r o c e s so ft h e a l g o r i t h m ，t h en u m b e ro ft h ei n i t i a lm a r k e ds t a t ep a i r si sa b l et ob ei n c r e a s e d b a s e do nt h i s ，w e a n a l y z e dt h ep r o p e r t i e so fc o a c c e s s i b l es t a t e sa n dt h ee s s e n c eo ft h ei n i t i a lm a r k e ds t a t ep a i r si n d e t a i l f u r t h e rm o r ew em o d i f i e da n dc i r c u m s t a n t i a t e dt h eo r i g i n a la l g o r i t h m ，a n ds h o w e dt h e c o r r e c t n e s sa n da n a l y z e dt h ec o m p u t a t i o nc o m p l e x i t yo f t h em o d i f i e da l g o r i t h m t h i r d l y w eh a v ev e r i f i e dt h ec o r r e c t n e s so f t h ea b o v et w oa l g o r i t h m sb ys o m ei n s t a n c e s w e a l s oh a v ef o u n df o u r 伍e t o r si n f l u e n c i n gt h er e s u l to ft h et w od i f f e r e n ta l g o r i t h m s ，s u m m a r i z e d t h e s er u n n i n gc a s e s ，a n dp r e s e n t e df i v ei m p r o v e dp l a c e sf r o mt h eo r i g i n a lo n e f i n a l l y , w eh a v eg i v e nt h et w oc o n s t r u c t i o n sf o rt h eu n i o no ri n t e r s e c t i o no p e r a t i o no nt h e t w od f a s t h ea u t o m a t af r o mt h ec o n s t r u c t i o n sc a nb em i n i m i z e db yt h en e wa l g o r i t h m w eh a v e s h o w nt h ec o r r e c t b e s so f t h et w 0c o n s l r u 两o i l si nt h ee n d k e y w o r d s ：d e t e r m i n i s t i cf i n i t ea u t o m a t a , r o g u l a rl a n g u a g e , o p e r a t i o n , a l g o r i t h m 2 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 前言 有限自动机( f i n i t ea u t o m a t a ) 是一种研究离散事件动态系统的数学模型，是为研 究有限内存的计算过程和某些语言类而抽象出来的一种计算模型，是许多重要类型的硬件和 软件的有用模型 2 0 。2 3 。它出现于2 0 世纪4 0 年代，1 9 4 3 年麦克卡赛( m e c u l l o c h ) 与皮 特斯( p i t t s ) 建立了模拟神经网络的自动机 6 。1 9 5 6 年，莫尔( m o o r e ) 建立了描述计算机 时序的概念。此后，自动机理论迅速发展，与计算机技术密切结合，在人工智能、自动控制 等领域有着广泛的应用 2 ，7 ，2 s 。用有限自动机这种模型，我们能区分出哪些类型的问题是 计算机能有效解决的，雨对一些看似有解，但实际上却找不刭一个算法来求解的何愿，计算 机是不可解的。 有限自动机是计算机科学的重要基石，是自动机理论的研究对象，它可分为确定型有限 自动机( d e t e r m i n i s t i c 脚据a u t o m a t a ，d f a ) 和非确定型有限自动机( n o n - d e t e r m i n i s t i c 励妇a u t o m a t a ，n f a ) 两种。非确定型有限自动机可转化为确定型有限自动机 3 0 。确定 型有限自动机与非确定型有限自动机识别的语言都是正则语言。由于正则语言的良好性质， 许多为其它自动机( 下推自动机或图灵机) 不能判定的问题，在有限状态自动机的情形下， 都可以得到判定，并且存在有效的算法 1 9 。3 5 。 有限自动机等价判定问题以及由此产生的最小化问题的研究，在模糊自动机、正规语言、 正规表达式等方面具有重要影响 1 2 ，2 2 ，2 6 。在许多识别有限语言的自动机例子中，常会考 虑能否找到识别相同语言的更小自动机。对确定型有限自动机来说，最小确定型有限自动机 就是有着最少状态且能识别相同有限语言的确定型有限自动机。 确定型有限自动机最小化算法的核心 1 ，8 是把一个确定型有限自动机的状态集分成一 些不相交的子集，使得任何不同两子集的状态都是可区别的，而同一子集中的任何两个状态 都是等价的。也就是说，一台最小化的确定型有限自动机，它没有多余状态并且它的状态中 没有两个互相等价。一台有限自动机可以通过消除多余状态和合并等价状态而转换成一个最 小的与之等价的有限自动机。根据m y h i l l - n e r o d e 定理 9 ，在同构意义下接受一个正则语 言的最小状态确定型有限自动机是唯一的。也即。给定任何两个等价的最小状态z ，总 是能找到办法重新命名状态，使得这两个d 剐成为相同的。 由于正则语言与有限自动机的等价性，以及正则语言在并、交运算下的封闭性 2 1 ，3 1 ，3 6 ，使得多有限自动机经并、交运算后所得必然为一有限自动机，所识别语言必然 为一正则语言。因此，运算后所得确定型有限自动机必然可被最小化。但由于运算中会带来 一些新的多余状态，故如何去除这些多余状态以使运算后所得的确定型有限自动机能通过现 有的确定型有限自动机最小化算法得以最小化就变成了一个值得思考的问题。 下面，介绍一下本文所做的工作和本文的组织结构。 本文在自动机理论的基础上，研究了确定型有限自动机的最小化填表算法和确定型有限 3 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 自动机经并、交运算后的最小化问题。 在第一章，简要介绍了本课题相关的预备知识。阐述了自动机、正则语言及状态间相似 和等价关系的基本概念、性质和一些与本论文有关但未给出证明的基本结论。 第二章，介绍了确定型有限自动机的一种最小化算法一填表算法 3 4 ，对该算法进行了 详细描述、正确性证明和时空复杂性分析。其为本文给出的新算法的基础。 第三章，通过对已有填表算法分析、研究，发现原算法存在的两个问题：一是不能处理 不完全确定型有限自动机，二是预处理过程标记初始可区分状态对可进一步优化。基于此， 分别对余不可达状态的性质和初始标记状态对的本质进行了详细分析，进而修改并细化原填 表算法，最后对修改后的新算法进行了正确性证明和计算复杂性分析。 第四章，通过实例进一步从实践上验证新旧填表算法的正确性，且通过观察和比较不同 自动机在两种算法上的运行结果：首先找出了影响新旧算法运行的4 个因素：确定型有限自 动机的完全性、给定确定型有限自动机有无余不可达状态和初始划分 d o ，d ，d ， 中，值 的大小、输入字符表的元素个数i z i ；其次通过表格形式对新旧填表算法的运行情况作一 分析总结；最后详述了新算法对已有算法的5 个改进之处：能处理不完全确定型有限自动机： 一定程度上减少了处理的确定型有限自动机的状态复杂度；一定程度上减少了需判断的总状 态对个数；一定程度上增加了预处理中初始标记状态对的个数，从而减少了随后余下状态对 在输入字符下的判断次数；更加详细描述了算法的运算步骤。 第五章，基于改进填表算法的输入条件，对确定型有限自动机的并、交运算分别提出了 一种合理的构造方法，使得构造后得到的自动机能通过新填表算法最小化，并对构造方法的 正确性予以了证明。 第六章，总结本文所做工作，并对下一步的工作作出展望。 最后为致谢和列出参考文献。 4 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 第一章预备知识 1 1 自动机理论基础 有限自动机( 砌i t ea u t o m a t a ) 是为研究有限内存的计算过程和某些语言类而抽象 出来的一种计算模型，是许多重要类型的硬件和软件的有用模型。它可分为确定型和非确定 型两种。非确定型有限自动机( 刚) 可转化为确定型有限自动机( z w 谢) 。 在本章中，列出相关的基本概念和一些与本论文有关但未给出证明的基本结论，详细的 描述和证明可参见 3 ，4 ，5 ，1 7 1 1 1 确定型有爱自动机( a 黝) 基本4 ，i 客 定义1 ，1 1 确定型有限自动机d f a 是一个5 元组( q ，j ，吼，f ) ，其中 ( 1 ) q 是一个有穷集合，叫做状态表。 ( 2 ) z 是一个有穷集合，叫做字母表。 0 ) 万：q z _ q 是转移函数。 “) q o q 是起始状态 ( 5 ) f q 是接受状态集( 终态集) 说明：1 ) d f a 的确定性表现在转移函数占：q x - - q 为一单值函数。也就是说，对任何 状态q q 和输入符号口z ，8 ( q ，4 ) 唯一地确定了下一个状态。 当对任意状态q q 和任意输入符号口，a ( q ，砖q ( 不为空状态) 时，称 该d 芦为一完全d 明。( 即映射完整) 2 ) q o q 为唯一的起始状态，又称初态。 3 ) 可将转移函数扩展到串。如果子是扩展函数，则从艿构造出的扩展转移函数记为 艿，它接受状态p 和串w z ，返回状态g ，q 是当自动机从p 开始处理输入序列 w 时所到达的状态。通过对输入串的长度进行归纳定义艿如下： 8 ( p ，占) = p8 ( p ，们= 8 ( a ( p ，力，d ) 其中占为空字，w = x a ，a 是w 的结尾符号，x 是包含除结尾符号外w 的所有其它 符号的串。 4 ) 确定型有限自动机通常用两种记号来描述：状态转换矩阵和状态转换图。 例1 1 2 确定型有限自动机a = ( 0 ，l ，2 ，3 ，扣，万，0 ， 3 ) 其中占为：8 ( 0 ，口) = 1 , f r o ，6 ) = 2 文l ，口) = 38 ( 1 ，6 ) = 2 8 ( 2 ，a ) = l万( 2 ，6 ) = 3 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 6 ( 3 ，口) = 3万( 3 ，6 ) = 3 所对应的状态转换矩阵、状态转换图如图1 1 所示。 迫符 b 状态 a 012 l32 213 333 状态转换矩阵状态转换图 图1 。l 显然，上图所示确定型有限自动机为一完全d e 4 。 定义1 i 3 设a = ( q ，z ，占，q o ，f ) 是一台确定型有限自动机，w = q 口2 a n 是字母表上 的个字符串。如果存在q 中的状态序列珞，名，满足下述条件： ( 1 ) r o = q o ( 2 ) 万( ，q + 1 ) = + l ，f - o ，l ，胛一1 ( 3 ) f 则一接受字符串w 。 如果语言三= w i a 接受w ，则称自动机爿识别语言三。也即d _ 删a 的“语言” 是这个确定型有限自动机一接受的所有字符串的集合，记作( 椰。 定义1 1 4 令a = ( q ，占，g 。，) 为一台确定型有限自动机，则 ( 1 ) 如果存在w + 使得彦( 口o ，叻= q ，则称g q 是可达的； ( 2 ) 如果存在w z 使得舌( q ，w ) f ，则称q q 是余可达的。 显然对每一确定型有限自动机4 ，存在一确定型有限自动机曰，使得l ( b ) = l ( a ) ， 且曰的所有状态是可达的，同时口中至多有一状态是余不可达的。这个d f b 被称作一 简化的d 删。 一般情况下，在确定型有限自动机中，对任何状态和输入符号都有不超过一个转移，可 以给任何这样的自动机加上一个余不可达状态d 。然后，从每个状态q 出发，在g 没有转移 的某输入符号上，加上到状态d 的转移，结果可得到一个完全d f a 。因此。如果一个自动 机从任何状态出发在任何符号上至多有一个转移，而不是恰好有一个转移，这个自动机也是 d f a 。 例1 1 5 图1 2 中两个状态转换图均为表示语言l = f a b ) 的d f a 。 6 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 捌蔷g 冷 图1 2 在图1 2 中，左图为不完全、简化的d f a 。右图为完全、简化的d f a ，状态3 即为 余不可达状态d 。显然，余不可达状态3 的存在仅为保证映射的完整性。所以。去除余不可 达状态d 对于确定型有限自动机识别语言没有影响( 如左图) 定义1 1 6 确定型有限自动机a = ( g ，z ，以，吼，瓦) 为一最小d f a 是指，对任意使得 工= i ( b ) 的d f ab = 峨，瓦以，f b ) 刮级陶q 覃i ! 其中l q i 为集合q 中元素的个数，即自动机中状态的个数。 可见，最小确定型有限自动机没有多余状态并且它的状态中没有两个是互相等价的。 定义1 1 7 状态复杂度 1 1 通常状态复杂度指的是确定型有限自动机中的状态个数。一种正规语言的状态复杂度指 的是表示该语言的最小确定型有限自动机的状态复杂度。 1 1 2 确定型有限盖自动机( d f c a ) 基本概念 盖自动机( c o v e ra u t o m a t a ) 并非新概念。相似的概念在许多文献 1 0 ，1 3 - 1 6 ，2 4 ，2 9 中 由于不同的目的被研究。本文引入盖自动机的一些基本概念和性质是因为它是本文中新算法 的一些思想和新旧算法正确性证明的重要启示和来源。 非正式地，一个语言三的盖自动机爿是确定型有限自动机，它接受三中所有字 符串和其它可能比三中任何字符串更长的字串。 定义1 1 8 令，为语言三中最长字串的长度。一台如象工( 彳) f lz 9 = l 的d f a4 被称 作上的确定型有限盖自动机( d f c a ) 。 其中型= u 。，z 。为z 中长度为f 的所有字符串。可见，确定型有限盖自动机实质 上就是一台确定型有限自动机。 定义1 1 9 语言三的最小d f c a 令彳= ( q ，z ，艿，q o ，f ) 为语言三的一确定型有限盖自动机如果对每一三的d f c a b = ，艿，q o ，f ) ，有i q i 矧q i ，称彳为l 的- - t z b d f c a 例1 1 1 0 令字母表为z = 岛b ，c ，上= a b c ，a b a b c ，a b a b a b c 。显然，= 7 接受三 的最小d f a 如图1 3 所示，有8 个状态( 如果完全应为9 个) 图1 3 7 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 接受工的最小d f c a 如图1 4 所示，只有4 个状态( 如果完全应为5 个) 。 弋泸巧昀 图1 _ 4 经验 3 3 表明；对许多语言来说，构造d r m 比构造d _ f 更容易，表示同一有限语言 的最小d f c a 常常比精确表示该语言的最小d 以有着更少的状态和转移。 1 2 正则语言及运算 1 2 1 正则语言基本概念 定义i 2 1 如果一个语言被一台有限自动机识剐，则称它是正则语言。 定义1 2 2 包含有限数量字符串的形式语言称作有限语言。 有限语言是最简单的语言。所有有限语言都是正则语言。 正则语言除了可用有限自动机描述外，还可用正则表达式 2 7 ，3 2 j 描述。就描述能力而 言，正则表达式和有限自动机是等价的，它们都恰好能描述相同的语言：正则语言。 定义1 2 3 称胄是一个正则表达式，如果r 是 ( 1 ) 口，这里a 是字母表中的一个元素： ( 2 ) 占；( 空字) ( 3 ) 西；( 空集) ( 4 ) ( 矗lu r 2 ) ，这里r l 和r 2 是正则表达式； ( 5 ) ( 蜀。垦) ，这里蜀和马是正则表达式： ( 6 ) ( r 1 ) ，这里蜀是正则表达式。 其中u ( 并) 、o ( 连接、拼) 、 ( 星号、闭包) 为正则运算符，见定义1 2 5 。 定理1 2 4 每一个用正则表达式来定义的语言也可用有限自动机来定义。 1 2 2 正则运算及性质 定义1 2 5 正则运算符：并、交、连接( 拼) 、星号( 闭包) 设厶和三2 是两个语言，定义正则运算并、交、连接和星号如下： 并：厶u l 2 = 缸ix 厶或x l 2 ) 交：上ln 三2 = x jx l f i x l 2 连接：三l 。l 2 = x y i x l i 助三2 ) 星号：上：= x 1 x 2 。坼l k 2 1 且每一个而厶 定义1 2 6 运算的封闭性：如果把某种运算应用于一个对象集合的成员得到的对象仍在这 个集合中，则称这个对象集合在该运算下封闭。 出于本文的需要，我们只讨论正则语言类并、交运算的封闭性质。 s 贵，f l 大学计算机应用技术2 0 0 6 届硕士研究生论文 定理1 2 7 如果厶和三2 都是正则语言则厶u 厶也是。 定理1 2 8 如果三i 和岛都是正财语言，则三1 n 三2 也是。 1 3等价和相似关系 在有限语言所含字符串间存在着等价和相似关系。同样，在对应的自动机中，状态间也 存在着等价和相似关系。下面，介绍等价和相似关系的概念 2 8 以及这两种关系的性质 1 7 ，1 8 1 3 1 字符申间的等价和相似关系 定义1 3 1 令工为字母袭z 上的有限语言，x , y e 鬈，若对任意的z e f 。有 愆e 三营弦l 。则称x e y 。( x 和y 在工上是等价的) 关系；是自反、对称，传递的。 定义1 3 2 令三为字母表上的有限语言，z 为l 中最长字串的长度。令薯y z 。定 义如下关系； ( 1 ) x ，y ：当对所有z z ，使得i x - z 喀，i y z 喀，时，船l 营y z ； ( 2 ) x 。y ：当石。y 不成立 关系 v 。是自反、对称，但不传递的。 显然，在有限自动机a 上，若l = 三( 4 ) ，a ( q o ，功= a ( q o ，力= q ，则x s ly 且 x y 引理1 ，3 3 令上为有限语言，x ，y ，z z ，i x i 訇y 闰z l 。下面结论成立： ( 1 ) 若工y ，x z ，则) ，z 5 ( 2 ) 若x j ，y z ，则工z 5 ( 3 ) 若x 。y y * 。z ，则x * 。z 。 1 3 2 状态同盼等价和相似关系 定义l3 4 令a = ( q ，占，q o ，f ) 为一确定型有限自动机。若对任意字符串w ， 艿o ，叻f 8 ( q ，叻f ，则称p ；_ q ( 在a 中，状态p ，q 是等价的) 如果两个 状态不是等价的( 一) ，则说这两个状态是可区分的。 定义1 3 5 令彳= ( q ，艿，q o ，f ) 为一确定型有限自动机。对每一状态q q l 纠e l ( q ) = m i i l | w0 a ( q o ，w ) = 们， 即如w z ( g ) 为从初态到状态g 的最短字符串的长度。 定义1 3 6 令一= ( q ，艿，q o ，f ) 为有限语言三d f c a ，为l 中最长字串的长度令 9 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 p ，q q ，m = m a x l e v e l ( p ) ，l e v e l ( q ) 。若对任意w e 4 一，彦( p ，w ) e f 当且仅当 舌( g ，w ) ef ，则称p 一4q ( 在彳中，状态p ，g 是相似的) 。 显然，在d 黝a 中，若p i4q ，则有p 一q 。也即若p * _ q ，则有p - q 。 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 第二章确定型有限自动机( d f a ) 的最小化算法 一一填表算法 2 1 问题的产生 在许多识别有限语言的自动机例子中，常会考虑能否找到识别相同语言的更小自动机。 对d f a 来说，最小d f a 就是有着最少状态且能识别相同有限语言的d 以。 根据m y h i l l - n e r o d e 定理 7 ，在同构意义下接受一个正则语言的最小状态确定型有限 自动机是唯一的。也就是说，给定任何两个等价的最小状态d f ，总是能找到办法重新命 名状态，使得这两个d f 成为相同的。 d ，最小化算法的核心是把一个d 黝的状态分成一些不相交的子集，使得任何不同 两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。换句话说，一台最 小化的d f a ，它没有多余状态并且它的状态中没有两个互相等价。因此，一个有限自动机 可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。 下面介绍目前常用的一种d 尉最小化算法：填表算法 2 2 填表算法 2 2 1 算法描述 填表算法的思想是标识可区分状态对，即不等价状态对。首先标识状态对( p ，g ) ，p 和 口一个为终态，一个为非终态。这是因为在确定型有限自动机中，终态和非终态肯定是不等 价的。其次，对所有以终态结尾的字符串均能被自动机识别，所有以非终态结尾的字符串均 不能被自动机识别，以此进一步扩大可区分状态对。 填表算法由两个主要部分组成：第一步是判定状态间的等价关系；第二步是合并等价状 态。文献 3 4 2 3 页给出了填表算法的一个具体描述： 填表算法： 输入：d f aa = ( q ，艿，g o ，f ) 输出：表示同一有限语言三印) 的最小d f aa 。= ( q ，邑j ，玩，f ) 1 ；从4 中删除所有不可达状态。 2 ：考虑所有q 中无序状态对 p ，g ) ： p ，g ip ，q q ，p 办 3 ；标记所有对 p ，g ) ，p e f 且g 叠f ，或相反。 4 ：w h i l e 在前一步有新对被标记面 5 ： 力r 所有未被标记对 p ，g ) d b 6 ： f o r 所有a z d o 7 ： 矿 占( p ，口) ，6 ( q ，口) ) 已被标记t h e n 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 8 - 标记 p ，g ) 9 ： e n d f 1 0 ： e n d 如， 1 1 ： e n d 如r 1 2 ：e n dw h i l e 1 3 ：构造d f aa 。：合并等价状态。将未被标记的两个状态合并为一个状态，注意可 能不止两个状态合并为一个状态。如果 g ，p ) 、 p ，r ) 都未被标记，则所有这三个状态 合并为一个状态。这些标记表示状态间的等价关系。彳+ 中的状态表示么的等价状态集。 1 4 ：等价状态集问的转移函数可由等价状态集中任意状态问的转移而定。 1 5 ：得到d f a a = ( q ，占，q o ，f ) 即为上) 的最小d f a 。 2 2 2 算法正确性证明 在 3 4 中未给出该算法的正确性证明和计算复杂性分析。在本小节和下- - d , 节将逐一进 行这两项工作。 首先，在算法第1 行，去除所有不可达状态。由定义1 1 4 状态可达的定义，如果字符 串w l ( a ) ，则在自动机a 中识别w 的状态序列( r l = 吼，r f ) 必不经过不可达状 态。所以删除不可达状态对于自动机彳识别的语言是不影响的。 其次，算法第2 1 2 行，执行填表算法的第一步：判定状态间的等价关系。标记的对为 可区分状态对，即不等价状态对。由下述说明和定理可知其正确性。 说明： ( 1 ) 终态和非终态对 p ，g ) 肯定是不等价的。 因为在d f a a = ( q ，万，9 0 ，) 中，若p f ，q 萑f ，p ，q q 则由定义 1 3 4 状态间等价关系的定义，令w = 占z ，则j ( p 占) = p e f ， 8 ( q ，占) = q 芒f ，所以p 窖jg 。 ( 2 ) 若状态对 p ，q 的某一后继状态对 ，t ) 不等价，则状态对 o 时，定理成立叩对所有长度为 钧字符串w 能区分的狡卷对i 9 在算法中， 已被标记。 则当i w ，l + 1 时，对w 能区分的任一状态对 p ，订，有8 ( p ，叻和8 ( q ，1 j ) 恰有一个能被 自动机爿所接受。 设w = c i 口2 口。+ l z ，r = a ( p ，q ) ，t = a ( q ，口1 ) 。令w = 口2 口肿i ， 则彦( p ，w ) = 彦( 占( p ，q ) ，a ：4 。“) = 彦p ，w 。) ，文g ，w ) - - 彦( 占( 吼口，) ，口：。- c n + ) = 彦( f ，w ) 显然w 区分状态，和t 。 x w 。= 口2 羽m ，1w n ，由归纳假设，可区分状态对( ，t ) 已被标记。 当算法执行到5 - - 8 行，检测未被标记对 仍g ) ，q ，因为 r ， 已被标记，所以标记状 态对f p ，g ) 。 所以，当1 w l _ + 1 时，对w 能区分的任一状态对 p ，q ) 。在算法中必被标记。 定理得证。 由以上定理可见，当算法2 1 2 行运行完毕。未被标记的状态对即为两等价状态。 在算法第1 3 1 5 行，执行填表算法的第二步：合并等价状态，生成同一语言的最小确 定型有限自动机4 。同样，由下述说明、定义和定理可知其正确性。 说明： ( 3 ) 在上述算法中，若 叮，p ) 、 p ，) 都未被标记，则p 5 q = r 因为由定理2 2 1 ， g ，p ) 、 p ， 未被标记，有g ；p ，p s r 。 由等价关系的传递性质有g ；r 所以，这三个状态互为等价状态：p ；q = r 参照 2 4 “9 页状态集q 的相似状态集划分，定义状态集q 的等价状态集划分。 定义2 2 2 令自动机4 = ( g ，最蜘，d 为一确定型有限自动机， ( 蜴，q ，) 是状态集 q 的一划分，显然r 马qj ，如果以下条件成立： 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 ( 1 ) q u 奶u u q = q ( 2 ) q n q ，= 妒，对所有1 f ，s ，i ， ( 3 ) v 1 s i s ，v p ，q q f ，p 暑一牙 ( 4 ) v 1 f ，r ，f ，v p q ，v g q ，：p _ q 称( q l ，q ，) 为状态集q 的一等价状态集划分。 定理2 2 3 在上述算法第1 3 行，若将未被标记的状态对中的状态归入一状态集( 若 p ，g ) ， p ，) 都未被标记，则三个状态归入同一状态集) ，再将状态集q 中剩余的其它状态各自单 独视为一状态集，则得到q 的一等价状态集划分。 证明：需证明得到的划分满足定义2 2 2 中等价状态集的4 个性质。假设得到的状态集依次 为q l ，q ，。 由上述状态归类方法，显然性质( 1 ) 、性质( 3 ) 成立。 q luq 2u u q ，= o 。 v 1 i ，y p ，q q ，p 量g ( 由说r y j ( 3 ) ) 下面证明性质( 2 ) 和性质( 4 ) 成立。 由定理2 2 1 ，所有不等价状态对均被标记，所以若 p ，g 未被标记，表明p 和q 等价。 而由算法第1 3 行，任一状态p q ，只可能为以下两种情况之一： 1 ) 若存在包含p 的未被标记的状态对，则p 属于包含p 和p 的等价状态所在的状态集q j ； 假设q f = p ”，p t ) ，则显然p 。z p ，对v 1 i , j k ，i ，且对即q f ，在 未被标识的状态对中至少有一对含有状态p j ( 否则p 应单独视作一状态集，矛盾) 。 又对即q ，v g q ，1 f ，i _ ，有p 霉q 否则( p ，q ) 应不被标记，p 和口应归于同一的状态集，而f _ ，矛盾。 2 ) 若不存在包含p 的未被标记的状态对，则p 单独视作一状态集， 因为包含p 的任意状态对均被标记，则有对v q q 一 p ，p 鲁g 。 由1 ) 、2 ) ，任一状态p q 只可能在某一状态集中，即不可能p q l 且p q ，i ， 所以，性质( 2 ) 、( 4 ) 也成立。由算法第1 3 行得到的划分为q 的一等价状态集划分。 证毕。 由此，将得到的等价状态集划分( q l ，q ，) 的每一状态集视作劂a 。中一状态，则 得到r 个状态g ：，g ：一l ( 1 q 卜，) ，并由定理2 2 3 可知，g ：辜q j ，对任意 0 s f ，j s ，一1 ，i _ ，。 1 4 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 下面，证明算法第1 4 行转移函数构造的正确性。 定理2 。2 。4 对上述算法得到的等价状态集划分( q l ，q ) 中任一状态集q ( 1 i ，) ，任 一输入字符口z ，则一定存在一个状态集q j 0 s j ，) ，使得对任意p q ，有 6 ，口) q ，。 证明： 反证】 若存在两状态p ，q eq l ， 使得艿 ，口) 岛，6 ( g ，口) e 级，l s f ，七sr , y k 则根据定义2 2 2 等价状态集划分的性质4 ) ，有8 ( p ，口) _ 艿国，力 再由说明( 2 ) ，p g q 然而p ，q q l ，等价状态集划分的性质3 ) ，p ；q 。矛盾 所以，假设不成立。定理得证。 因此，如果等价状态集中一个状态是终态，则这个等价状态集中所有状态一定都是终态。 原因是任何终态和任何非终态都是可区分的，所以不能让终态和非终态同属于一个等价状态 集。 由上可知，d f aa 的初始状态g ：所对应的等价状态集应含有d f a 中初始状态 q 。，d f aa 的终态所对应的等价状态集应为包含d f aa 中终态的等价状态集。 最后，证明得到的d f aa 。为表示同一语言的最小d f a 。先引入一个定义。 定义2 2 5 x , l 所：f f i f ，令字符串v ，z ，使得i v ， = l e v e l 4 ( q a g $ ( g j ，q ) = q 。 即字符串h 为a e g ) a 初态q ：到达等价状态集q j 所对应状态的一个最短字符串。 定理2 2 6 由上述算法得到的d f aa 为识别语言三( 彳) 的最小d f a 。 证明； 反证 若存在识别三( 彳) 的另一更小d f aa = ( q ，墨艿，玩，f ) ，使得j q h q j - ，。 则根据定义2 2 5 ，由鸽巢原理，存在1 i _ ，使得 皂二 一 一 艿( 玩，v t ) = 占( o ，) ，即两字符串h ，一在爿上落在同一状态上 由等价状态集划分的性质，可选择p q ，q q ，有p 。q 也即，存在某一字符串w ，使得彦( p ，叻f 营g ( q ，叻叠f 。 所以，在4 中。彦( g ：，v ，们= 彦( p ，们f 铮彦( q o ，_ 叻= 彦( g ，_ 1 ，) 萑f ， 即v t w l ( a ) 铮 e i w 萑三( 4 ) 。 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 而在d 删二i 中，两字符串v 。，v ，落在同一状态上，即对任意的w ， 皂皂皂皂品 有艿( 玩，v 。们= 占( 6 ( 0 ，v 。) ，w ) = 艿( 艿( 玩，) ，w ) = 万( 玩，”j w ) ， 也即u w 三( 4 ) 铮v ，w e ( 爿) 。矛盾。 所以，假设不成立。 定理得证。 2 2 3 时空复杂性分析 分析以上算法，第1 行为预处理工作：去除不可达状态：第2 一1 2 行为判定给定确定型 有限自动机状态间的等价关系；第1 3 1 4 行为合并等价状态并构造最小确定型有限自动机。 假设给定确定型有限自动机去除不可达状态后的状态数为珂，显然预处理工作仅需状态 数的常数时间和空间，可略去不计。下面重点分析第2 一1 4 行的时间和空间复杂性。 2 2 3 1 时间复杂性 在算法第2 1 2 行判定两个状态是否等价并标记不等价状态对( 可区分对) 。首先第3 行作初始标记( 标记所有终态和非终态对) ，需标记k 一七) 对，其中0 k 玎一l 为非 终态状态数。可见最少需标记0 对( 全为终态，k = 0 ) ，最多需标记1 一n 2 l 对，所以需d ( 2 ) l4j 时间；而4 1 2 行的w h i l e 循环，总共需判断的状态对为c ：丛! ；掣对，在一轮中，考虑 所有未被标记状态对，看看是否已经发现其后继对中有一对是不等价的( 已标记) ，所以一 轮不超过o ( n 2 ) 时间。而且，如果在某轮中没有加入新的标记，则算法结束。因此，o ( n 4 ) 肯定为该循环的运行时间上界。 但是，更仔细的算法能在o ( n 2 ) 时间里填好表。这一思想 3 1 0 8 是对于每对状态 ，j ) ， 初始化“依赖”p ，s ) 的这些 p ，办对的表。也就是说，如果发现p ，j 是可区分的，则 p ，q 是可区分的。在开始是通过下面的方式建立表：检查每对状态 p ，西，对于固定多个输入符 号中的每个a ，把 p ，g 写在状态对 占( p ，口) ，万( g ，口) 的表上，这些是p 和g 在口上的后继 状态。 如果最终发现 ，s 是可区分的，则往下考虑 ，s 的表。对于这个表中还不是可区分 的每个对，都让这个对是可区分的，并把这个对放到必须同样检查的对队列中。 这个算法的总工作量与表的长度之和成比例，因为在每一次里，要么加入一些东西到表 中( 初始化) ，要么第一次和最后一次检查表的成员( 当往下考虑已经发现可区分的对的表 时) 。由于认为输入字母表规模是常数，所以每个状态对都写在0 ( 1 ) 个表中。存在o ( n 2 ) 个 状态，所以工作量是o ( n 2 ) 。 在算法1 3 1 4 行，合并等价状态和生成转移函数。合并等价状态实际上是生成等价状 1 6 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 态集划分。即判断每一状态的归属，需。伪) 时间。生成转移函数为对每个输入字符口，等 价状态集的箭弧指向，需o ( i f 功时闯。由于 z f 是一个常数，所以时间复杂度为联彩 因此，整个算法时间复杂度为o ( n 2 ) 2 2 3 2 空间复杂性 由上面的分析可知，所需的主要空闯有：( 1 ) 、存储确定型有限自动机：嚣个状态，j 1 个输入字符，玎x i 1 个转移；( 2 ) 、存储! ：尘个状态对标记，l i 1 个依赖关系。所以， z 该算法的空闯复杂度也为a l ，1 2 l h 贵州大学计算机应用技术2 0 0 6 届硕士研究生论文 第三章确定型有限自动机( d f a ) 改进的填表算法 3 1 问题的产生 填表算法的实质是尽最大努力求出可区分状态对。它是通过递归地发现并标记d f a a = ( q ，万，吼，f ) 中的可区分对来实现的。 基础：如果p 是接受状态而q 是非接受状态，则状态对 p ，q 是可区分的，在表中作上 标记。 归纳：设p 和g 是满足下列条件的状态：使得对于某个输入符号a ，r = 8 ( p ，和 t = j 国，口) 是已知可区分状态对( 已标记) ，则 p ，g ，是可区分状态对，在表中作上标记。 然而，