基于信息系统的确定有限自动机最小化算法  

Algorithm for minimizing determination finite automation based on information system

作　　者：杨传健[1] 葛浩[2] 姚光顺[1] 王波[2] 

机构地区：[1]滁州学院计算机与信息工程学院,安徽滁州239012 [2]滁州学院机械与电子工程学院,安徽滁州239012

出　　处：《计算机应用》2012年第7期1991-1993,1997,共4页journal of Computer Applications

基　　金：安徽高等学校省级自然科学研究项目(KJ2011Z276;KJ2012A212);安徽省高等学校省级优秀青年人才基金资助项目(2011SQRL123;2012SQRL151);滁州学院科学研究项目(2010kj014B;2011kj003Z;2011kj017B)

摘　　要：目前,确定有限自动机(DFA)最小化问题多侧重于理论研究,尚无太多便于实现的算法,为此,对确定有限自动机最小化方法进行了研究,提出将DFA转换为信息系统,基于等价类划分方法简化信息系统,再将简化的信息系统转换为最小化DFA;针对上述处理过程,给出一个基于分治思想的DFA最小化算法,在平均情况下该算法的时间复杂度为O(n log n),空间复杂度为O(n)。最后通过实例验证了所提算法的正确性。At present,Determination Finite Automation（DFA） minimization more focuses on theoretical research,and there are not many algorithms easy to achieve.Therefore,the method of minimization of determination finite automation was researched.First,DFA was converted into information system;and then the information system was simplified,which was based on the partition of equivalence classes;at last the simplified information system was converted into minimized DFA.Concerning the above process,an algorithm of minimizing DFA based on strategy of divide and conquer was proposed.In the average case,the time complexity and space complexity of the algorithm are O（n log n） and O（n） respectively.Finally,an example was used to explain the feasibility of the proposed algorithm.

关 键 词：确定有限自动机 信息系统 等价类 最小化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]