（基础数学专业论文）一类非确定型有穷自动机的极小化及时间复杂性.pdf

摘要 本文对自动机理论的研究主要是两个方面：自动机的极小化和极小化的时间 复杂性。 在自动机的状态集合上定义等价关系，引入等价类，将等价的状态合并成一 个状态，生成新的状态数较小的自动机。新生成的自动机与原自动机识别的语言 不变，也就是说它们是等价的。这就是树图分割法的思想。利用树图分割法可以 进行确定型有穷自动机的极小化。 本文的重点内容是构造了一类非确定型有穷自动机，即连接型有穷自动机。 这类有穷自动机是由两台确定型有穷自动机连接而成的。利用两台确定型有穷自 动机状态集合上的等价关系可以构造出连接型有穷自动机状态集合上的等价关 系。这类非确定型有穷自动机也可以利用树图分割法来极小化。还可以得到连接 后再极小化的自动机的状态数不大于极小化后再连接的自动机的状态数。 非确定型有穷自动机的情况比较复杂。往往比较大的有穷自动机没有等价状 态，但将其中某两个或者几个状态进行合并并不改变它们的语言。本文给出了非 确定型有穷自动机状态合并的条件。找到了非确定型有穷自动机极小化状态的临 界条件。 自动机极小化的时间复杂性，有效的验证了极小化算法是否有效。一般地， 多项式时间内能完成的就认为该算法是有效的。确定型有穷自动机和连接型有穷 自动机利用树图分割法进行极小化，它们都在状态的三次方时间内就可以完成。 本文的最后给出了非确定型有穷自动机极小化算法。 关键词：连接型有穷自动机等价关系不可区分状态 时间复杂性树图分割法临界条件 中图分类号：t p 3 0 1 1 3 文献标识码：h a b s t r a c t t h er e s e a r c ho ft h ea u t o m a t i o nt h e o r ym a i n l yi n c l u d e st w oa s p e c t s ：o n ei s m i n i m i z a t i o no fa u t o m a t o na n dt h eo t h e ri si t st i m ec o m p l e x i t y e q u i v a l e n tr e l a t i o n s a r ed e f i n i t e di nt h es e to ft h ea u t o m a t i o n ss t a t e sa n d e q u i v a l e n tc l a s s e sw i l lb ei n t r o d u c t e d t h e nt h ee q u i v a l e n ts t a t e sw i l lb em e r g e di n t o o n es t a t e ，s ot h en e wg e n e r a t i o no fa u t o m a t i o nw i l lb es m a l l e r t h el a n g u a g et h a tt h e n e wg e n e r a t i o no fa u t o m a t i o na c c e p t si st h es a m ea st h el a n g u a g et h a tt h eo r i g i n a l a u t o m a t o na c c e p t s t h a ti st os a y ，t h e ya r ee q u i v a l e n t t h i si st h et r e es e g r e g a t e d m e t h o d t r e es e g r e g a t e dm e t h o dc a nb eu s e dt om i n i m i z ed e t e r m i n i s t i ct - m i t e a u t o m a t i o n ( d f a ) ak i n do fn o n d e t e r m i n i s t i cf i n i t ea u t o m a t i o n ( n f a ) i st h ef o c u so ft h i sp a p e r t h a ti sc o n n e c t i n gn f a s u c hn f ai sd e t e r m i n e db yt h et w o - d f a u s i n ge q u i v a l e n t r e l a t i o n so ft w o d f a ss t a t ec a nc o n s t r u c te q u i v a l e n tr e l a t i o no fc o n n e c t i n gn f a s t h es t a t e s u c hn f ac a l la l s ou s et r e es e g r e g a t e dm e t h o dt om i n i m i z e c o n c l u s i o n s c a nb eg o tt h a tt h en u m b e ro ft h em i n i m i z i n gc o n n e c t i n ga u t o m a t i o n ss t a t e si sn o t m o r et h a nt h en u m b e ro ft h e c o n n e c t i n gm i n i m i z i n ga u t o m a t i o n ss t a t e s n f ai sm o r ec o m p l i c a t e d ab i gn f ai so f t e nn oe q u i v a l e n ts t a t e s ，b u tm e r g i n g t w oo rs e v e r a ls t a t e sd o n tc h a n g ei t sl a n g u a g e i nt h i sp a p e rc o n d i t i o no fm e r g i n g s t a t e si sg i v e na n dt h en u m b e ro fm i n i m u ma u t o m a t i o n ss t a t e si sf o u n d t h et i m ec o m p l e x i t yo fm i n i m i z i n ga u t o m a t i o ni sv e r ye f f e c t i v et ot e s ta l g o r i t h m i ng e n e r a l ，t h ea l g o r i t h mw h i c hc a nb ec o m p l e t e di np o l y n o m i a lt i m ei se f f e c t i v e u s i n go ft r e es e g r e g a t e dm e t h o d , d f aa n dc o n n e c t i n gn f a c a nb em i n i m i z e di n c u b i ct i m e f i n a l l yt h ea l g o r i t h mo fm i n i m i z i n gn f ai sp r e s e n t e di nt h i sp a p e r k e yw o r d s ：c o n n e c t i n gn f a e q u i v a l e n tr e l a t i o n u n d i s t i n g u i s h e ds t a t e t i m ec o m p l e x i t y t r e es e g r e g a t e dm e t h o d c r i t i c a lc o n d i t i o n 4 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究在做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律责任由本人承担。 论文作者签名： 奎秘 日 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权贵州大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：獬导师签名： 日期：21 q 垃旦 第一章前言 1 1 研究背景 自动机理论是研究抽象计算的装置或“机器 。在2 0 世纪3 0 年代计算机出 现之前，图灵研究过一种抽象机器，这种机器具备了今天计算机的所有能力。图 灵的目是精确地描述一条界线，这条界线区分计算机能做什么和不能做什么。图 灵的结论不仅适用于抽象的图灵机，也适用于今天的真实计算机( 2 5 j o l m e h o p c r o f l ，e t c 2 0 0 4 ) 。 在2 0 世纪4 0 和5 0 年代，一些科学家开始研究有穷自动机，有穷自动机理 论是h u f f m a n 、m o o r e 等人开创的。它给出了一类计算模型，这种模型在计算机 科学的若干应用领域都有着重要的作用( 3 0 m i c h a e ls i p s e r , 2 0 0 0 ) 。有穷自动机 理论的发展对今天计算机科学的影响是深远的，经过几十年的发展，自动机理论 已成为计算机科学中的一个重要分支，并应用于计算机科学的许多领域，如编译 程序构造、文本处理、结构型数据翻译以及开关线路设计等，它是计算机软件、 硬件研究的重要基础理论( 1 9 c c a m p e a n u ，e t c 2 0 0 1 ) 。 正规式理论是由k l 爸爸n e 于1 9 5 6 年提出的，正则表达式与有穷自动机是根本 不同的，但它们表示完全相同的语言正则语言。正则表达式的最重要之处是 在有穷自动机中的应用( 3 0 m i c h a e ls i p s e r , 2 0 0 0 ) 。由于从正则表达式得到的 d f a 的大小呈指数形式且最小的n f a 是很难得到的。因此，是否考虑用其它的 一些方法来寻求最小的自动机。这种观点得到的自动机不一定是最小的，但可以 “适度”的小而且可以在很高的效率下被构造。研究自动机的专家完成了从正则 表达式构造典型的带空转移的( 一n f a ) 的算法，而且得到的n f a 的大小呈线 形( 2 6 k t h o m p s o n ，1 9 6 8 ) ，s i p p u 与s o i s a l o n s o i n i n e n 还改进了t h o m p s o n 的算 法使得构造的e n f a 更小。但是，不带s 转移的n f a 的情形是比较困难的。鉴 于这种情况，由另外一些专家 r m c n a u g h t o n 。y a m a d a ( 3 2 r m c n a u g h t o n ，h y a m a d a ，1 9 6 0 ) 与v m g l u s h k o v ( 3 6 v m g l u s h k o v , 1 9 6 1 ) 寻找 到了一个好的用来构造较小的n f a 的算法，是“位置自动机 ，v a n t i m i r o v ( 3 5 v a n t i m i r o v , 1 9 9 6 ) 在位置自动机的基础上又寻找了一个较好的算法，是“基于偏 导的自动机，l i l i e ( 2 9 l i l i e ，s y u ，2 0 0 3 ) 也在位置自动机基础上有寻找了一个 更好的算法，是“序自动机”，后者所得到的自动机是很小的。 5 1 2 研究的主要内容及意义 随着计算机控制技术的广泛应用，软件设计越来越复杂，要求越来越高，其 实时性、并发性、交互性以及友好性等都难以用顺序的静态的程序来描述和实现。 有穷自动机在软件设计中的应用，为设计者提供了一种新的解决问题的思想和方 法。一个有穷自动机等价于一个状态转换图。这样得到的状态转换图可以用有穷 自动机的有关理论和算法进行等价变换、约简，然后用程序实现。由于状态转换 图与程序有一定的对应关系，所以使得程序比较规范化，从而高效的完成了软件 设计工作，因此有穷自动机的化简成为重要的研究课题。 本文对于有穷自动机的研究，主要基于两个方面：一是对有穷自动机的极小 化；二是极小化的时间复杂性。 在等价的前提下，自动机的状态越少，意味着越节省软件和硬件资源。有穷 自动机的极小化是指将自动机的状态集划分成一些不相交的子集，使得任何两个 不同的子集中的状态都是可区分的，而同一子集中的任何两个状态都是等价的。 本文引入树图分割法，搜索所有不可区分到的状态，将不可区分的状态对进行合 并，就实现了自动机的极小化。 本文还找到了非确定有穷自动机状态合并的条件以及极小化的状态临界条 件。最后给出了一般非确定型有穷自动机极小化算法。 1 3 本文的结构安排及主要工作 本文共分为五章，总共十个部分，结构如下： 第一章：前言。主要介绍了本论文的研究背景及研究意义； 第二章：有穷自动机基本理论。主要介绍自动机的基本定义、定理； 第三章：确定型有穷自动机的极小化； 第四章：连接型有穷自动机的极小化； 第五章：非确定型有穷自动机的极小化； 另外，本文还包括全文总结及进一步的工作、致谢、参考文献、附录以及原创性 声明五个部分。 6 第二章有穷自动机基本理论 2 1 引言 有穷自动机理论是描述词法规则的基本理论。在实际应用中，有穷自动机是 关于存储极其有限的计算机的很好的模型，它有一组状态及其控制，响应外部“输 入 ，“控制 从状态移动到状态。各类有穷自动机之间的关键区别之一，在于 控制究竟是“确定的 还是“非确定的”，前者意味着在任何时刻自动机不能处 在一种以上状态中，后者意味着能同时处在几种状态中。我们知道，增加非确定 性并不能定义出任何不能用确定型有穷自动机来定义的语言，但是用非确定型有 穷自动机来描述应用却具有很高的效率。事实上，非确定性允许用较高层语言来 “设计问题的解( 2 8 l i l i e ，s y u ，2 0 0 2 ) 。通常我们可以通过算法将非确定型有 穷自动机转化为确定型有穷自动机，然后在常规计算上“执行 。 2 2 确定型有穷自动机基本概念 定义2 1 确定型有穷自动机d f a 是一个五元组m 一( q ，6 ，q o ，f ) ，其中： ( 1 ) q 是一个有穷集合，叫做状态集。 ( 2 )是一个有穷集合，叫做字母表。 ( 3 ) 6 ：q z 呻q 是转移函数。 ( 4 ) q o q 是起始状态。 ( 5 ) f q 是接受状态集。 通常，我们对字符a 和字符串，我们可以写作 ( q i ，a g o ) 一( 6 ，口) ，) ，这里的符号一指一步变迁。m 接受一个在上的字符 串，可以表示为：对于某个厂f ，( 留。，) _ ( 厂，允) 这里九表示空串，呻+ 表示 有限次变迁。 定义2 2 ( 转移函数的扩展) 设m ；( q ，6 ，q o ，f ) 一台确定型有穷自动机， 定义6 如下： ( 1 ) 6 + 国，a ) = q( 状态g 下不读任何输入，就还处在g 中) ( 2 ) 假设一x r ，也就是说，a 是0 3 的结尾符号，x 是包含除结尾符号外的 7 所有符号串，6 国，) = 6 ( 6 ( 鸟，x ) ，a ) 。 此定义的思想是，为了计算6 国，) ，首先计算6 固，z ) ，6 + ( g ，z ) 计算完后所处 的状态是自动机在处理的结尾符号外的所有符号之后所处的状态。假设这个状 态是p ，也就是说，6 。( g ，x ) = p ，那么6 0 ，) 就是从状态p 再输k a ( 的 结尾符号) 上转移所得到的状态，即有6 ( g ，c o ) = 6 0 ，a ) 。 定义2 3 ( d f a 接受的语言)设mt ( q ，z ，6 ，g o ，) 是台确定型有穷自 动机，m 所接受的语言记为l ( m ) ，定义为：l ( m ) 一伽i6 。，) ，】- 也就是 说，语言l ( m ) 是让初始状态吼通向接受状态之一的串的集合( 2 5 j o h n e h o p c r o f t ，e t c 2 0 0 4 ) 。 一台机器可能接受若干字符串，但是它永远只能识别一个语言。若一个语 言被一台确定型有穷自动机识别，则称这个语言为正则语言。 例2 4 图2 1有穷自动机旭 = 【c ol 至少含有一个1 或者在最后的l 后面有偶数个o 】- l ( m 。) = l ，即称m 。识别l 或者m 。接受l 。若机器不接受任何字符串，那么它仍 然识别一个语言，即空语言。 定义2 5 ( 状态轨迹) 设m ；( q ，6 ，q o ，) 为一台确定型有穷自动机( d f a ) ， 由6 定义函数6 ：q 宰呻q 如下： 6 t ( g ，) 一q ，6 ( q ，a x ) 一6 ( 6 ( g ，口) ，x ) 其中三是指上的有穷符号串构成的集合，称串x 将状态留带到状态6 ( g ，z ) 。对 于x a l a 2 口3 a 。称状态序列口o ，q 1 ，日2 吼为串z 将留。带到状态6 + ( ，z ) 的 状态轨迹，其中4t6 ( 鼋o ，a l a 2 口3 a 。) 1s is ，l 记：q 国，石) = _ 【吼，9 1 ，留2 吼 。 定义2 6 设m 一( a ，6 ，q o ，f ) 为一台确定型有穷自动机，在q 上引入二元 关系r ：v p ，q e a ， r 营( 觇) ( 6 0 ，x ) f 营6 ( g ，z ) ，) 。容易验 证：尺满足自反性，对称性和传递性，所以尺是q 上的一个等价关系。对于 8 m 坳，g q ， r ，称状态p ，q 不可区分的，即表示p ，鼋等价。若j + ， 使6 + 0 ，) 与6 ，c o ) 中的一个到达接受状态的而另一个到达非接受状态，称状 态p ，q 可区分，& 为区分p ，q 的证据。 两个状态s 和r 等价的条件是( 1 3 韩光辉，1 9 9 8 ； 1 4 韩光辉2 0 0 5 ) ： ( 1 )一致性条件：状态s 和r 必须同时为可接受状态或不可接受状态。 ( 2 ) 蔓延条件：对于所有输入符号状态s 和r 必须转换到等价的状态里。 也就是说，两个状态若相等应满足：在同样输入的作用下都有相同的输出；在同 样的输入条件下其相应的次态应彼此等价。这可能存在三种情况：对应次态相同； 其次态就是两个现态本身；其次态是彼此等价的。 定理2 7 设m = ( q ，6 ，q 。，f ) 是一台确定型有穷自动机，在状态q 上，若p ，口 是等价的，q ，r 是等价的，则状态p ，是等价。 证明：设q 上的等价关系为尺， ( p ，口) 尺辛( v x x + ) ( 6 p ，z ) f 营6 ( 日，x ) e f ) ( 口，r ) r 号( v x x ) ( 6 ( g ，z ) ，尊6 ( r ，x ) f ) 则有：( p ，) 尺净( v x x ) ( 6 ( p ，z ) f 营6 r ，x ) ，) 所以p ，是等价的。 定义2 8 ( 等价类自动机) 设m 一( q ，6 ，q o ，f ) 为一台确定型有穷自动机 ( d f a ) ，借助等价关系只，取等价类【p 】i 佃q ： 耐，我们可以构造 一台m 的等价类自动机【m 】，【m 】一( q ，6 + ，q 。，) 其中： q = 瞳】1 日q ) ； ：字母表保持不变； 6 ：0 x x 啼q 并且( 1 ) 6 ( 口，) 一q ； ( 2 ) 6 ( 鼋，踟) = 6 固，山) ，口) 。6 ( q ，a ) ，其中6 ( 鼋，) 一q ； q o 一【q 。】初始状态； f - k 】i g ，) 接受状态； 定义2 9 ( 极小化自动机定义) 设m - ( q ，6 ，q o ，f ) 为一台确定型有穷自动 机( d f a ) ，( m ) = b 。称m 为接受语言b 的极小化自动机，如果接受召的任 何自动机的状态数不低于l q i 。 9 2 3 非确定型有穷自动机基本概念 定义2 1 0 非确定型有穷自动机是一个五元组一( q ，6 ，q o ，f ) ，其中， ( 1 ) q 是一个有穷集合，叫做状态集； ( 2 ) 是一个有穷集合，叫做字母表； ( 3 ) 6 ：q x x 。_ q 是转移函数( 这里。- u e ) ； ( 4 ) q 。q 是起始状态； ( 5 ) f q 是接受状态集。 非确定型有穷自动机的转移函数6 是一个以q 中一个状态和中一个输 入符号作为变量并且返回q 的一个子集的函数。n f a 与d f a 之间的唯一区别在 于6 的返回值的类型：在n f a 的情况下，返回值是一个状态集合，而在d f a 的 情况下返回值是单个状态( 1 8 c c a m p e a n u ，e t c 2 0 0 5 ) 。 定义2 1 1 ( 转移函数的扩展) 设n = ( q ，6 ，q 。，f ) 一台非确定型有穷自动机， n f a 的转移函数6 的扩展函数6 定义如下： 7 ( 1 ) 6 + ( g ，g ) l 幻)( 状态目下不读输入，就还处在状态g 中) ( 2 ) 假设一x a ，也就是说，a 是缈的结尾符号，x 是包含除结尾符 k 号外的所有符号串，若6 ，x ) = 仞t ，p ：既卜柚u 6 ( p t ，口) = “，r 2 ，k ) 那 么6 。( 口，) = “，吃，k 。此定义的思想的实质是首先计算6 + ( q ，z ) ，然后遵 循从这些状态中任何一个状态出发的带a 的标记的任何转移。 对于非确定型有穷自动机，在读的各个字符时，有可能形成对下一个的选 择序列，并从初始状态到达任何接受状态。用的输入符号的其它选择、导致非 接受状态或者根本不会导致任何状态( 即状态序列“死亡刀) ，这样的事实不妨碍 n f a 在总体上接受( 1 1 秦永彬，许道云，2 0 0 6 ) 。 定义2 12 ( 非确定型有穷自动机状态等价) 设n 一( q ，6 ，q 。，f ) 是一台非 确定型有穷自动机，在q 上引入等价关系r ：若p ，q e q 且v ，有 1 0 6 q ，) nf 乒g 6 + ( g ，) nf 乒f 2 j ，贝0 称 尺。 定义2 1 3 ( 等价类有穷自动机) 设n 一( q ，6 ，q o ，f ) 是一台非确定型有穷 自动机，由状态集q 上的等价关系尺所确定的等价类【p 】- 幻q ： 尉， 则的极小化自动机可表示为： 。 n 孤i 。一( 【p 】：p e q ，6 。i n ，【q 。】， 【p 】：p f ) ) ( 其中6 。证( 【p 】，a ) 16 0 ，a ) 2 4 带转移的非确定型有穷自动机基本概念 现在介绍有穷自动机的另一种扩展。新“特征 允许在空串上的转移。实 际上，允许n f a 没有收到输入符号就自动转移，这类自动机与非确定型有穷自 动机是一样的，并不扩大有穷自动机接受的语言类，但是在程序设计中发挥了很 大的便利。 带转移的非确定型有穷自动机的形式化表示与非确定型有穷自动机的形 式化表示类似，只是有一点例外的，即转移函数必须含有在占上转移的信息。形 式化地，把一j 跗表示成札t ( q ，6 。，q o ，f ) ，其中，除6 。外，其它所有的组 成部分都有与n f a 同样的解释，而6 。是有下列变量的函数： ( 1 ) 首先具有状态集q 中的一个状态； ( 2 ) 其次具有集合u 】中的一个元素，也就是说，要么是输入符号，要么 是符号，并且要求f 不是字母表中的符号； 闭包顺着所有状态g 出发带标记的来转移到达其它状态，然后再顺着这些状 态发出的转移，依此类推，最终求出顺着箭弧都带f 标记的任何路径从g 可达 的每个状态，称为状态g 的闭包，记为：e c l o s e ( q ) 。 例2 1 4如图是一n f a 状态图的一部分。 图2 2 一n f a 的部分状态图 1 1 从状态1 出发，顺着只带标记的路径有1 呻2 一3 6 ，1 _ 4 。因此 e c l o s e ( 1 ) 一仉2 ，3 ，4 ，6 。 定义2 1 5 ( s n f a 转移函数6 的扩展) 设e 一朋啊n 一( q ，6 ，q o ，f ) 转 移函数6 的扩展函数6 。定义如下： 基础：6 ( g ，) i e c l o s e ( q ) 也就是说，如果这条路径的标记是，则只能顺着 从状态口出发带占标记的箭弧，这恰好是e c l o s e 所做的。 归纳：设形如x a ，其中a 是的结尾符号。注意a ，a 是不能为，甓。 计算6 ( g ，) 如下： 1 设6 ( 口，x ) 为 岛，p ：，p 。) 。也就是说，这些只是顺着标记为x 的路径可达 的所有状态。这条路径可能以一个或者多个带f 标记的转移来结尾，也可能 有其它的f 转移。 2 设u 乞。6 ( p i ，a ) 为饥，r 2 ，k ) 也就是说，顺着带x 标记的路径从q 到达一些 状态，遵循所有带a 标记的从这些状态发出的转移，这些是顺着带甜标记的 路径从口可达的一些状态，顺着下面的步骤( 3 ) 中的标记的箭弧，从这些 求出其它可达的状态。 3 6 国，) iu 7 ，e c l o s e ( 5 ) 。 定义2 16 ( 一m 啊所接受的语言) 设i ( q ，6 ，q o ，f ) 是一台一n f a ，则 一n f an 所接受的语言记为l ( n ) ：l ( ) i 和i6 ( 鸟。，) n f a ) 。 2 5 连接型有穷自动机基本概念 定义2 1 7 m ，i l a ( q l ，6 ，q o ，e ) ，m ：i ( q 2 ，6 ：，q 。，e ) 是两台确定型有穷 自动机，它们的连接型有穷自动机：n - m ，。m ：i ( 0 1u q 2 ，6 ，q 。，丘u e ) 是 一台非确定型有穷自动机。本文取q 1nq ：一彩进行讨论。其中6 定义为： 1 2 6 0 ，t o ) = 6 ，p ，) 若pe q , f 1 6 ，0 ，) 都互，一f 且贸0 ，缈) 茁f 6 ，0 ，c o ) u q o ) 着p 互且( 一或6 7 ( p ，t o ) f ) p ：p ，) ) 若p e q ： 定义2 1 8 设- m 。m ：i i ( quq 2 ，6 ，q 。，互u f ：) 是一台连接型的有穷自 动机，所接受的语言记为l ( ) ，定义为：l o v ) - 枷l6 ( ，) n ( 互u f ：) - 囝) 。 也就是说，语言l ( n ) 是让初始状态q o 通：q 接受状态之一的串的集合。 ， 定义2 19 ( 连接关系) ( 1 0 j 徐江，2 0 0 5 ； 1 2 宿云，2 0 0 5 )连接关系是将 两个关系进行笛卡尔积再从笛卡尔积中选择满足一定条件的记录的运算。设选择 条件为f ( 可以为一个一般的条件表达式) ，则连接关系可记为： r o o ，s = piri ( t l ，t 2 ) n ( 瓴尺) n ( 乞e s ) ) f lf o ) ) 。 定义2 2 0 ( 墨，恐) 设m ，i l m ( q l ，岛。q o ，互) ，m 2 ；( q ：，6 ：，留o ，e ) 是两台 确定型有穷自动机，r 和恐分别是q 1 和q 2 上的等价关系，称 r o 。，r 2 ， 若满足p q 1 ，q e q 2 ，且v ，按照定义2 1 1 中所定义的转移函数6 ，有 6 0 ，) n e 一乃寺争6 ( g ，) f - ) e g 。 2 6 确定型有穷自动机与非确定型有穷自动机的等价性 对于许多语言来说，构造n f a 比构造更容易，出入意料的是，每一介用某 个n f a 描述的语言也能用某个d f a 来描述。也就是说n f a 好象并不比d f a 识别 的语言多。实际上，确定型有穷自动机和非确定型有穷自动机识别相同的语言类。 但是，对于给定的某个语言，描述识别这个语言的n f a 有时比描述识别这个语 言的d f a 更容易得多。 如果两台机器识别相同的语言，则称它们是等价的。 定理2 2 1 每台非确定型有穷自动机都有一台确定型有穷自动机与之等价。 设一个语言被一台n f a 识别，必须证明存在一台d f a 也识别这个语言。基 本想法是把n f a 转换成模拟它的d f a 。 证明：设nt ( q ，6 ，q o ，f ) 是识别语言l 的n f a ，要构造一台d f am 来识 别。在给出完整的构造之前，先考虑比较容易的情况，假设没有s 箭头。以 1 3 后再把箭头考虑进来。 下面来构造m 一( a ，6 ，口o ，) 1 ) a - p ( q ) m 的每一个状态是的一个状态子集。p ( q ) 是q 的所有子集 组成的集合； 2 ) 对于r e q 。和口，令6 似，a ) ；幻q i 存在，r ，使得q 5 ( r ，口) 。如 果r 是m 的一个状态，则它是的一个状态子集。当m 在状态尺读符号a 时， 6 ( 尺，a ) 给出a 把尺中的状态带到什么地方。由于每一个状态可以转移到一个状 态子集，所以取所有这些子集的并a 记为：6 ( 尺，口) ；u 6 ( ，口) ； 3 ) q o 。 吼】，m 开始时所在的状态对应于只含n 的起始状态的集合； 4 ) f t 怛e a lr 包含的一个接受状态) ； 如果当时的可能状态中有一个接受状态，则机器m 接受。 现在来考虑f 箭头，为此再引入一个记号。对于m 的任意一个状态r ，根 据闭包的定义e c l o s e ( r ) = 臼l 从r 出发沿着0 个或多个占箭头可以到达g 】然 后，我们修改m 的转移函数，使得在每一步之后，在沿着箭头可以达到的所 有状态也包含在里面，用e c l o s e ( 5 ( r ，口) ) 代替6 ( ，a ) 能产生这个效果于是 6 ( r ，a ) 一幻e a i 存在r e r ，使得q e e c l o s e ( 5 ( r ，口) ) 】此外还要修改一下膨的 起始状态，使得开始时口。把从的起始状态出发沿着箭头可以达到的所有状 态也要包含近来即 g 。t 改为 g o 卜：e c l o s e ( i q o 。】) 就能产生这个效果。 现在已经完成了模拟n f an 的d f am 的构造m 的构造显然是正确的， 在计算的每一步，m 进入的状态明显地对应于此时可能处于的状态子集。 例2 2 2 一台非确定型有穷自动机，它的初始状态为q o ，接受状态为q 2 我们 可以认为，只要自动机还没有“猜测 到结尾的0 1 ，那么自动机就一直处在鸟o ， o j 一 一 图2 3 接受所有以0 1 结尾的串n f a 1 4 可能出现这样的情况：即使下一个符号是o ，这个符号也不是结尾0 1 的开始。 因此，状态q 0 在0 和1 上都可以转移到自身。但如果下一个符号是0 ，这个n f a 也猜测到了结尾0 1 串开始了，因此，这时自动机从状态开始在符号o 的作用 下到达状态9 1 ，吼在符号1 的作用下到达终结状态口：。注意，有两个从q 。出发 带o 标记的箭弧，n f a 可以选择进入吼或者吼，实际上都进入。没有从q 。出发 带。标记的箭弧，在g ；状态下，如果该n f a 验证的下一个符号是l ，则该自动机 就会进入状态g ：。口：是该自动机的终结状态，在该n f a 中，根本没有从q ：出发 的箭。在这种情况下，该n f a 中存在的与这些状态相对应的线路就终止了，但 其它的线路还可继续存在。在某个d f a 中，对每一个输入符号恰好有一个箭弧 离开每一个状态。则与n f an 等价的d f am 的转换图为： 例2 2 3 - - - - 图2 4 例2 2 2 n f a 构造出的d f a 0 图2 5n f an 的状态图 形式描述n 一( q ， o ，q ，6 ，1 ，僻) 其中q = 仙2 ，封，要构造与等价的d f ad ，首先 确定d 的状态。有3 个状态1 ，2 ，3 ，所以d 有8 个状态，d 的每一个状态对应于 的一个状态子集，于是d 的状态集为：【囝，讲，【2 ， 封，仕2 ，扎3 ， 2 ，3 】i ，仉2 ，3 】 其次确定d 的起始状态和接受状态。起始状态是从1 出发沿着箭头能够到达的 所有状态加上1 本身。有一个箭头从1 到3 ，故e c l o s e ( 1 y ) 一让努，d 的接受 状态集是的所有包含接受的状态子集，即【僻，仉2 ) ，仉3 】- ，他2 ，3 1 1 最后确定d 的转移函数。d 的每一个状态遇到输入o 到一个地方、遇到输入1 到一个地方。 状态2 遇到输入o 到2 和3 ，但是从2 和3 不能沿着箭头走得更远，所以在d 中， 状态| 【2 遇到输a o 到 2 ，3 】。因为在中，状态2 遇到1 只能到状态3 ，并且不能 从3 沿着s 箭头走的更远，所以在d 中，状态【2 】遇到输入1 走到状态【3 。因为 在中没有0 箭头从状态1 射出，所以在d 中状态m 遇到0 走到g 。状态 1 遇 到l 走到 2 。因为在中状态3 遇到0 走到1 、而1 又沿着g 箭头回到3 ，所以在d 中状态 3 】遇到0 走到n 封，状态 遇到1 走到g 。 因为1 没有0 箭头指向任何状态，2 用0 箭头指向2 和3 ，并且2 和3 都没有 用s 箭头指向任何地方，所以状态仉2 遇到0 走到 2 ，3 。状态诅2 遇到1 走到 2 ，毋。继续按照这个方式进行，可以得到d 的状态图。 图2 6 例2 2 3n f an 等价的d f ad 的状态图 由定理2 2 1 可以直接得到下面两个推论 推论2 2 4 一个语言被某个d f a 所接受，当且仅当被某个n f a 所接受。 推论2 2 5 一个语言l 被某个占一n f a 接受，当且仅当被某个d f a 所接受。 1 6 第三章确定型有穷自动机的极小化 3 1 确定型有穷自动机的极小化 确定型有穷自动机( d f a ) 的极小化仍是有穷自动机应用及实现的重要问 题之一。d f a 的极小化可以揭示状态之间的内在联系，便于其存储实现。便于 建立用d f a 描述的任务模型，一些理论问题也与极小化思想有关( 6 朱征宇，朱 庆生，2 0 0 1 ； 7 朱征字，朱庆生2 0 0 3 1 5 刘大本，2 0 0 5 ) 。 前面我们已经提到过，状态的极小化过程是指利用等价性将自动机的状态集 划分为一些不相交的子集，使得任何两个不同的子集中的状态都是可区分的，而 同一个子集中的任何两个状态都是等价的。最后，我们可以将形成的等价类用其 中一个元素代表。这就实现了自动机的极小化而不改变它们识别的语言。 下面我们来看一个例子 例3 。1 有穷自动机ml i t ( q ，6 ，q o ，f ) ，其中q = 恤，b ，c ，d ，e ，f ，g ，何 ， 芝一 o ，母，f 。怛 。图3 1 所示 图3 1有穷自动机m 根据第二章确定型有穷自动机状态等价定义，可以做出如下判断： 首先考虑状态哇和g 。串f 不可区分这两者，因为它们都是非接受状态；串0 不 可区分这两者，因为在输h o 时a ( a ，0 ) f l i t b ，a ( g ，0 ) 一g ，二者分别到达状态b 和 g ，这些状态也是非接受的，同样，串1 不可区分a 和g ，因为此时两者分别到 达f 和e ，都是非接受的。串0 1 区分a 和g ，因为6 似，0 1 ) - c ，6 + ( g ，0 1 ) ；e ， 1 7 c 是接受状态，e 是非接受状态。 同样的，我们考虑状态a 和e ，在输入占上，a 和e 都不是接受的，所以s 不区分这两者；在输入1 上，二者都到达状态f ，因此以1 开头的串都不区分a 和 ，即慨，6 似，i x ) l i l t6 。但，l x ) 。我们再考虑以。开头的字符串的情况，串 o 使二者分别到达b 和日，b 和日都不是接受的，所以串0 本身不区分4 和e ， 但是b 和日在输入1 上都到达c ，在输入0 都到达g ，因此以0 开头的所有输入 都不能区分a 和e ，综上所述，无论输入什么样的串都不能区分a 和e ，表示a 和e 是等价状态。树图分割法搜索例3 1 中所有不可区分的状态，如下图： 输入字符 俨，c ，g ， 输入字 应得到 冈 1 _ j 图3 2 树图分割法搜索m 中所有不可区分的状态对 搜索的基本原则是：在同样的输入条件下其相应的次态应彼此等价。这可能存在 三种情况：( 1 ) 对应次态相同；( 2 ) 其次态就是两个现态本身；( 3 ) 其次态是彼 此等价的。首先将所有状态分割成可接受状态集合f 一 c 】- 和不可接受状态集合。 q 1 = 0 4 ，b ，d ，e ，f ，g ，好) ，6 ( 彳，0 ) - b ，6 ( 曰，0 ) 一g ，6 ( d ，0 ) = c ，6 ( ，0 ) 。h ， 6 ( f ，0 ) = c ，6 ( g ，0 ) 一g ，6 ( 日，0 ) 。g ，所以在q 1 中输入字符0 得到对应的转换后 的状态集为q 1 0 - - b ，g ，c ，h ，c ，g ，g ) ，在例3 1 中6 即，1 ) 一f ，6 p ，1 ) tc j 6 ( d ，1 ) 一g ，6 陋，1 ) 一f ，6 ( f ，1 ) eg ，6 ( g ，1 ) te ，6 ( 日，1 ) 二c 因此在q l 中输入1 得到对应的转换后的状态集合为q 1 ，。俨，c ，g ，f ，g ，e ，c ，根据不可区分定义可 以得到如下结论：坛，6 p ，l x ) n f 彩营6 饵，l x ) f l f - a ， 6 ( 曰，0 x ) a f 乒彩静6 饵，0 x ) c if a ，6 + ( d ，h ) nf - 彩营6 ( f ，a x ) n f 一彩， 6 ( d ，帆) n ，一彩营6 + 仃，0 x ) nf 一在第一步中就可以判断口和日，d 和f 是 不可区分的，第二步再在剩余的无法判断的状态集中输入长度为2 的字符，进行 判断，直到求出所有的不可区分的状态对，将所有不可区分的状态进行合并。就 得到例3 1 的极小 如图： 图3 3m 的极小化自动机 树图分割法3 2 ( 1 ) 首先将d f a 所有的状态分割成可接受状态和不可接受状态集。 ( 2 ) 用双圆圈来标记最大的不可区分的状态集合。 。 ( 3 ) 将d f a 所有输入字符按某一个顺序排列。 ( 4 ) 依次输入字符进行判断，直到求出最大不可区分状态集为止。 下面我们再来看一个例子进一步说明树图分割法。 例3 3 设m 一( q ，6 ，日。，f ) 是一台确定型有穷自动机，q 一 o ，1 , 2 ，3 ，4 ， q 。= 0 ，f 一 4 】，一和，6 ，m 的状态转换图如下： 1 9 n 图3 4m 的状态图 用树图分割法来分析例3 3 ： 不 0 ，1 ，2 ，3 ，4 j 丁接受状态可接受状 图3 5树图分割法搜索m 不可区分的状态 首先将m 的状态分割成可接受和不可接受的状态集合，因为可接受的状态和不 可接受状态是可以区分的，再分别对可接受状态集合和不可接受状态集合输入字 符进行判断找出不可区分的状态，在例3 3 中，可接受的状态只有一个是状态4 ， 所以状态4 与其它的状态都是可区分的。在不可接受集合中，先输入长度为1 的 字符a , b 来搜索在一步内不可区分的状态，状态3 与其它状态都是可以区分的， 而且可以判断状态0 和2 是在任何情况下都是不可区分的，最后求出所有不可区 分的状态，将所有不可区分的对合并成一个状态，就得到原自动机的极小化自动 机。由图3 5 判断出的不可区分的状态对进行合并，得到例3 3 中自动机m 的 极小化自动机。如下图： 2 0 图3 6 例3 3 的极小化自动机 这阶段的主要任务是采用树图分割法来极小化d f a 。该方法的主要思想是：将 d f a 分割成一些不相交的子集，使得任何不同两个子集的状态是可区分的，而 同一子集中任何两个状态是不可区分的。也就是说，构造状态集的一个划分，再 将这个划分中的每个子集作为新的状态，就得到等价的极小化的d f a 。下面证