确定型格值有限自动机的最小化

• 作者: 李斌 舒兰
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 格半群 确定型有限状态自动机 等价关系 商集 最小化 最小化算法
• 年，卷（期）: 2010,（32）
• 页码范围: 52-54
• 分类号: O235|TP23
• 字数: 3862字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.32.014

摘要

给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义.指出了求取DLFAM=(Q,∑,δ,q0,σ)的实质是求取Q/Rk.由此以可到达状态为基础引入了等价关系Rk、Sk与商集Q/Sk,证明了Rk=Rk-1∩Sk,由此得到Q/Rk的等价类为Q/Rk-1中等价类与Q/Sk中等价类的非空交集全体.引入了Hk,并证明了可由Hk求取Q/Sk,从而得到仅利用集合运算便可求取Q/Rk的算法,最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李斌	电子科技大学应用数学学院	67	362	11.0	15.0
2	舒兰	电子科技大学应用数学学院	62	288	10.0	12.0