一个完善的基于判定链表的DFA最小化算法  

Perfect state-judging list based minimization algorithm for DFA

作　　者：陈矗[1] 任平红[1] 禹继国[1] 马炳先[2] 

机构地区：[1]曲阜师范大学计算机科学学院,山东日照276826 [2]济南大学信息科学与工程学院,济南250022

出　　处：《计算机工程与应用》2013年第6期48-51,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60903099);山东省自然科学基金(No.ZR2012FM023)

摘　　要：应用判定链表进行DFA最小化方法中只处理无互相依赖等价状态会造成最小化结果不正确。针对此问题,分析了DFA中状态的k次传递等价、含自回路状态的等价以及互相依赖等价等结构特点,将分析结果应用于DFA最小化算法中,提出了一个完善的基于判定链表的DFA最小化算法。该算法涵盖所有等价状态的链表处理,与传统的分割或合并算法的最小化结果一致,保证了基于判定链表的最小化结果的正确性。Sometimes the minimization result of DFA is not correct by using the state-judging list method for it can only deal with equivalent states without inter-dependency. To solve this problem, the structural characteristics of DFA are analyzed includ- ing k transition equivalence, state＇ s equivalence with self-loop and inter-dependent equivalence. The structural characteristics are applied to minimization of DFA. So a perfect state-judging list based minimization algorithm is put forward. The algorithm covers all equivalent structures and outputs the same result with classic partition or combination algorithms which also shows rightness of the algorithm.

关 键 词：判定链表 确定有限状态自动机(DFA) 最小化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]