计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (6): 48-51.

• 理论研究、研发设计 • 上一篇    下一篇

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

陈  矗1,任平红1,禹继国1,马炳先2   

  1. 1.曲阜师范大学 计算机科学学院,山东 日照 276826
    2.济南大学 信息科学与工程学院,济南 250022
  • 出版日期:2013-03-15 发布日期:2013-03-14

Perfect state-judging list based minimization algorithm for DFA

CHEN Chu1, REN Pinghong1, YU Jiguo1, MA Bingxian2   

  1. 1.College of Computer Science, Qufu Normal University, Rizhao, Shandong 276826, China
    2.College of Information Science and Engineering, Jinan University, Jinan 250022, China
  • Online:2013-03-15 Published:2013-03-14

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

关键词: 判定链表, 确定有限状态自动机(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