关键词: 判定链表, 确定有限状态自动机（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 rightness of the algorithm.

Key words: state-judging list, Deterministic Finite states Automata（DFA）, minimization