《形式语言与自动机》课件ch4.6-4.7.ppt
《《形式语言与自动机》课件ch4.6-4.7.ppt》由会员分享,可在线阅读,更多相关《《形式语言与自动机》课件ch4.6-4.7.ppt(14页珍藏版)》请在文库网上搜索。
1、1School of Computer Science,BUPT4.6 上下文无关语言的性质上下文无关语言的性质u2 2型语言的泵浦引理型语言的泵浦引理 u2 2型语言的封闭性型语言的封闭性 u2 2型语言的判定问题型语言的判定问题 u二义性问题二义性问题 2School of Computer Science,BUPT1.2型语言的泵浦引理型语言的泵浦引理n设设L L是是上上下下文文无无关关语语言言,存存在在常常数数p p,如如果果LL,且且pp,则则 可可 以以 写写 为为 1 12 20 03 34 4,使使 2 23 3,2 20 03 3pp,对对于于i0i0有有1 12 2i i0
2、 03 3i i4 4LL。(不不含含L L的情况)的情况)n物理意义:n线性语言的泵浦引理是说,在正规集合中,每个足够长的字符串都包含一个短的字串,随便将这个子串在原处重复插入多少次,所得的新字串还是在原正规集中。n 2型语言的泵浦引理是说,有两个靠得很近的子串,它们可以重复任意多次(但二者重复的次数相同),所得的新串依然属于该2型语言。3School of Computer Science,BUPT设设G是是Chomsky文法(形如文法(形如ABC,Aa),产生语言产生语言L,若若L且且有一定的长度,则边缘为有一定的长度,则边缘为的推导树有一定的推导树有一定长度的路径。长度的路径。对于对于
3、Chomsky范式,设路径长度为范式,设路径长度为n,则有边缘长度,则有边缘长度 2n1 ,如下图所示,如下图所示 证明:明:Sa A路径 1 a 21 1 1SABa Aa A路径 2 aa 22 1 24School of Computer Science,BUPT设文法设文法G有有n个非终结符,取个非终结符,取p2n ,若若L,且,且p(即(即 2n ),则必有则必有 2n1 ,即存在一条,即存在一条长度长度 n的路径,至少为的路径,至少为n+1。这时。这时,该路径上的结点数为该路径上的结点数为n+2(包括最高层顶点及最底层叶子)。包括最高层顶点及最底层叶子)。G中只有中只有n个非终结符
4、个非终结符在这条路径上必然有某两个结点相同在这条路径上必然有某两个结点相同Saaaaa路径424-18(第i层最多有2i 个非终结符。第i+1层若全为终结符,则与第i层非终结符个数相等。)5School of Computer Science,BUPT设为设为v1 1=v2 2=A,v1 1靠近树根,靠近树根,v1 1到叶子的最长路径为到叶子的最长路径为n+1。形如形如 如图:Z1203Z12 n p (v1到叶子的路径最多为n+1)而v1*=2v23,v2*=0v1v2A v1*=2v23 =22v233=2i2v233i=2iv23i=2i03i S=12034*=12i 03i4 SCA
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言与自动机 形式语言 自动机 课件 ch4 4.7