文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 基于子集构造法的优化的NFA确定化算法

基于子集构造法的优化的NFA确定化算法

发布时间：2023-02-25 15:00:21   来源：文档文库   
小 中 大
字号：
手机查看
第２１卷第１期　计算机技术与发展　Ｖｏ１．２１　Ｎｏ．１　２０１１年１月　ＣＯＭＰＵＴＥＲ　ＴＥＣＨＮＯ１　０ＧＹ　ＡＮＩ）ＤＥＶＥＩ　ＯＰＭ　ＥＮｑ、　Ｊａｎ．　２０ｌ１　基于子集构造法的优化的Ｎ　ＦＡ确定化算法　任平红，陈　矗，曹宝香，禹继国　（山东曲阜师范大学计算机科学学院，山东日照２７６８２６）　摘要：使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题，基于非确　定有限自动机的特点并针对子集构造法的不足，提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的　有效引出状态集概念并证明了Ｐ￣ｃ］ｏｓｕｒｅ的并定理以保证算法的正确性，其次给出了用于避免重复计算的识别符的有效　引出状态集的构造子算法和单状态集的ｓ—ｃｌｏｓｕｒｅ的求算子算法，基于这两个子算法给出了优化的非确定有限自动机确　定化算法，最后将算法应用于实例，实验结果表明计算量远小于子集构造法的计算量。相比子集构造法，算法能更有效地　对非确定有限自动机进行确定化。　关键词：子集构造法；非确定有限自动机；优化的；确定化算法　中图分类号：ＴＰ３０１．１　文献标识码：Ａ　文章编号：１６７３—６２９Ｘ（２０１１）Ｏ１￣００７０—０４　Ａｎ　Ｏｐｔｉｍｉｚｅｄ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｔｒａｎｓｉｔｉｏｎ　ｆｒｏｍ　ＮＦＡ　ｔｏ　ＤＦＡ　Ｂａｓｅｄ　ｏｎ　Ｓｕｂｓｅｔ　Ｃｏｎｓｔｒｕｃｔｉｏｎ　Ｍｅｔｈｏｄ　ＲＥＮ　Ｐｉｎｇ—ｈｏｎｇ，ＣＨＥＮ　Ｃｈｕ，ＣＡＯ　Ｂａｏ－ｘｉａｎｇ，ＹＵ　Ｊｉ－ｇｕｏ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｑｕｆｕ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｒｉｚｈａｏ　２７６８２６，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｒｅｐｅｔｉｔｉｖｅ　ｃｏｍｐｕｔｉｎｇ　ｅｘｉｔｓ　ｉｎ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｔｒａｎｓｉｔｉｏｎ　ｆｒｏｍ　ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃ　ｉｆｎｉｔｅ　ａｕｔｏｍａｔａ　ｔＯ　ｄｅｔｅｒｍｉｎｉｓｔｉｃ　ｆｉ—　ｎｉｔｅ　ａｕｔｏｍａｔａ　ｕｓｉｎｇ　ｔｈｅ　ｓｕｂｓｅｔ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｍｅｔｈｏｄ，Ｔｏ　ｓｏｌｖｅ　ｔｈｉｓ　ｐｒｏｂｌｅｍ，ａｌｌ　ｏｐｔｉｍｉｚｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｒａｎｓｉｔｉｏｎ　ｆｒｏｍ　ＮＦＡ　ｔＯ　ＤＦＡ　ｉｓ　ｐｕｔ　ｆｏｒｗａｒｄ　ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｃｈａｒａｃｔｅｒｓ　ｏｆ　ＮＦＡ　ａｎｄ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｓｈｏｒｔｃｏｍｉｎｇｓ　ｏｆ　ｔｈｅ　ｓｕｂｓｅｔ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｍｅｔｈｏｄ．Ｆｉｒｓｔ，ｔｈｅ　ｃｏｎｃｅｐｔ　ｔｈａｔ　ｅｆｆｅｃ—　ｔｉｖｅ　ｓｏｕｒｃｅ　ｓｔａｔｅ　ｓｅｔ　ｆｏｒ　ａ　ｍａｒｋ　ｓｙｍｂｏｌ　ｉｓ　ｄｅｆｉｎｅｄ　ａｎｄ　ｔｈｅ　ｔｈｅｏｒｅｍ　ｔｈａｔ　ｃｏｍｂｉｎａｔｉｏｎ　ｏｆ　ｓ—ｃｌｏｓｕｒｅ　ｉｓ　ｐｒｏｖｅｄ．Ｔｈｅ　ｔｈｅｏｒｅｍ　ｇｕａｒａｎｔｅｅｓ　ｔｈｅ　ｉｒｇｈｔｎｅｓｓ　ｏｆ　ｔｈｅ　ｆｏｌｌｏｗｉｎｇ　ａｌｇｏｒｉｔｈｍｓ．Ｓｅｃｏｎｄ，ｔｗｏ　ｓｕｂ　ａｌｇｏｒｉｔｈｍｓ　ｔｈａｔ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　ｅｆｆｅｃｔｉｖｅ　ｓｏｕｒｃｅ　ｓｔａｔｅ　ｓｅｔ　ｆｏｒ　ａ　ｍａｒｋ　ｓｙｍｂｏｌ　ａｎｄ　ｈｔａｔ　ｃｏｍｐｕｔｉｎｇ　ｓ—ｃｌｏｓｕｒｅ　ｏｆ　ａ　ｓｅｔ　ｗｉｔｈ　ｏｎｌｙ　ｏｎｅ　ｓｔａｔｅ　ａｒｅ　ｇｉｖｅｎ．Ｂａｓｅｄ　ｏｎ　ｔｈｅｓｅ　ｓｕｂ　ａｌｇｏｒｉｔｈｍｓ，ｔｈｅ　ｏｐｔｉｉｍｚｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｒｎａｓｉｔｉｏｎ　ｒｆｏｍ　ＮＦＡ　ｔＯ　ＤＦＡ　ｉｓ　ｇｉｖｅｎ．Ｉｎ　ｔｈｅ　ｅｎｄ，ａｌｌ　ｅｘｐｅｒｉｍｅｎｔ　ｉｓ　ｃａｒｒｉｅｄ　ｏｕｔ　ａｎｄ　ｔｈｅ　ｒｅｓｕｌｔ　ｓｈｏｗｓ　ｔｈａｔ　ｃｏｍｐｕｔｉｎｇ　ａｍｏｕｎｔ　ｏｆ　ｔｈｉｓ　ａｌｇｏｒｉｔｍｈ　ｉｓ　ｆａｒ　ｌｅｓｓ　ｔｈａｎ　ｔｈａｔ　ｏｆ　ｓｕｂｓｅｔ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｍｅｔｈｏｄ．Ｃｏｍｐａｒｉｎｇ　ｔＯ　ｓｕｂｓｅｔ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｍｅｔｈｏｄ，ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　Ｃａｎ　ｃｏｎｖｅｒｔ　ＮＦＡ　ｔＯ　ＤＦＡ　ｍｏｒｅ　ｅｆ－　ｉｆｃｉｅｎｆｌｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｕｂｓｅｔ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｍｅｔｈｏｄ；ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｉｔｃ　ｆｉｎｉｔｅ　ａｕｔｏｍａｍ；ｏｐｔｉｉｍｚｅｄ；ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｒａｎｓｉｉｔｏｎ　ｆｒｏｍ　ＮＦＡ　ｔｏ　ＤＦＡ　０　引　言　存在ｓ—ｅ］ｏｓｕｒｅ重复计算和由于对非８转换的判断而　作为计算机科学的基础，有限自动机（Ｆｉｎｉｔｅ　Ａｕ—　引起的重复计算等问题　。当ＮＦＡ状态集元素数　ｔｏｍａｔａ，ＦＡ）可以抽象绝大多数计算机领域的有限系　量较多时重复计算的问题非常严重。为解决此问题，　统，广泛应用于自然语言处理　和串匹配　等诸多方　提出一种基于子集构造法的优化的ＮＦＡ确定化算法，　面。非确定有限自动机（Ｎｏｎ—ｄｅｔｅｒｍｉｎｉｓｔｉｃ　Ｆｉｎｉｔｅ　Ａｕ—　可以有效地避免重复计算的问题。　ｔｏｍａｔａ，ＮＦＡ）是ＦＡ理论的重要组成部分，ＮＦＡ的化　简　和确定化　具有重要的理论和实际意义。目　１识别符的有效引出状态集概念和　—ｃｌｏ－　前广为采用的子集构造法　’　虽然能够正确地完成　ｓｕｒｅ　定理　ＮＦＡ的确定化，但是在确定化过程中对于ＮＦＡ状态集　为规整起见，首先给出ＮＦＡ的一般定义并在全文　中统一使用其定义中的符号。　收稿日期：２０１０—０５－３１：修回日期：２０１０—０９—０３　定义１　“：ＮＦＡ定义为一个四元组：Ｍ＝（Ｑ，　，６，　基金项目：ｆＩｆ东省优秀中青年科学家奖励基金（２００５ＢＳ０１０１６）　ｑ　Ｆ）。其中：Ｑ是状态集，　是基本字母表，６是状态　作者简介：任平红（１９８０～），女，山东德州人，讲师，硕士，研究方向为　转换函数（Ｑ　Ｘ（　ｕ｛　｝）一２　），ｑ。是开始状态，Ｆ是　计算机图形图像处理、算法；曹宝香，教授，研究方向为图形图像处　终态集。　理、算法；禹继国，教授，膊士，研究方向为算法。　基于ＮＦＡ的定义，定义２给出识别符的有效引出　
第１期　任平红等：基于子集构造法的优化的ＮＦＡ确定化算法　・７１　状态集的定义。　定义２：对于识别符Ｕ（ａ∈　）有效的引出状态集　在第二节中给出。　｝。　Ｅ［Ｕ］定义为：Ｅ［ａ］＝｛ｑ　ｌ　ｑ∈Ｑ＾占（ｑ，ａ）≠　２识别符的有效引出状态集的构造子算法　和单状态集的　一ｃｌｏｓｕｒｅ求算子算ｔ　基于定义２、定理１和推论１，给出识别符的有效　引出状态集Ｅ［ａ］的构造子算法和单状态集的　—　ｃｌｏｓｕｒｅ的求算子算法，并在第三节中用于基于子集构　造法的优化的ＮＦＡ确定化算法中。　２．１　识别符的有效引出状态集的构造子算法　识别符的有效引出状态集Ｅ［ａ］指出了ＮＦＡ中哪　些状态具有标识为Ｕ的转移，对应于ＮＦＡ状态图中具　有标识为ａ的引出弧的状态集合。在ＦＡ理论中，由于　需要对确定有限自动机（Ｄｅｔｅｒｍｉｎｉｓｔｉｃ　Ｆｉｎｉｔｅ　Ａｕｔｏｍａｔａ，　ＤＦＡ）进行最小化，而使用分割算法对非完全ＤＦＡ直　接进行最小化存在一些问题　，所以非完全ＤＦＡ需　要转换为完全ＤＦＡ　。ＮＦＡ的确定化不存在同样的　问题，所以不需要将非完全的ＮＦＡ转换为完全的　ＮＦＡ。对于一个非完全的ＮＦＡ，Ｅ［ａ］　Ｑ。在子集构　造法中，扫描状态转换矩阵会造成对（Ｑ—Ｅ［ａ］）这一　部分状态集的无效判断和计算，如果能计算出Ｅ［ａ］　就可以避免这些无效判断和计算。在第二节中将给出　计算Ｅ［ａ］的子算法。　定义３　：ＮＦＡ单状态集｛　｝（ｓ　Ｅ　Ｑ）的８一　ｃｌｏｓｕｒｅ定义为：ｓ—ｃｌｏｓｕｒｅ（｛ｓ｛）＝｛Ｐ　ｌ　Ｐ∈Ｑ　Ａ　Ｐ∈　６（５，占：｝：）｝；ＮＦＡ状态集　（　Ｑ）的ｓ—ｃｌｏｓｕｒｅ定义　为：ｓ—ｃｌｏｓｕｒｅ（Ｔ）＝｛ｓ　Ｉ　ｓ　Ｅ占一ｃｌｏｓｕｒｅ（ｔ）＾ｔ　Ｅ　Ｔ｝。　定义３中ＮＦＡ单状态集的ｓ—ｃｌｏｓｕｒｅ和状态集的　８一ｃｌｏｓｕｒｅ都是无序集合，基于此性质和定义３可以得　如下定理和推论：　定理１：　一ｃｌｏｓｕｒｅ（Ｔ）＝ｕ　—ｃｌｏｓｕｒｅ（｛ｔ｝）。　证明：根据定义３，８一ｃｌｏｓｕｒｅ（Ｔ）＝｛ｓ　ｌ　∈８一　ｃｌｏｓｕｒｅ（ｔ）Ａ　ｔ∈Ｔ｝＝Ｕ　｛Ｐ　ｌ　Ｐ∈Ｑ＾Ｐ　Ｅ　（ｔ，　：Ｉｃ）｝　＝　ｓ—ｃｌｏｓｕｒｅ（…）。　定理１说明求解状态集的ｓ—ｃｌｏｓｕｒｅ可以转变为　求解单状态集的　—ｃｌｏｓｕｒｅ，子集构造法中ＮＦＡ每个　状态集的ｓ—ｃｌｏｓｕｒｅ不必完全重新计算，可以依托于　ＮＦＡ每个单状态集｛ｔ｝（ｔ∈Ｑ）的计算来完成。　由定理１可得如下推论：　推论１：８一ｃｌｏｓｕｒｅ（Ｔ）＝ｕ　ｓ—ｃｌｏｓｕｒｅ（Ｔ　）。　证明：　一ｃｌｏｓｕｒｅ（　）＝｛ｓ　Ｉ　ｓ∈８一ｃｌｏｓｕｒｅ（ｔ）八　ｔ∈Ｔ｝＝Ｕ｛ｒ　ｒ　ｓ　ｌ　ｓ∈ｓ—ｃｌｏｓｕｒｅ（ｔ）＾ｔ∈Ｔ　｝：Ｕ　ｒ　ｒ　—ｃｌｏｓｕｒｅ（Ｔ　）。　推论１说明求解状态集　的　—ｃｌｏｓｕｒｅ可以转变　为求解其子集　的ｓ—ｃｌｏｓｕｒｅ，当Ｉ　Ｉ＝１时就转变为　定理１中求解的情况。　子集构造法中不同状态集的占一ｃｌｏｓｕｒｅ计算过程　中可能存在重复计算的部分。当状态集元素数量较多　时，重复计算现象非常严重。在ＮＦＡ确定化过程中应　用定理１或推论１的结论可以避免重复计算以提高计　算的效率。为应用定理１或推论ｌ，需要计算单状态集　的　一ｃｌｏｓｕｒｅ，单状态集的８一ｃｌｏｓｕｒｅ的求算子算法将　算法思想：按列扫描ＮＦＡ的状态转换矩阵一遍，　当到达状态在Ｑ中时将出发状态加入对应识别符的有　效引出状态集Ｅ［ａ］中，一遍扫描后对于　中任意识别　符ａ的Ｅ［ａ］都计算完毕。　识别符的有效引出状态集Ｅ［ａ］的构造子算法的　类ｃ伪代码具体描述如下：　输入：ＮＦＡ　Ｍ：（Ｑ，　，　，ｑ。，Ｆ）。　输出：Ｅ［ａ］（Ｖ　ａ　Ｅ　）。　方法：　’＝　；　ｗｈｉｌｅ（　’≠　）｛　Ｖ　ａ　Ｅ　’：　ｆｏｒ（Ｖ　ｑ∈Ｑ）　ｉｆ（６（ｑ，ａ）≠　）　ａ］＋＝｛ｑ｝；　三’一：｛ａ｝；　｝　通过识别符的有效引出状态集Ｅ［ａ］可避免ＮＦＡ　状态集（对应ＤＦＡ的某个状态）中没有标识为ａ的引　出弧的状态的无效判断和计算。　２．２　单状态集的ｅ－ｃｌｏｓｕｒｅ的求算子算法　算法思想：对于ＮＦＡ的任意一个状态ｑ（ｑ∈Ｑ）构　成的单状态集｛ｑ｝，如果ｑ有一个或一个以上的　一转　换到达Ｑ中的状态，则８一ｃｌｏｓｍ。ｅ（｛ｑ｝）只需引用这些　状态分别对应的单状态集的ｓ—ｃｌｏｓｕｒｅ的计算结果及　｛ｑ｝的并集即可。　单状态集｛ｑ｝的　一ｃｌｏｓｕｒｅ（｛ｑ｝）求算子算法的　类ｃ伪代码具体描述如下：　输入：ＮＦＡ　Ｍ＝（Ｑ，　，６，ｑ。，Ｆ）。　输出：　一ｃｌｏｓｕｒｅ（｛ｑ｝）（Ｖ　ｑ∈Ｑ）。　方法：　Ｑ’＝Ｑ；　ｗｈｉｌｅ（Ｑ’≠（２））｛　ｆｏｒ（Ｖ　ｑ∈Ｑ’）　ｉｆ（６（ｑ，ｇ）＝＝　）８一ｃｌｏｓｕｒｅ（｛ｑ｝）：　ｅｌｓｅ　ｉｆ（艿（ｑ，ｓ）＝＝Ｔ）ｓ—ｃｌｏｓｕｒｅ（｛ｑ｝）：｛ｑ｝＋　∑８一ｃｌｏｓｕｒｅ（｛ｔ｝）；　
・７２－　计算机技术与发展　第２ｌ卷　’一＝｛ｑ｝；　｝　单状态集８一ｃｌｏｓｕｒｅ（｛ｑ｝）的计算采用了递归计　算，ｓ—ｏｌｏｓｌｌｒｅ（｛ｑ｝）只依赖于８（ｑ，８）集合中的元素　的单状态集的ｓ—ｅ｜ｏｓＨｒｅ。当算法结束时，任意单状　态集的ｓ—ｃｌｏｓｕｒｅ都可以被计算出来。根据定理１，任　意ＮＦＡ状态集的ｓ—ｃｌｏｓｕｒｅ可通过其元素状态的单状　态集的ｓ—ｃｌｏｓｌｌｒｅ的合并得到。这样就避免子集构造　法中通过入栈出栈　叫把每一个ＮＦＡ状态集的每一个　状态都计算８一ｃｌｏ￥１１ｒｅ而带来的大量的重复计算。　３优化的ＮＦＡ确定化算法　以子集构造法的基本方法为基础，应用识别符的　有效引出状态集Ｅ［ｎ］的构造子算法和单状态集的　一ｃｌｏｓｕｒｅ的求算子算法，得到优化的ＮＦＡ确定化算　法，其类ｃ伪代码具体描述如下：　输入：ＮＦＡ　Ｍ＝（Ｑ，　，８，ｑ。，　’）。　输出：ＤＦＡ　Ｍ’＝（Ｑ’，　，８’，ｑ。’，Ｆ’）。　方法：　调用识别符的有效引出状态集的构造子算法；　调用单状态集的占一ｃｌｏｓｕｒｅ的求算子算法；　Ｑ’＝｛８一ｅｌｏｓＩｌｒｅ（｛ｑ。｝）｝；　ｕｒｌｍａｒｋ＝｛　—ｃｌｏｓｕｒｅ（｛ｑ０｝）｝；　ｍａｒｋ＝　；ｗｈｉｌｅ（ｕｎｍａｒｋ≠　）｛　Ｖ　Ｕ∈ｕｎｍａｒｋ：　ｆｏｒ（Ｖ　ｎ∈　）｛　ＥＳ＝Ｕ　ｎ　Ｅ［ｎ］；　Ｔ＝６（ＥＳ，８）；　Ⅳ＝∑８一ｃｌｏｓｕｒｅ（…）；　ｉｆ！（Ｎ∈Ｑ’）｛　ｐ’＋＝｝Ⅳ｝；　６’［Ｕ，０］＝Ⅳ；　｝　｝　’　ｉｌｉｌｍａｒｋ一＝｛Ｕ｛；　ｍａｒｋ＋＝｛Ｕ｝；　｝　重命名Ｑ’和６’对应元素，其中ｓ—　ｅ］ＯＳｌｌｒｅ（｛ｑ。｝）重命名为ｇ。’；　Ｆ’＝｛ｆＩ　ＶＭ∈ｍａｒｋ，（Ｍ　ｎ　Ｆ≠　）＾（　重　命名为　）｝；　得到ＤＦＡ　Ｍ’并且Ｍ’　Ｍ。　算法开始时通过调用识别符的有效引出状态集的　构造子算法求得基本字母表　中每一个基本字母的有　效引出状态集，通过调用单状态集的ｓ—ｃｌｏｓｕｒｅ的计　算子算法得到ＮＦＡ状态集９巾每一个状态作为唯一・　元素的状态集的。一ｃ｜ｏｓｌｌｒｅ供算法的后续步骤使用。　算法中ｕｎｍａｒｋ是一个存放未被处理的ＮＦＡ状态集的　集合，ｍａｒｋ是一个存放已经处理的ＮＦＡ的状态集的集　合。算法通过一个ｗｈｉｌｅ循环完成从ＮＦＡ状态集及其　转换表向对应ＤＦＡ状态及其转换表的转变。此循环　中ＥＳ是ＮＦＡ状态集中具有标识为。的引出弧的状态　子集，　是状态子集中的状态识别。后转换到的状态　集，Ⅳ是ｒ中状态的单状态集的８一ｃｌｏｓｕｒｅ的并集。当　Ⅳ与已知状态集不同时将其加入ＤＦＡ的状态集９’中　（对应于ＤＦＡ的一个状态）并把相应的转换函数　６’［Ｕ，０］＝Ｎ加入ＤＦＡ的６’中。每一次循环的最后　把该次循环处理的ＮＦＡ的状态集从ｕｎｍｌｔｒｋ集中移除　并移入ｍａｒｋ集中。　４实例分析　通过下面的实例说明算法的应用及对避免重复计　算的有效性。设ＮＦＡ　Ｍ＝（Ｑ，　，６，％，Ｆ），其中：Ｑ　＝｛０，１，２，３，４，５，６，７，８，９，１０｝，　＝｛口，ｂ｝，８＝｛８（ｏ，０）　＝　，６（０，ｂ）＝　，　（０。ｓ）＝｛１，７｝，６（１，口）：　，８（１，　ｂ）：　，６（１，ｓ）：｛２，４｝，８（２，０）＝｛３｝，８（２，６）＝　，　６（２，ｓ）＝　，艿（３，０）＝　，８（３，６）＝　，８（３，　）＝　｛６｝，８（４，０）＝　，８（４，ｂ）＝｛５｝，８（４，　）＝　，８（５，　ｏ）＝　，　（５，６）＝　，艿（５，　）＝｛６｝，Ｂ（６，口）＝　，　８（６，ｂ）＝　，８（６，ｓ）＝｛１，７｝，６（７，口）＝｛８｝，８（７，ｂ）　＝⑦，８（７，　）＝　，８（８，口）＝　，占（８，ｂ）＝｛９｝，８（８，　ｓ）＝　，占（９，ａ）＝　，６（９，６）＝｛ｌ０｝，８（９，　）＝　，　（１０，口）＝　，　（１０，ｂ）＝　，　（１０，ｇ）：　｝，ｑ。＝０，Ｆ　＝｛１０｝。　根据识别符的有效引出状态集的构造子算法可　得：Ｅ［ｏ］＝｛２，７｝，Ｅ［ｂ］＝｛４，８，９｝。根据单状态集的　ｓ—ｃｌｏｓｕｒｅ的求算子算法可得：８一ｃｌｏｓｕｒｅ（｛０｝）＝｛０｝　ｕ　一ｅ］ｏｓｌｌｒｅ（｛１｝）Ｕ占一ｉ￣ｌｏｓｕｒｅ（｛７｝），　—　ｃｌｏｓｕｒｅ（｛１｝）＝｛１｝Ｕ　ｓ—ｃｌｏｓｕｒｅ（｛２｝）ｕ　—　ｃｌｏｓｕｒｅ（｛４｝），　一　ｃｌｏｓｕｒｅ（｛２｝）　＝　｛２｝，ｓ　—　ｃｌｏｓｕｒｅ（｛３｝）＝｛３｝Ｕ　ｓ—ｅｌｏｓＨｒｅ（｛６｝），　一　ｃｌｏｓｕｒｅ（｛４｝）＝｛４｝，　一ｃｌｏｓｕｒｅ（｛５｝）＝｛５｝Ｕ　ｓ—　ｃｌｏｓｕｒｅ（｛６｝），ｓ—ｃｌｏｓｕｒｅ（｛６｝）＝｛６｝ＬＪ　ｓ—　ｅｌｏｓＨｒｅ（｛１｝）Ｕ　ｓ—ｅｌｏｓＬｌｒｅ（｛７｝），ｓ—ｅｌｏｓＩｌｒｅ（｛７｝）：　｛７｝，占一ｅｌｏｓｉｌｒｅ（｛８｝）＝｛８｝，　—ｅｌｏｓＩｌｒｅ（｛９｝）：｛９｝，　ｓ—ｃｌｏｓｕｒｅ（｛１０｝）＝｛１０｝。　代人可得：ｓ—　ｃｌｏｓｕｒｅ（｛０｝）＝｛０，１，２，４，７｝，　一ｅ｜ＯＳｉｌｒｅ（｛１｝）＝｛１，　２，４｝，ｓ—ｃ］ｏｓｕｒｅ（｛２｝）：｛２｝，８一ｅｌｏｓｌｌｒｅ（｛３｝）：｛１，　２，３，４，６，７｝，８　一　ｅｌｏｓｌｌｒ￣（｛４｝）　＝　｛４｝，　一　ｅｌｏｓｌｌｒｅ（｛５｝）＝｛１，２，４，５，６，７｝，ｓ—ｃ｜ｏｓｌｌｒｅ（｛６｝）＝　｛１，２，４，６，７｛，ｓ　—　ｃ］ＯＳ／ｌｒｅ（｛７｝）　＝　｛７｝，８　一　

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

《基于子集构造法的优化的NFA确定化算法.doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

编译原理清华大学出版社第8章习题重点题解答 有限自动机的确定化算法子集法问题探析1 编译原理复习(有答案) 编译原理第4章答案 编译原理 编译原理考试知识点复习 编译原理复习题及答案 编译原理中子集法的教学探讨 编译原理-试题及答案(魏国利) 编译原理复习(有答案)
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号