搜索
1CollegeofComputerScience&Technology,BUPT§4.6上下文无关语言的性质2型语言的泵浦引理2型语言的封闭性2型语言的判定问题二义性问题2CollegeofComputerScience&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型语言。3CollegeofComputerScience&Technology,BUPT设G是Chomsky文法（形如A→BC,A→a）,产生语言L－{ε},若ω∈L且ω有一定的长度，则边缘为ω的推导树有一定长度的路径。对于Chomsky范式，设路径长度为n，则有边缘长度︱ω︱≤2n－1，如下图所示证明：SaA路径＝1︱ω︱＝︱a︱＝21－1＝1SABaAaA路径＝2︱ω︱＝︱aa︱＝22－1＝24CollegeofComputerScience&Technology,BUPT设文法G有n个非终结符，取p＝2n,若ω∈L，且︱ω︱≥p（即︱ω︱≥2n）,则必有︱ω︱≥2n－1，即存在一条长度n的路径，至少为n+1。这时,该路径上的结点数为n+2(包括最高层顶点及最底层叶子）。∵G中只有n个非终结符∴在这条路径上必然有某两个结点相同Saaaaa路径＝4︱ω︱≤24-1＝8（第i层最多有2i个非终结符。第i+1层若全为终结符，则与第i层非终结符个数相等。）5CollegeofComputerScience&Technology,BUPT设为v1=v2=A,v1靠近树根，v1到叶子的最长路径为n+1。形如如图：Z1＝ω2ω0ω3︱Z1∣≤2n＝p（∵v1到叶子的路径最多为n+1）而v1*=ω2v2ω3，v2*=ω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ω16CollegeofComputerScience&Technology,BUPT2型文法泵浦引理的用途：判断一给定语言不是上下文无关文法。思路：用反证法。例：证明L＝{anbncn∣n≥1不是2型语言}证：假设L是2型语言。取常数p，ω＝apbpcp,∣ω∣＝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+2p∴不满足泵浦引理的条件。②如果ω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型语言的假设矛盾。7CollegeofComputerScience&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型语言。8CollegeofComputerScience&Technology,BUPT例：证明L＝{ak2︱k≥1}不是2型语言证：假设L是2型语言。由泵浦引理，取常数p，当ω∈L时，︱ω︱＝k2≥p将ω＝ak2写为ω＝ω1ω2ω0ω3ω4，并有︱ω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（增加了ω2ω3，而︱ω2ω3︱≤p）而（p+1）2＝p2+2p+1p2+p即导致p2︱ω1ω22ω0ω32ω4︱（p+1）2即ω’∈L，与假设L是2型文法矛盾∴L不是2型文法。9CollegeofComputerScience&Technology,BUPT2.2型语言的封闭性（1）设有2型语言L1、L2,则L1∪L2，L1L2，L1*为2型语言。证明——自学（2）2型语言对交不封闭反证：取反例L1＝{anbncm︱m,n≥1}——2型L2＝{ambncn︱m,n≥1}——2型L1∩L2＝{anbncn︱n≥1}——不是2型（3）2型语言对补运算不封闭若对补封闭，则对交封闭。已知对交不封闭，∴对补不封闭（4）2型语言对置换封闭。（略）10CollegeofComputerScience&Technology,BUPT※3.2型语言的判定问题——略11CollegeofComputerScience&Technology,BUPT4.二义性问题a．二义性定义：对同一句子（句型）存在两个不同的推导树或存在两个不同的最左（右）推导。b．上下文无关文法的二义性是不可判定的。c．可能导致二义性的某些生成式形式SSSSSSSSSS和二棵推导树（1）S→SS︱β对句型SSS，有将S→SS︱β变换为S→SA︱A，可消除二义性。A→β(2)S→SbS（3）S→aS︱Sβ12CollegeofComputerScience&Technology,BUPT§4.7受限型上下文无关文法对文法的生成式形式加以某些限制＝受限型文法一、线性文法：生成式为A→ω1Cω2或A→ω1形式的2型文法,其中ω1、ω2∈T*,A,C∈N,且ω1ω2≠ε。由线性文法产生的语言称为线性语言。正则文法为线性文法。反之不成立。13CollegeofComputerScience&Technology,BUPT例：G1＝（{S},{a,b},P,S）S→aSa︱bSb︱εL(G1)＝{ωω︱ω∈{a,b}*}例：G2＝（{S},{a,b},P,S）S→aSb︱abL(G2)＝{anbn∣n≥1}L(G1)和L(G2)都是线性语言，但不是正则集。14CollegeofComputerScience&Technology,BUPT二、顺序文法：设G＝（N,T,P,S）,若非终结符可被排序为A1A2…An，N＝{A1,A2,…,An}，当P中有生成式Ak→β，则β内不含有lk的Al。此时称文法G为顺序文法。由顺序文法产生的语言为顺序语言。例：（书P181,例2）15CollegeofComputerScience&Technology,BUPT作业：ch4习题23,24,2516CollegeofComputerScience&Technology,BUPT第四章上下文无关文法与下推自动机推导树与二义性上下文无关文法的变换Chomsky范式和Greibach范式下推自动机上下文无关文法与下推自动机上下文无关语言的性质受限型上下文无关文法17CollegeofComputerScience&Technology,BUPT练习题证明L={ambn|n=m2}不是2型语言。L={|{a,b}*}，求产生L的Greibach范式文法G，及空栈接受L的NPDAM。L={|{a,b}*且含a,b的个数相同}，求产生L的Greibach范式文法G，及空栈接受L的NPDAM。