《形式语言与自动机》课件ch4.6-4.7.ppt

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路径 2aa22 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。形如形如 如图：Z1203Z1 2 n p （v1到叶子的路径最多为n+1）而v1*=2v23，v2*=0v1v2A v1*=2v23 =22v233=2i2v233i=2iv23i=2i03i S=12034*=12i

5、03i4 SCABABCBABBbbbbbb路径P在该路径上：v1靠近根，其子树为T1，边为Z1v2远离根，其子树为T2，边为0203=416School of Computer Science,BUPT2 2型文法泵浦引理的用途：判断一给型文法泵浦引理的用途：判断一给定语言不是上下文无关文法。定语言不是上下文无关文法。思路：用反证法。例：证明 Lanbncn n1 不是2型语言证：假设L是2型语言。取常数p，apbpcp ,3pp 将写成12034,其中231 且 203p.考虑203在中所处的位置：如果2含有a，3含有c，apbpcp ,则有203最小为abpc p+2p 不满足泵浦引理的

6、条件。如果2、3都含有a，（b或c）apbpcp 可写成akam an al ajbpcp 20 3其中m+n+lp,m+l1,k+m+n+l+j=p.将2、3重复i=2次，将有 =akamianaliajbpcp =ap+m+lbpcpL (a的个数大于b和c的个数)与2型语言的假设矛盾。7School of Computer Science,BUPT(3)若2、3分别包含a和b（b和c）设2=am、3=bn 且m+n1当取=akamap-m-kbjbnbp-j-ncp 时 将2、3重复i=2次，有将 =akaimap-m-kbjbinbp-j-ncp L （其中a、b个数将大于c的个数）与

7、2型语言假设矛盾。综上，L不是2型语言。8School of Computer Science,BUPT例：证明例：证明L 不是不是2型语言型语言证：假设证：假设L是是2型语言。型语言。由泵浦引理，取常数由泵浦引理，取常数p，当，当L时，时，k2 p 将将 写为写为12034，并有，并有203 p 且且 23即即231则应有则应有12i03i4 L203 p，2311203p又又 ，特别是当取，特别是当取kp时，时，有有=p2 12034 p2 12 20324 p2 +p即导致即导致p2 12 20324 受限型文法受限型文法一、线性文法：一、线性文法：生成式为生成式为AA1 1CC2 2

8、或或 AA1 1 形式的形式的2 2型文法型文法,其中其中1 1、2 2 T T*,A,CN ,A,CN ,且且1 12 2。n由线性文法产生的语言称为线性语言。由线性文法产生的语言称为线性语言。n正则文法为线性文法。反之不成立。正则文法为线性文法。反之不成立。13School of Computer Science,BUPTn例：例：G1 1（S,a,b,P,S）SaSabSb L(G1 1)a,b*n例：例：G2 2（S,a,b,P,S）SaSbab L(G2 2)anbn n1n L(G1 1)和和L(G2 2)都是线性语言，但不是正则集。都是线性语言，但不是正则集。14School of Computer Science,BUPTn二、顺序文法：二、顺序文法：设设G（N,T,P,S）,若非终结符可被排序为若非终结符可被排序为A1A2 2An n，NA1 1,A2 2,An n，当，当P中有生成式中有生成式Ak k，则则内不含有内不含有lk的的Al l。此时称文法。此时称文法G为顺序文法。为顺序文法。n由顺序文法产生的语言为顺序由顺序文法产生的语言为顺序语言。语言。