第3章词法与有限自动机案例.ppt

  1. 1、本文档共98页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
4、确定有限自动机的化简 终态和非终态是可区别的。 (3)状态等价的条件 一致性条件:状态 s 和 t 必须同时为终态或非终态。 蔓延性条件:对于所有输入符号,状态 s 和 t 必须转化到等价的状态里。 等 价 4、确定有限自动机的化简 (4)DFA最小化的任务 确定有限自动机化简的任务是去掉多余状态,合并等价状态。多余状态是指从该自动机的开始状态出发,任何输入串也不能达到的状态,即从初态结点开始永远到达不了的那些状态。 (5)DFA最小化算法(子集分割算法) 基本思想 将DFA M中的状态集分割成一些互不相交的子集,使得任何不同的两个子集中的状态都是可区别的,而同一个子集中的任何两个状态都是等价的。 从每个子集中任选一个状态作为代表,同时消去其它等价状态及其射出的弧。 把那些原来到达其它等价状态的弧改为到达相应的代表状态。 (5)DFA最小化算法(子集分割算法) 具体步骤 初始分割:把状态集S划分为终态集和非终态集,记为 其中, 属于终态集, 属于非终态集。 k次分割:假定经过k次划分后, 得到m个子集, 记为 ,并且属于不同子集中的状态都是可区别的。检查 中的每个子 集 ,看其能否进一步分割。令 ,若存在一个输入字符a(a∈Σ),使得 不全包含在现行分割 的某一子集 中,就将 一分为二。 4、确定有限自动机的化简 分割办法: 假设当前子集 ,若状态q1和q2经a弧分别到达状态t1和t2,而t1和t2又分属于当前已划分出的两个不同子集 和 中,则此时应将 分为两半,使得一半含有q1,另一半含有q2。 4、确定有限自动机的化简 q1和q2不等价 t1和t2不等价 (5)DFA最小化算法(子集分割算法) 具体步骤 循环分割:重复上一步,直到子集个数不再增加为止(即每个子集已是不可再分的了)。所谓不能划分,是指该子集或者仅有一个状态,或者虽有多个状态但这些状态均不可区别(即等价)。 选代表,删除等价状态:对于最后分划 中的每一个子集,选取该子集中的一个状态代表其它等价状态。例如,状态子集I={q1,q2,…,qk},挑选q1作为子集I的代表,则凡导入到q2,…,qk的弧都改成导入到q1中,然后将q2,…,qk及其所射出的弧从原来的DFA中删除。 决定初态和终态:设删除等价状态之后的DFA为M′ ,凡那些包含M的初态的状态子集所对应的代表状态均作为M′的初态;凡那些包含M的终态的状态子集所对应的代表状态均作为M′ 的终态。则有L(M′ )=L(M)。 4、确定有限自动机的化简 4、确定有限自动机的化简 【例3.13】 对下图所示的DFA M进行化简。 解:①初始分割 将状态集S={0,1,2,3,4,5,6}划分为终态集{3,4,5,6}和非终态集{0,1,2}。 4、确定有限自动机的化简 ② 考察{3,4,5,6} 所以,{3,4,5,6}不再分割。 ③考察{0,1,2} 由于 ,所以,应将{0,1,2}分割为{0,2}和{1}。 至此,得到的全部分割子集为{3,4,5,6},{0,2}和{1}。 4、确定有限自动机的化简 ④考察{0,2} 所以,将{0,2}分割为{0}和{2}。 最后,得到的全部分割子集为{0},{1},{2},{3,4,5,6}。每个子集均不需再分割,即每个子集内的状态互相等价,任意不同两个子集中的状态都是可区别的。 4、确定有限自动机的化简 ⑤选代表,删除多余状态 令状态3代表{3,4,5,6},把原来导入4

文档评论(0)

1112111 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档