一种新的DFA状态最小化算法

• 作者: 孟晨 王成 范书义
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 确定有穷自动机(DFA) 状态最小化 状态转换矩阵
• 年，卷（期）: 2012,（1）
• 所属期刊栏目: 研究、探讨
• 页码范围: 47-48,67
• 分类号: TP391
• 字数: 3905字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2012.01.014

摘要

提出了一种基于状态转换矩阵的适合计算机实现的DFA状态最小化算法,在计算等价状态过程中,通过记录扫描过程中发现的具有相同输入字符和相同转换状态的状态判定链表,算法可以用一遍扫描和与传统算法相近的存储空间实现DFA状态的最小化.与传统的DFA状态最小化算法相比,该算法具有较好的时间复杂度和相同的空间复杂度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王成	军械工程学院导弹工程系	73	378	10.0	15.0
2	孟晨	军械工程学院导弹工程系	164	1365	19.0	27.0
3	范书义	军械工程学院导弹工程系	20	77	5.0	8.0