一个完善的基于判定链表的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 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最小化方法中只处理无互相依赖等价状态会造成最小化结果不正确.针对此问题,分析了DFA中状态的k次传递等价、含自回路状态的等价以及互相依赖等价等结构特点,将分析结果应用于DFA最小化算法中,提出了一个完善的基于判定链表的DFA最小化算法.该算法涵盖所有等价状态的链表处理,与传统的分割或合并算法的最小化结果一致,保证了基于判定链表的最小化结果的正确性.