DFA最小化算法研究  

Research on the Algorithm for Minimizing DFA

作　　者：周时阳[1] 祝建华[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《计算机工程与科学》2007年第3期60-62,共3页Computer Engineering & Science

摘　　要：本文指出了现有DFA最小化算法的缺陷,并给出使用这些算法对DFA限制条件以及将不满足限制条件DFA等价转换成满足限制条件的DFA一般方法;在研究状态等价的充分条件基础上,提出了一种新的适用任何DFA的最小化算法及其算法的正确性证明。The paper points out the disadvantages of the algorithm for minimizing DFA,gives the restriction of using this algorithm,and the common method by which a DFA which does not satisfy the restriction can be transformed equivalently to a DFA which satisfies the restriction.Based on a study of the sufficient conditions of state equivalence,a brand-new algorithm of minimizing DFA that can be applied to any DFA is proposed,also the proof of the accuracy of this algorithm is provided.

关 键 词：DFA 算法 最小化 

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