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

• 作者: 任平红 禹继国 陈矗 马炳先
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 判定链表 确定有限状态自动机(DFA) 最小化
• 年，卷（期）: 2013,（6）
• 所属期刊栏目: 理论研究、研发设计
• 页码范围: 48-51
• 页数: 4页
• 分类号: TP391
• 字数: 5539字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1209-0311

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	禹继国	曲阜师范大学计算机科学学院	87	351	11.0	15.0
2	马炳先	济南大学信息科学与工程学院	7	65	5.0	7.0
3	任平红	曲阜师范大学计算机科学学院	14	49	3.0	7.0
4	陈矗	曲阜师范大学计算机科学学院	12	35	3.0	5.0