《形式语言与自动机》课件ch3.4-3.6.ppt
《《形式语言与自动机》课件ch3.4-3.6.ppt》由会员分享,可在线阅读,更多相关《《形式语言与自动机》课件ch3.4-3.6.ppt(37页珍藏版)》请在文库网上搜索。
1、12023/6/7School of Computer Science,BUPT第四节第四节有有 转换的转换的NFAn一、定一、定义概念:当概念:当输入空串入空串(无无输入入)时,也能引,也能引起状起状态的的转移。移。例:输入入“002”时的的转移格局:移格局:q0q1q201222023/6/7School of Computer Science,BUPT -NFA 的形式定义的形式定义 一个一个 -NFA 是一个五元组是一个五元组A=(Q,T,q0,F).有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合q0 Q F Q
2、 与与 NFA 的不同之处的不同之处 :Q (T )2Q32023/6/7School of Computer Science,BUPT -NFA 如何接受输入符号串如何接受输入符号串q1q0q2q3q5 ,+,q4 该该 -NFA 可以接受的字符串如:可以接受的字符串如:3.14+.314 314.42023/6/7School of Computer Science,BUPT二、二、-闭包(闭包(closure)概念概念 状态状态q的的-闭包闭包,记为,记为 -CLOSURE或或ECLOSE,定义为从,定义为从 q经所有的经所有的 路径可以到达路径可以到达的状态(包括的状态(包括q自身),
3、自身),如:如:q0q1q2012 -CLOSURE(q0)=q0,q1,q2 -CLOSURE(q1)=q1,q2 -CLOSURE(q2)=q2 52023/6/7School of Computer Science,BUPT状状态子集子集I I 的的-闭包:包:-CLOSURE(I)-CLOSURE(q)q I例:例:-CLOSURE(q1,q2)-CLOSURE(q1)-CLOSURE(q2)q1,q2nIa Ia 概念:概念:对于状态子集对于状态子集I Q,任意任意aT,定义定义Ia如下:如下:Ia=-Closure(P)其中其中P=(I,a).即即P是从是从I中的状中的状态经过一条
4、一条标a的的边可以到达的状可以到达的状态集合集合62023/6/7School of Computer Science,BUPT例:例:I Iq0q0,q1q1,求求I I1 1I I1 1 -CLOSURE-CLOSURE(I I,1 1)-CLOSURE-CLOSURE(q0q0,q1q1,1 1)-CLOSURE-CLOSURE(q1 q1)q1q1,q2q2q0q1q201272023/6/7School of Computer Science,BUPT扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串 设一个设一个 -NFA,:Q T 2Q 扩充定义扩充定义 :Q T*2Q 对
5、任何对任何q Q,定义:定义:1 (q,)=ECLOSE(q)2(q,a)-CLOSURE(P)其中其中P p|存在存在r(q,)p(r,a)注意:注意:此时此时(q,a)(q,a),因为因为(q,a)表示由表示由q出发,只沿着标出发,只沿着标a 的路径所能到达的状态,的路径所能到达的状态,而而(q,a)表表示示由由q出出发发,沿沿着着标标a(包包括括转转换换在在内内)的的路路径径所所能能到到达的状态达的状态.82023/6/7School of Computer Science,BUPT-NFA中,中,与与函数的不同函数的不同 举例举例 计算计算 (q0,a)(q0,)-CLOSURE(q0
6、)q0,q2(q0,a)-CLOSURE(q0,),a)-CLOSURE(q0,q2,a)-CLOSURE(q0,a)(q2,a)-CLOSURE(q1 q3)q1,q2 q3q1,q2,q3同理:同理:(q0,aa)q3-CLOSURE(q0)q0,q2-CLOSURE(q1)q1,q2-CLOSURE(q2)q2-CLOSURE(q3)q392023/6/7School of Computer Science,BUPT三、三、-NFA 的的 语语 言言 设一个设一个 -NFA M=(Q,T,q0,F)定义定义M 的语言:的语言:L(M)=|(q0,)F 即即 满足满足(q0,)含有含有F的
7、一个状态的一个状态 102023/6/7School of Computer Science,BUPT四、有四、有 转换的转换的NFA与无与无 转换的转换的NFA的等价的等价1.-NFANFA具具有有转转移移的的NFA是是不不具具转转移移的的NFA的的一一般般情况,所以只要情况,所以只要证证明下面的定理即可:明下面的定理即可:定定理理:如如果果L被被一一个个具具有有 转转移移的的NFA接接收收,那么那么L可被一个不具可被一个不具 转转移的移的NFA接收。接收。证证明明思思路路:构构造造一一个个不不具具 转转移移的的NFA,证明明其其接收具有接收具有 转转移的移的NFA所接受的所接受的语语言。言
8、。112023/6/7School of Computer Science,BUPT从从 -NFA 构造等价的构造等价的 无无 NFA设M=(Q,T,q0,F)是是一一个个-NFA,可可构构造造一一个个无无 的的NFAM1=(Q,T,1,q0,F1),对任何任何a T,1(q,a)=(q,a)。(注意(注意与与的区的区别别与与联联系。而系。而1和和是相等的。)是相等的。)F1 F q0若若-CLOSURE(q0)F F否否则122023/6/7School of Computer Science,BUPT从从 -NFA 构造等价的构造等价的 无无 NFA证明明:采用归纳法证明采用归纳法证明1(
9、q0,)(q0,),),|=1|=1。当当|w|=0,即即 w=时,不一定相等,不一定相等.1(q0,)q0,而而(q0,)-CLOSURE(q0)因此,从因此,从|1开始开始证明明 1.当当|=1时,定,定义相等。相等。由由1定定义 1(q0,a)(q0,a)132023/6/7School of Computer Science,BUPT设当当|=n时,1(q0,)=(q0,),),则当当|a|=n+1时,左左侧 1(q0,a)1(1(q0,),),a)1((q0,),),a)由由归纳假假设1(R,a)设R(q0,)1(q,a)q R (q,a)q R.由由1定定义(R,a)((q0,),
10、),a)R(q0,)(q0,a)右右侧再再证:1(q0,)含含F1的的一一个个状状态当当且且仅当当(q0,)含含F的的一个状一个状态 (略)(略)142023/6/7School of Computer Science,BUPT证证明同明同时时展示了一种将展示了一种将-NFA转转化化为为NFA的方法的方法.-NFANFADFA例:将将-NFA转换为转换为NFA.(图3.4.1,3.4.3)q0q1q2012q0q1q20120,11,20,1,2152023/6/7School of Computer Science,BUPT举例举例q1q0q2q3q5 ,+,q4q0 q1q1 q4q2q2
11、 q3 q5q3 q5162023/6/7School of Computer Science,BUPT第五节正则集和正则式正则集:正则集:字母表上一些特殊形式的字符串的集合,字母表上一些特殊形式的字符串的集合,是正则式所表示的集合。是正则式所表示的集合。正则式正则式:用类似代数表达式的方法表示正则语言。:用类似代数表达式的方法表示正则语言。运算运算:作用于语言上的三种代数运算作用于语言上的三种代数运算-联合联合(union)-连接连接(concatenation)-(星)星)闭包闭包(closure)172023/6/7School of Computer Science,BUPT正则表达式
12、(正则表达式(regular expression)归纳定义归纳定义正则表达式正则表达式如下:如下:基基础:,a(a T)都是正都是正则式式(原子正原子正则式式),相相应的正的正则集集为,a归纳:如果如果A和和B是正是正则式,且分式,且分别代表集合代表集合L(A)和和L(B),则(A+B),(A.B),A*也是正也是正则式,分式,分别表示以下正表示以下正则集:集:L(A)L(B)(语言言A/语言言B的串的串)L(A).L(B)(两个两个语言中的串的言中的串的连接接)L(A)*(语言言A中的串的多次中的串的多次连接接)仅通过有限次使用以上两步定义的表达式,才是字母表T上的正则式。这些正则式所表示
13、的字符串集合是T上的正则集。182023/6/7School of Computer Science,BUPT正则表达式算符优先级正则表达式算符优先级算符优先级(算符优先级(precedence)依次为依次为-(closure)-连接连接(concatenation)-(union)定义:若两个正则式表示相同的正则集,则称这两个正则式相等。即 R1R2 L(R1)=L(R2)注1:正则集是T*的子集。注2:L+包含当且仅当L包含。注3:每个正则集至少对应一个正则式(可有无穷多个正则式)192023/6/7School of Computer Science,BUPT正则表达式举例正则表达式举例
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言与自动机 形式语言 自动机 课件 ch3 3.6