好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

编译原理DFA化简与正则文法.ppt

46页
  • 卖家[上传人]:宝路
  • 文档编号:47992376
  • 上传时间:2018-07-08
  • 文档格式:PPT
  • 文档大小:2.87MB
  • / 46 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 上节回顾1、DFA和NFA2、NFA确定化为DFAn(1)、使初态和终态均唯一;n(2)、使NFA的每个箭弧上或为单个字符,或为ε;n(3)、NFA中,∑={a1, …, ak}, 将NFA确定化:n (a)、构造一张含有k+1列的表,置该表首行首列为ε_Closure(X);n (b)、若某一行第一列已确定,则置第i+1列为Iai,若该行某列未在该表第 一列出现过,就将其加入到该表第一列最后一行;n (c)、重复上述过程,直至出现在第i+1列上的所有状态子集均在第一列上 出现过;n (d)、将每个状态子集合并为一个状态,根据得到的状态转换矩阵构造 DFAn(4)、DFA的初态为首行首列的状态,终态为那些含有原终态的状态子集遗留问题021ab4b6 a021ab3b21a21a4 b3a5b456ba356ab34563012 baabbaab1、DFA是否可化简? 2、如何化简?3、怎样才是最简DFA?有四个终态只有一个终态DFA M化简的目标v 寻找一个状态数比M少的DFA M’,使得 L(M)=L(M’) v 最终目标是找到状态最少的那个M’。

      无关状态10124baaab3aa56ab多余状态如何删除多余状态? (1)寻找没有从其它状态连接的输入弧 的状态,把它及其连接的弧去掉; (2)将孤立的TG去掉无关状态202341baaaba56aab死状态如何删除死状态? (1)寻找没有连接到其它状态的弧的 状态(组),将该状态(组)及其弧去掉; (2)重复(1),直到找不到为止多余状态和死状态都称为无关状态3.2.7 DFA化简等价状态和可区别状态0123abbb等价状态:s和t是等价的,如果 从s出发能读出某个字w而停在终 态,那么同样从t出发也能读出同 样的字w而停在终态;反之,若 从t出发能读出某个字w而停在终 态,那么同样从s出发也能读出 同样的字w而停在终态b013ab如果s与t不等价,则称这两 个状态是可区别的等价状态的情况v 若u、v通过所有a弧可以到达的状态等价,那么u、v等价若u、v通过a分别到达s、t: 若u能接受aw,则s、t必能接受w,v必可接受aw; 若v能接受aw,则t、s必能接受w, u必可接受awaus Yawtwv到达终态时,终态是可接收空 串的,非终态不可以可区别状态的情况0123abbb(1) 终态和非终态是可区别的;(2) 有a弧的和没有a弧的状态可区别的;有a弧的状态可以接受部分以a 为首的字,而没有a弧的状态 一定不能接受以a为首的字。

      因为s和t可区别,必存在字w,或者 s可接受,t不可接受;或者t可接受 而s不可接受 那么对于字aw,或者u可接受v不可 接受;或者v可接受而u不可接受3) 若us, vt, 若s、t可区别,则u、v 可区别aausvtaa(4) u有a弧到达s,对s的任意等价状态t,v 均没有a弧到达,则u, v可区别假设u、v等价,若s可接受字w,则u、v 可接受字aw,v通过a弧到达的状态必能 接受w;反之,若v通过a弧到达的状态 能接受字w,则u、v可接受aw,s可接受 w这样v通过a弧达到的状态与s等价, 矛盾状态集划分0123abbb(1) 终态和非终态是可区别的;(2) 有a弧的和没有a弧的状态可区别的;(3) 若us, vt, 若s、t可区别,则u、v 可区别aa(1) 终态和非终态是可区别的;(2) 1、2有b弧到达3,0没有4) u有a弧到达s,t是s的等价状态,v没有 到达t的a弧,则u, v可区别DFA化简DFA M=(S, Σ, f, S0, Z),状态子集划分算法:(2) 将S的终态和非终态分开,形成基本划分Π={S-Z, Z},Π中属于两个不 同子集状态是可区别的;(1) 消除无关状态;(3) 若某一时刻Π={I(1), I(2), …, I(m)},且属于不同子集的状态是可区别的, 检查每个I(k)是否能进一步划分:对任意字符a,若I(k)中有状态s1和s2经a弧分别到达t1和t2,且t1和t2属于Π 的不同子集,则将I(k)一分为二:I(k1)={s|s∈I(k)且s经a弧到达t1所在子集中的状态}I(k2)=I(k)-I(k1) (4) 重复执行(3),直到Π中的每个子集都不能再划分为止;(5) 合并等价状态。

      例:将下面的DFA化简021ab4b6 a021ab3b21a21a4 b3a5b456ba356ab3456(1) 消除无关状态2) 初次划分: Π0={{0,1,2}, {3,4,5,6}} (3) 考察{0,1,2}:f(0,a)=1∈{0,1,2};f(1,a)=3∈{3,4,5,6};f(2,a)=1∈{0,1,2};Π1={{0,2},{1},{3,4,5,6} } (4) 考察{0,2}:f(0,b)=2∈{0,2}; f(2,b)=4∈{3,4,5,6};Π2={{0}, {2}, {1}, {3,4,5,6}}021ab4b6 a021ab3b21a21a4 b3a5b456ba356ab3456(4)Π2={{0}, {2}, {1}, {3,4,5,6}}(5) 考察{3,4,5,6}: f(3,a)=3∈{3,4,5,6}; f(4,a)=6∈{3,4,5,6};f(5,a)=6∈{3,4,5,6};f(6,a)=3∈{3,4,5,6};f(3,b)=5∈{3,4,5,6}; f(4,b)=4∈{3,4,5,6}; f(5,b)=4∈{3,4,5,6}; f(6,b)=5∈{3,4,5,6};最后划分:Π3={{0}, {2}, {1}, {3,4,5,6}}例:将下面的DFA化简021ab4b6 a021ab3b21a21a4 b3a5b456ba356ab3456(6) 根据最后划分:Π3={{0}, {2}, {1}, {3,4,5,6}},合并等价状态。

      0123aaaabbbb(7) 确定初态和终态例:将下面的DFA化简合并状态后创建关系的原则两个状态集之间:S={s1,s2,…,sm}, T={t1,t2,…,tn}s1s2s3smt1t2t3tnaaa a(1) 从si到tj全部有a弧:从S到T引a弧STa(2) 部分si到tj有a弧,部分没有:s1s2s3smt1t2t3tnaa说明S可划分s1s2s3smt1t2t3tns1s2s3smt1t2t3tnaaaa(3) 全部si到部分tj有a弧,到部分tj没有:从S到T引a弧(4) 从si到tj全部没有a弧:ST从S到T没有a弧合并状态后创建关系的原则两个状态:S={s1,s2,…,sm}, T={t1,t2,…,tn}(1) 从si到tj全部有a弧:从S到T引a弧;(2) 部分si到tj有a弧,部分没有:说明S可划分;(3) 全部si到部分tj有a弧,到部分tj没有:从S到T引a弧;(4) 从si到tj全部没有a弧:S到T没有a弧S=T的情况:(1) 从si到sj全部有a弧:从S到自身引a弧;(2) 部分si到sj有a弧,部分没有:说明S可划分;(3) 全部si到部分sj有a弧,到部分sj没有:从S到自身引a弧;(4) 从si到sj全部没有a弧:S到自身没有a弧。

      例DFA化简(1) 消除无关状态;(2) 首次划分:Π0={{1,2,4,5,6,7}, {0,3}}015601120140101701010103(3) 考察{1,2,4,5,6,7},由0弧:{ }, { }(3) 考察{1,2,4,5,6,7},由0弧:{1 }, { }(3) 考察{1,2,4,5,6,7},由0弧:{1 }, {2 }(3) 考察{1,2,4,5,6,7},由0弧:{1 }, {2,4 }(3) 考察{1,2,4,5,6,7},由0弧:{1 }, {2,4,5 }(3) 考察{1,2,4,5,6,7},由0弧:{1,6 }, {2,4,5 }(3) 考察{1,2,4,5,6,7},由0弧:{1,6 }, {2,4,5,7 }故:Π1={{1,6},{2,4,5,7}, {0,3}}(4)考察{1,6},不能划分。

      5)考察{2,4,5,7}, Π2={{1,6}, {2,5}, {4,7}, {0,3}}例DFA化简(6)最终划分: Π={{1,6}, {2,5}, {4,7}, {0,3}}0156011201401017010101032,54,71,60,301010101例DFA化简0210131001405100110(1) 消除无关状态;(2) 首次划分:Π0={{0}, {1,2,3,4,5}}(3) 考察{1,2,3,4,5},由0弧:Π1={{0} , {1,5}, {2,3,4}}(4) 考察{1,5}:{1,5}0{0}, {1,5}1{3}, 不能划分:Π2={{0} , {1,5}, {2,3,4}}(5) 考察{2,3,4},由0弧不能划分;由1弧: {2,4}, {3}Π3={{0} , {1,5}, {2, 4} ,{3}}例DFA化简0210131001405100110(6) 考察{2,4}:{2,4}0{3}, {2,4}1{0}, 不能划分(7) 最终得到:{0}, {1,5}, {2,4}, {3}(5) Π3={{0} , {1,5}, {2, 4} ,{3}}例DFA化简0210131001405100110根据最终划分构造DFA:{0}, {1,5}, {2,4}, {3}2,431,5010010101前期内容回顾1、一个语言可以用正规式描述;2、正规式容易构造出NFA进行描述;3、NFA可以确定化为DFA,而DFA编程实现无回溯;4、DFA可以进一步化简以减少状态数量,进一步简化程序编制;每个NFA是否也可以用正规式描述?如何转换?ijABijA|BijSA*TijA kBijABijS kT A使NFA的弧上仅含单个输入字符或ε的过程是逐步分解的过程 ;NFA构造正规式的过程是逐步合并的过程。

      3.3 NFA M构造正规式 R例:NFA M转换为正规式 R,使 L(R)=L(M)03142a,baaa,bbba,bY4ε 2ε 03142a|baabbY4ε 2ε a|ba|b例:NFA M转换为正规式 R,使L(R)=L(M)031a|babYa4ε a|bb2ε a|baY4ε a|ba(a|b)* 1bY2ε a|bb(a|b)*例:NFA M转换为正规式R,使L(R)=L(M)0a|bY3aa(a|b)* 1bb(a|b)*3aYa(a|b)*0aa(a|b)*01bYb(a|b)*bb(a|b)*例:NFA M转换为正规式R,使L(R)=L(M)0a|bYaa(a|b)*bb(a|b)*(aa(a|b)*) | (bb(a|b)*)0Yaa(a|b)*bb(a|b)*例:NFA M转换为正规式R,使L(R)=L(M)0a|bY(aa(a|b)*) | (bb(a|b)*)(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*0a|bY(aa|bb)(a|b)*R= (a|b)*(aa|bb)(a|b)*正则文法(3型文法)v 正则文法的产生式形式为:AαB或Aβ 或者ABα或 Aβ, 其中A,B∈VN,α∈VT , β∈VT∪{ε}o单词既可用正则文法表示,也可用正规式表示。

      o正则文法、正规式、DFA、NFA是等价的正规式FA正则文法FA正则文法正规式3.4.1 正则文法转换为FA文法G[A]:AaA, Aa, AbB, 。

      点击阅读更多内容
      相关文档
      【课件】有理数的加法(第二课时)课件 2024—2025学年人教版数学七年级上册.pptx 【课件】有理数的减法(第二课时)课件 2024—2025学年人教版数学七年级上册.pptx 【统编版】高中语文必修上册第二单元《4心有一团火温暖众人心》优质课(29张PPT)课件.pptx 【统编版】高中语文必修上册第一单元 3铁凝《哦香雪》上课课件(27张PPT)课件.pptx 【统编版】高一语文必修上册4-1《喜看稻菽千重浪—袁隆平》优质课(29张PPT)课件.pptx 【统编版】高中语文必修上册第二单元《4喜看稻菽千重浪》公开课(33张PPT)课件.pptx 【统编版】高中语文必修上册第一单元 3铁凝《哦香雪》原创课件(35张PPT)课件.pptx 【统编版】高中语文必修上册第一单元 3铁凝《哦香雪》优秀课件(25张PPT)课件.pptx 【新教材】高中语文部编版必修上册第二单元《4心有一团火温暖众人心》优秀课件(46张PPT)课件.pptx 【统编版】高一语文必修上册第4课《喜看稻菽千重浪—袁隆平》精品课(28张PPT)课件.pptx 【统编版】高中语文必修上册第二单元《4心有一团火温暖众人心》优质课(21张PPT)课件.pptx 【统编版】高一语文必修上册第4课《喜看稻菽千重浪—袁隆平》公开课(28张PPT)课件.pptx 【系列】高一(46)班《最强大脑 解密记忆——学习方法类》主题班会(18张PPT)课件.pptx 【统编版】高中语文必修上册第一单元 3铁凝《哦香雪》精美课件(33张PPT)课件.pptx 【新教材】高中语文部编版必修上册第二单元《4心有一团火温暖众人心》公开课(30张PPT)课件.pptx A0002【统编版】2025年高一语文秋季开学第一课《“语”你相遇遇见美好》公开课 (31张PPT)课件.pptx 苏科版(2024)新教材九年级物理上册第十二章《第1节 机械能》精品课件.pptx 苏科版(2024)新教材九年级物理上册第十一章《第3节 功》精品课件.pptx 享受青春拒绝早恋+主题班会说课课件.pptx 人教版(2024)新教材九年级物理全一册第十五章《第3节 串联电路和并联电路》精品课件.pptx
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.