《形式语言与自动机》课件ch3.7-3.8.ppt
《《形式语言与自动机》课件ch3.7-3.8.ppt》由会员分享,可在线阅读,更多相关《《形式语言与自动机》课件ch3.7-3.8.ppt(21页珍藏版)》请在文库网上搜索。
1、12023/6/7School of Computer Science,BUPT3.7 正则表达式与有限自动机的关系结论:有有限限自自动机机、右右(左左)线性性文文法法、正正则表表达式都定达式都定义了同一种了同一种语言言-正正则语言言.证明策略明策略 -NFANFADFARERE(Regular Expression)-正则表达式22023/6/7School of Computer Science,BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式(状态消去法)(状态消去法)思路思路:(1)扩展自动机的概念,允许正则表达式作为转移弧的标记。这样,就有可能在消去某一中间状态时,保证
2、自动机能够接受的字符串集合保持不变。(2)在消去某一中间状态时,与其相关的转移弧也将同时消去,所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补。以下分别介绍中间状态的消去与正则表达式构造过程。32023/6/7School of Computer Science,BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式(中间状态的消去)(中间状态的消去)xy r1r2xz r1y r2代之以:xy r1+r2xyr2r1代之以:xy r1*xz y r1代之以:42023/6/7School of Computer Science,BUPT从从 DFA 构造等价的
3、构造等价的正则表达式正则表达式(中间状态的消去)(中间状态的消去)q1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去消去s52023/6/7School of Computer Science,BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式(状态消去法)(状态消去法)步骤步骤:(1)对对每每一一终终态态q,依依次次消消去去除除q 和和初初态态q0 之之外外的的其其它它状状态态;(2)若若q q0,最终可得到一般最终可得到一般形式如下左图形式如下左图的状态自动机,的状态自动机
4、,该自动机对应的正则表达式可表示为该自动机对应的正则表达式可表示为 (R+SU*T)*SU*.(3)若若q=q0,最终可得到最终可得到如下右图的自动机,它对应的正则如下右图的自动机,它对应的正则 表达式可以表示为表达式可以表示为 R*.(4)最终最终的正则表达式为的正则表达式为每一终态对应的每一终态对应的正则表达式之和(并)正则表达式之和(并).62023/6/7School of Computer Science,BUPT状态消去法举例状态消去法举例对于终态对于终态C对于终态对于终态D等价的正则表达式等价的正则表达式(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)72023/6/
5、7School of Computer Science,BUPT状态消去法举例状态消去法举例01342567 a b aa b b a b012567a+ba+b aabb0257(a+b)*(a+b)*aa+bb07(a+b)*(aa+bb)(a+b)*82023/6/7School of Computer Science,BUPT定定理理:L 是是正正则表表达达式式R 表表示示的的语言言,则存存在在一一个个 -NFA E,满足足L(E)=L(R)=L.证明明:构构造造性性证明明.可可以以通通过结构构归纳法法证明明从从R 可可以以构造出与其等价的,构造出与其等价的,满足如下条件的足如下条件的
6、 -NFA:(1)恰好一个恰好一个终态;(2)没有弧没有弧进入初入初态;(3)没有弧离开没有弧离开终态;从从正则表达式正则表达式构造等价的构造等价的 -NFA92023/6/7School of Computer Science,BUPT基础基础:从从正则表达式正则表达式构造等价的构造等价的 -NFA(归纳归纳构造过程)构造过程)1 对于对于 ,构造构造为为 3 对于对于a,构造为构造为a2 对于对于 ,构造构造为为102023/6/7School of Computer Science,BUPT归纳归纳:从从正则表达式正则表达式构造等价的构造等价的 -NFA(归纳归纳构造过程)构造过程)1
7、对于对于R+S,构造为构造为 112023/6/7School of Computer Science,BUPT归纳归纳:从从正则表达式正则表达式构造等价的构造等价的 -NFA(归纳归纳构造过程)构造过程)2 对于对于RS,构造为构造为 3 对于对于R*,构造构造为为 122023/6/7School of Computer Science,BUPT举举例例:设设正正则则表表达达式式 1*0(0+1)*,构构造造等等价价的的 -NFA.从从正则表达式正则表达式构造等价的构造等价的 -NFA0+1 1*132023/6/7School of Computer Science,BUPT从从正则表达
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言与自动机 形式语言 自动机 课件 ch3 3.8