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

摘要：

实现DFAM=(Q,Σ,δ,q0,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最小化算法的一个容易实现的构造性描述及示例.

关键词： 有限自动机 等价关系 商集 最小化算法 集合运算

作者: 韩光辉 段国丽

作者单位: 武汉商业服务学院教育技术中心,湖北,武汉,430056 江汉大学,数学与计算机科学学院,湖北,武汉,430056

会议类型: 国内会议

会议名称: 湖北省机械工程学会设计与传动专业委员会2006年学术年会

会议地点: 武汉

会议语种:中文

页码: 69-71

在线出版日期: 2006-10-01（万方平台首次上网日期，不代表论文的发表时间）