上下文无关语言的泵引理_第1页
上下文无关语言的泵引理_第2页
上下文无关语言的泵引理_第3页
上下文无关语言的泵引理_第4页
上下文无关语言的泵引理_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

上下文无关语言的泵引理《理论计算机科学基础》1《理论计算机科学基础》2非上下文无关语言B={anbncn|n0}

非CFLC={ww|w{0,1}*

}

非CFLCc={x|xww,w{0,1}*

}

是CFL《理论计算机科学基础》3泵引理定理3.19(泵引理):

设A是上下文无关语言,

则存在常数p(泵长度)使得,

若sA且|s|p,则s=uvxyz,

满足下述条件:1)

i0,uvixyizA;2)|vy|>0;3)|vxy|p.《理论计算机科学基础》4泵引理定理3.19(泵引理):

设A是上下文无关语言,

则存在常数p(泵长度)使得,

若sA且|s|p,则s=uvxyz,

满足下述条件:1)

i0,uvixyizA;2)|vy|>0;3)|vxy|p.xvuyzRRxvuyzRRRvyxuzR《理论计算机科学基础》5泵引理证明:设G是产生A的CFG.令b是规则右边的最大长度,

不妨设b2.在G的语法分析树中,

每个结点至多有b个儿子.高度为h的语法分析树产生的串

长度不超过bh.设G中变元个数是|V|,令p=b|V|+2.则长度不小于p的串的语法

分析树高度至少是|V|+2.《理论计算机科学基础》6泵引理证明(续):

设s是长度不小于p的串,则s的语法分析树高度不小于|V|+2.

设是结点数最少的语法分析树.

中最长路径长度不小于|V|+2.

由于数叶是终结符,

这条路径上变元数不小于|V|+1.s《理论计算机科学基础》7泵引理证明(续):

根据鸽巢原理,

必有某个变元R在这条路径上

重复出现.

选择R为这条路径上在

最下面的|V|+1个变元中

重复出现的变元.RR《理论计算机科学基础》8泵引理证明(续):

如图把s划分成uvxyz.

上面的R带有较大的子树,

产生vxy.

下面的R带有较小的子树,

产生x.

这两个子树可以互相替换,

因此i0,uvixyizA.xvuyzRRxvuyzRRRvyxuzR《理论计算机科学基础》9泵引理证明(续):v和y不能都是空串,

否则用较小的子树替换

较大的子树仍然得到s,

但是整个树的结点数减少,

这与是结点数最少的语法

分析树矛盾.

所以|vy|>0.xvuyzRR《理论计算机科学基础》10泵引理证明(续):R的选取使得R两次

出现都是在最长路径最下面的

|V|+1个变元中,所以产生vxy的R的子树

人人文库> 全部分类> 行业资料 > 工业设计

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论