计算机工程与应用2013，Vol.49Issue(6)：48-51,4.DOI:10.3778/j.issn.1002-8331.1209-0311
一个完善的基于判定链表的DFA最小化算法
Perfect state-judging list based minimization algorithm for DFA
摘要
Abstract
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 including 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 Tightness of the algorithm.关键词
判定链表/确定有限状态自动机(DFA)/最小化Key words
state-judging list/ Deterministic Finite states Automata (DFA)/ minimization分类
信息技术与安全科学引用本文复制引用
陈矗,任平红,禹继国,马炳先..一个完善的基于判定链表的DFA最小化算法[J].计算机工程与应用,2013,49(6):48-51,4.基金项目
国家自然科学基金(No.60903099) （No.60903099）
山东省自然科学基金(No.ZR2012FM023). （No.ZR2012FM023）
