资源描述：
《形式语言与自动机课件――上下文无关语言的性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、§4.6上下文无关语言的性质2型语言的泵浦引理2型语言的封闭性2型语言的判定问题二义性问题1CollegeofComputerScience&Technology,BUPT1.2型语言的泵浦引理设L是上下文无关语言，存在常数p，如果ω∈L，且︱ω︱≥p，则ω可以写为ω＝ω1ω2ω0ω3ω4，使ω2ω3≠ε，∣ω2ω0ω3∣≤p，对于i≥0有ω1ω2iω0ω3iω4∈L。（不含L＝{ε}的情况）物理意义:线性语言的泵浦引理是说，在正规集合中，每个足够长的字符串都包含一个短的字串，随便将这个子串在原处重复插入多少次，所得的新字串还是在原正规集中。2型语言的泵浦引理是说，有两个靠得很近的子串，它
2、们可以重复任意多次（但二者重复的次数相同），所得的新串依然属于该2型语言。2CollegeofComputerScience&Technology,BUPT设G是Chomsky文法（形如A→BC,A→a）,产生语言L－{ε},若ω∈L且ω有一定的长度，则边缘为ω的推导树有一定长度的路径。对于Chomsky范式，设路径长度为n，则有边缘长度︱ω︱≤2n－1，如下图所示证明：SaA路径＝1︱ω︱＝︱a︱＝21－1＝1SABaAaA路径＝2︱ω︱＝︱aa︱＝22－1＝23CollegeofComputerScience&Technology,BUPT设文法G有n个非终结符，取p＝2n,若ω∈L，
3、且︱ω︱≥p（即︱ω︱≥2n）,则必有︱ω︱≥2n－1，即存在一条长度>n的路径，至少为n+1。这时,该路径上的结点数为n+2(包括最高层顶点及最底层叶子）。∵G中只有n个非终结符∴在这条路径上必然有某两个结点相同Saaaaa路径＝4︱ω︱≤24-1＝8（第i层最多有2i个非终结符。第i+1层若全为终结符，则与第i层非终结符个数相等。）4CollegeofComputerScience&Technology,BUPT设为v1=v2=A,v1靠近树根，v1到叶子的最长路径为n+1。形如如图：Z1＝ω2ω0ω3︱Z1∣≤2n＝p（∵v1到叶子的路径最多为n+1）而v1*=>ω2v2ω3，v2*
4、=>ω0∵v1＝v2＝A∴v1*=>ω2v2ω3=>ω2ω2v2ω3ω3=>ω2iω2v2ω3ω3i=>ω2iv2ω3i=>ω2iω0ω3i∴S=>ω1ω2ω0ω3ω4*=>ω1ω2iω0ω3iω4SCABABCBABBbbbbbb路径P在该路径上：v1靠近根，其子树为T1，边为Z1v2远离根，其子树为T2，边为ω0ω2ω0ω3=εω4ω15CollegeofComputerScience&Technology,BUPT2型文法泵浦引理的用途：判断一给定语言不是上下文无关文法。思路：用反证法。例：证明L＝{anbncn∣n≥1不是2型语言}证：假设L是2型语言。取常数p，ω＝apbpcp,
5、∣ω∣＝3p≥p将ω写成ω＝ω1ω2ω0ω3ω4,其中∣ω2ω3∣≥1且∣ω2ω0ω3∣≤p.考虑ω2ω0ω3在ω中所处的位置：①如果ω2含有a，ω3含有c， ∵ω＝apbpcp,则有∣ω2ω0ω3∣最小为∣abpc∣＝p+2>p ∴不满足泵浦引理的条件。②如果ω2、ω3都含有a，（b或c）∵∣ω∣＝apbpcp可写成ω＝akamanalajbpcpω2ω0ω3其中m+n+l≤p,m+l≥1,k+m+n+l+j=p.将ω2、ω3重复i=2次，将有ω’=akamianaliajbpcp=ap+m+lbpcp∈L(a的个数大于b和c的个数)∴与2型语言的假设矛盾。6CollegeofCompu
6、terScience&Technology,BUPT(3)若ω2、ω3分别包含a和b（b和c）设ω2=am、ω3=bn且m+n≥1当取ω=akamap-m-kbjbnbp-j-ncp时将ω2、ω3重复i=2次，有将ω’=akaimap-m-kbjbinbp-j-ncp∈L（∵其中a、b个数将大于c的个数）∴与2型语言假设矛盾。综上，L不是2型语言。7CollegeofComputerScience&Technology,BUPT例：证明L＝{ak2︱k≥1}不是2型语言证：假设L是2型语言。由泵浦引理，取常数p，当ω∈L时，︱ω︱＝k2≥p将ω＝ak2写为ω＝ω1ω2ω0ω3ω4，并有︱ω
7、2ω0ω3︱≤p且︱ω2ω3︱≠ε即︱ω2ω3︱≥1则应有ω1ω2iω0ω3iω4∈L∵︱ω2ω0ω3︱≤p，︱ω2ω3︱≥1∴1≤︱ω2ω0ω3︱≤p又∵ω＝ak2，特别是当取k＝p时，有︱ω︱=p2＝︱ω1ω2ω0ω3ω4︱∴p2<︱ω1ω22ω0ω32ω4︱p2+p即导致p2<︱ω1ω22ω0ω32ω4︱<（p+1）2即ω’∈L，与假设
