首页 > DFA最小化算法中状态等价判断方法

DFA最小化算法中状态等价判断方法

发布时间：2023-03-28 13:46:20 来源：文档文库

小中大

字号：

手机查看

第１Ｏ卷第６期　Ｖ０１．１Ｏ．Ｎｏ．６　宜宾学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｙｉｂｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　２０１０年６月　Ｊｕｎｅ，２０１０　ＤＦＡ最小化算法中状态等价判断方法　刘益　（宜宾学院计算机与信息工程学院，四川宜宾６４４０００）　摘要：对使用‘‘分割法’’最小化ＤＦＡ中出现的当一个状态没有相应的产生式存在时如何进行分割，提出了正确使用“分割法”最小化ＤＦＡ关键是需要正　确判断ＤＦＡ中各个状态之间的等价关系，并对当一个状态没有相应的产生式存在时如何判断等价进行了分析．　关键词：ＤＦＡ；最小化；分割法　中图分类号：ＴＰ３０１．１　文献标志码：Ａ　文章编号：１６７１－５３６５（２０１０）０６－００５５－０２　Ａｎ　Ｅｑｕａｔｉｏｎ　Ｒｅｌａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｎ　ｔｈｅ　Ｍｉｎｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｏｆ　ＤＦＡ　ＬＩＵ　Ｙｉ　（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｙｉｂｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｙｉｂｉｎ　６４４０００　Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｓ　ｆｏｒ　ａ　ｓｔａｔｅ　ｗｉｔｈｏｕｔ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｐｒｏｄｕｃｔｉｏｎ　ｕｓｉｎｇ　ｔｈｅ　ｓｅｇｍｅｎｔａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｍｉｎｉｍｉｚｅ　ＤＦＡ，ｔｈｅ　ｋｅｙ　ｉｓ　ｔｏ　ｊｕｄｇｅ　ｔｈｅ　ｅｑｕａｔｉｏｎ　ｒｅｌａｔｉｏｎ　ａｍｏｎｇ　ｓｔａｔｅｓ．Ａｎｄ　ｔｈｅ　ｅｑｕａｔｉｏｎ　ｒｅｌａｔｉｏｎ　ｆｏｒ　ａ　ｓｔａｔｅ　ｗｉｔｈｏｕｔ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｐｒｏｄｕｃｔｉｏｎ　ｗａｓ　ａｎａｌｙｚｅｄ．　Ｋｅｙ　ｗｏｒｄｓ：ＤＦＡ；ｍｉｎｉｍｉｚａｔｉｏｎ；ｓｅｇｍｅｎｔａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　确定有限自动机ＤＦＡ（Ｄｅｔｅｒｍｉｎｉｓｉｔｉｃ　Ｆｉｎｉｔｅ　Ａｕｔｏｍａ－　ｔｉｏｎ）的应用范围很广，它可以作为识别语言、电路设计、模　采用“分割法”后得到：　ＤＦＡ　Ｍ’＝（｛Ｓ，ａ，ｂ｝，｛０，１｝，８，Ｓ，｛ａ｝），且：　６（Ｓ，０）＝ａ　６（Ｓ，１）＝ａ　８（ｂ，１）：ａ　型检测以及加密算法等方面的一种工具　．一个ＤＦＡ的　获得一般是通过对ＮＦＡ确定化后得到．但这样的ＤＦＡ可　分析在文献　中的例子，例子２：　ＤＦＡ　Ｍ＝（｛０，１，２，３｝，｛ａ，ｂ｝，６，０，｛２，３｝），且：　６（０，ａ）：１　８（１，ａ）＝１　８（１，ｂ）＝２　８（２，ａ）＝３　８（２，ｂ）＝３　８（３，ａ）＝３　８（３，ｂ）＝３　采用“分割法”后得到：　能含有多余状态，还需要对其进行最小化．最小化后的　ＤＦＡ即可以更好地表示状态之间的内在关系，也便于在利　用ＤＦＡ描述任务模型时提高计算机的工作效率．对ＤＦＡ　进行最小化的方法常采用“分割法”．在一些特殊情况下使　用分割法最小化ＤＦＡ，会出现最小化后的ＤＦＡ与最小化　前的ＤＦＡ不等价　，说明分割法在最小化ＤＦＡ中可能存　ＤＦＡ　Ｍ’＝（｛０ｌ，２３｝，｛ａ，ｂ｝，８，０１，｛２３｝），且：　６（０ｌ，ａ）＝Ｏ１　６（Ｏ１，ｂ）＝２３　８（２３，ａ）＝２３　６（２３，　ｂ）＝２３　在缺陷．本文将对这个问题进行分析，找出在使用分割法　最小化ＤＦＡ过程中存在的误区．　从上两例看出：采用分割法后得到的ＤＦＡ　Ｍ’与ＤＦＡ　１问题的提出　ＤＦＡ的最小化是指一个ＤＦＡ中不存在多余状态，并　且在其状态集中不存在两个相互等价的状态，但必须保证　最小化后的ＤＦＡ与最小化前的ＤＦＡ能够识别相同的语言　集．如果最小化后的ＤＦＡ与最小化前的ＤＦＡ不能识别相　Ｍ不能识别相同的语言集．因此文献作者提出的分割法算　法有问题，在一些ＤＦＡ最小化上不能给出正确结论．　２　ＤＦＡ最小化算法分析　分割法通过对ＤＦＡ　Ｍ的状态集进行分析，将集合分　割成一些不相交的子集．划分之后，这些子集中的状态是　同的语言集，则称它们是不等价，即在最小化过程中出现　了错误．　等价的．然后从每个子集中选出一个元素，消去其他元素，　重新构造一个ＤＦＡ　Ｍ’．这个ＤＦＡ　Ｍ’就是最小化的，而且　Ｌ（Ｍ）＝Ｌ（Ｍ’）．可以看出，分割法是对状态集的集合分　分析文献　中的例子，例子１：　ＤＦＡ　Ｍ＝（｛Ｓ，ａ，ｂ｝，｛０，１｝，６，Ｓ，｛ａ，ｂ｝），且：　８（Ｓ，０）＝ａ　６（ｓ，１）＝ｂ　６（ｂ，１）＝ａ　收稿日期：２０１０—０３—１６．修回：２０１０—０５—１２　割，而划分的依据是集合中元素之间的等价问题．因此，分　割法的核心问题是讨论状态集中各状态之间的等价问题．　作者简介：刘益（１９７１一），男，四川宜宾人，讲师，硕士研究生，主要从事人工智能研究　
５６　宜宾学院学报　第１０卷　所谓两个状态相互等价是指：对一给定的ＤＦＡ　Ｍ，若　根据状态是否等价的判断，从状态０出发识别字符串　“存在状态ｓｌ、ｓ２∈Ｓ且ｓｌ≠ｓ２，如果从ｓ１出发能识别字符　串　而停于终态，从ｓ２出发也同样能够识别这个　而停　于终态；反之，若从ｓ２出发能识别１３而停于终态，则从ｓｌ　出发也能识别这个ｐ而停于终态，则称ｓｌ和ｓ２是等价的，　ａａｂｂｂ”停于终态，或者字符串“ａａａｂ￣”停于终态；而从状　ａａａｂａａ”停于终态，或者字符串“ｂａａａ”停于终态，或者字　态ｌ出发识别字符串“ａａｂｂｂ”停于终态，或者字符串　“符串“ｂｂｂｂ”停于终态．换句话说，从状态０出发识别的字　否则就是可区分的　，如例１：　ＤＦＡ　Ｍ＝（｛ｓ，ａ，ｂ｝，｛０，１｝，６，Ｓ，｛ａ，ｂ｝），且：　８（ｓ，０）＝ａ　８（ｓ，１）＝ｂ　８（ｂ，１）＝ａ　当采用分割法进行最小化的时候，在分析状态集合中　各状态之间是否等价出了问题．文献　４　中在分割法中认为　状态ａ，ｂ之间是等价的．原因是：　对于输入字符０，状态ａ和ｂ都找不到相应的产生式　进行转换．可以认为对于输人字符０，状态ａ和ｂ等价．　对于输入字符１，状态ｂ能找到产生式６（ｂ，１）＝ａ，意　味着它可以转换到状态ａ；对于状态ａ，没有相应的产生　式，那么它与状态ｂ没有区别，因此对于输入字符１，状态　ａ和ｂ等价．　综上所述，状态ａ和ｂ等价，可以把它们放到同一个　子集中．得到新的ＤＦＡ　Ｍ’：　ＤＦＡ　Ｍ’＝（｛ｓ，ａ｝，｛０，１｝，６，Ｓ，｛ａ｝），且：　８（Ｓ，０）＝ａ　６（ｓ，１）＝ｂ　８（ａ，１）＝ａ　根据状态是否等价的判断，从状态ｂ出发识别字符串　“１”停于终态，而从状态ａ出发不能识别任何字符串．因此　说状态ａ和ｂ等价是错误的．对ＤＦＡ　Ｍ来讲已经是最简化　的了，如例２：　ＤＦＡ　Ｍ＝（｛０，１，２，３｝，｛ａ，ｂ｝，８，０，｛２，３｝），且：　６（０，ａ）＝１　８（１，ａ）＝１　８（１，ｂ）＝２　８（２，ａ）：３　８（２，ｂ）＝３　６（３，ａ）＝３　６（３，ｂ）：３　对于输入字符ａ，状态０有产生式８（０，ａ）＝１，状态１　有８（１，ａ）：１，状态２有产生式８（２，ａ）＝３，状态３有６　（３，ａ）＝３；对于输入字符ａ，状态０、ｌ可以认为等价，状态　２、３可以认为等价．　对于输入字符ｂ，状态０没有对应的产生式，状态１有　８（１，ｂ）＝１，状态２有产生式８（２，ｂ）：３，状态３有８（３，　ｂ）＝３；对于输入字符ｂ，状态２、３可以认为等价．而对于状　态０、１同样存在例子１中的问题，由于对状态０在输入字　符ｂ的时候没有对应的产生式，也认为０、ｌ等价．　综上所述，把状态０、１放到同一个子集中，状态２、３　放到另一个子集中．得到新的ＤＦＡ　Ｍ’：　ＤＦＡ　Ｍ’：（｛０ｌ，２３｝，｛ａ，ｂ｝，６，０１，｛２３｝），且：　６（０１，ａ）＝０１　６（０１，ｂ）＝２３　６（２３，ａ）＝２３　６（２３，　ｂ）：２３　符串必须以字母ａ开始，而从状态１出发识别的字符串可　以是字母ｂ开始，因此对于状态０和１来说是不等价的．对　于状态２、３则能识别相同字符串，它们是等价的．ＤＦＡ　Ｍ最　小化后应该为：‘　ＤＦＡ　Ｍ’＝（｛０，１，２３｝，｛ａ，ｂ｝，６，０１，｛２３｝），且：　８（ｏ，ａ）＝１　８（１，ａ）＝１　８（１，ｂ）＝２３　８（２３，ａ）＝　２３　６（２３，ｂ）＝２３　３小结　文献　中针对在识别输入字符的时候没有相应的产　生式与之对应，提出了“失败状态”．在文献　中对此类问　题提出了“空集‘ｐ改成特殊的‘ｐ状态”．实际上，无论是　“失败状态”还是“特殊状态”，如果在当前状态，对于给出　的一个字符，在产生式集合中没有对应的产生式，则表示　当前状态出发不能识别相应的字符．根据分割法原理，在　分割一个子集的时候，子集中状态对某字符出现一个状态　有对应的产生式，而另一个状态没有，这两个状态肯定是　不等价的．　参考文献：　［１］沈浩，孙永强．自动机，逻辑与博弈［Ｊ］．计算机工程，２００３，２９　（２Ｏ）：９－１１．　［２］陶仁骥．一种有限自动机公开钥密体制和数字签名［Ｊ］．计算机学　报，１９８５，８（６）：４０１－４０９．　［３］陈义仁，王一宾．ＤＦＡ化简算法的一种改进方法［Ｊ］．安庆师范学　院学报（自然科学版），２００９，１５（１）：４５－４８．　［４］周时阳，祝建华．ＤＦＡ最小化算法研究［ｊ］．计算机工程与科学，　２００７，２９（３）：６０－６２．　［５］徐红．对确定有限自动机最小化算法的改进［ｊ］．桂林航天工业高　等专科学校学报，２００５（４）：１４—１６．　［６］吕映芝，张素琴，蒋维杜．编译原理［Ｍ］．北京：清华大学出版社，　１９９８．　［７］胡元义．编译原理教程［Ｍ］．西安：西安电子科技大学出版社，　２０ｏ３．　［８］陈火旺，钱家骅，孙永强．程序设计语言编译原理（第三版）［Ｍ］．　北京：国防工业出版社，２０００．　［９］罗军．确定的有限自动机（ＤＦＡ）化简方法改进［Ｊ］．河南广播电视　大学学报，２００５，１８（３）：５５－５７．　【编校：李青】　

本文来源：https://www.2haoxitong.net/k/doc/da2fe10f964bcf84b9d57b7c.html