有限自动机最小化算法的实现

• 作者: 韩光辉
• 来源期刊: 武汉商业服务学院学报
• 学科: 工学
• 关键词: 有限自动机 等价最小有限自动机 等价关系 商集 划分
• 年，卷（期）: 2006,（1）
• 所属期刊栏目: 应用研究
• 页码范围: 60-62
• 页数: 3页
• 分类号: TP301.1
• 字数: 2338字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-2277.2006.01.017

摘要

实现DFA M=(Q,∑,δ,qo,F)最小化算法的关键问题是如何编程求取商集Q/Rk(即状态的k阶区分).本文引入等价关系Sk与商集Q/Sk(状态的严格k阶区分),证明了Rk=Rk-1 ∩ Sk,因此Q/Rk是Q/Rk-1中等价类与Q/Sk中等价类的非空交集全体.为了求取Q/Sk,引入Q的子集Hk,利用集合的交、差运算可由Hk求取Q/Sk,从而仅利用集合运算便可求取Q/Rk.基于上述讨论,给出了DFA最小化算法的一个容易实现的构造性描述.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	韩光辉		25	81	6.0	8.0