woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

有限自动机的最小化算法

最小有限自动机,是指满足下述条件的确定有限自动机

没有无用状态(无用状态已删除) 没有等价状态(等价状态已合并)

.删除无用状态算法

【定义】无用状态是指自动机从开始态出发,对任何符号串都不能到达的状态。

【判别算法】 构造有用状态集 Qus

q0 为开始态,则 q0Qus

qiQus 且有 d(qi,a)= qj 则令 qjQus

重复执行,直到Qus不再增大为止。

从状态集Q中,删除不在Qus中的所有状态。

. 合并等价状态算法

【原理】两个状态i,j等价,当且仅当满足下面两个条件:

必须同是结束态,或同不是结束态;

对所有字母表上符号,状态i,j必变换到等价状态。

. 合并等价状态算法

划分不等价状态集

初始,把状态集Q化分成两个不等价子集:

Q1(结束状态集) Q2(非结束状态集)

把每个Qi再划分成不同的子集,条件是:

对同一Qi中两个状态ij,若对字母表中的某个符号,变换到已划分的不同的状态集中,则ij应分离:

d(i,a)Qm , d(j,a)Qn mn

重复步骤,直到再不能划分为止;

合并最终划分的每个子集中的各状态(合而为一)

 

posted on 2009-11-05 23:42 肥仔 阅读(1860) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理