基于简单路径上的识别字实现DFA的最小化

• 作者: 杨思春
• 来源期刊: 微机发展
• 学科: 工学
• 关键词: 自动机 DFA 最小化 等价类 简单路径
• 年，卷（期）: 2005,（4）
• 所属期刊栏目: 智能与算法研究
• 页码范围: 19-20,23
• 页数: 3页
• 分类号: TP301.6
• 字数: 2126字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2005.04.007

摘要

DFA最小化的关键在于给出状态集合中所有的等价类.根据状态等价的定义,若能求出每一状态在其所有识别路径上的识别字,则通过比较这些状态的识别字,就可获得状态集合中所有的等价类.现有文献中并未采用这一方法,原因是对于某些状态,可能存在一些较为复杂的识别路径,若按这些路径逐一求出对应的识别字,则有一定的难度.文中基于识别路径中的简单路径,给出一种基于简单路径上的识别字实现DFA最小化的算法.该算法可作为现有算法的一个有益补充.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨思春	安徽工业大学计算机系	71	416	11.0	17.0