形式语言与自动机课件——上下文无关语言的性质讲解

1、1College of Computer Science & Technology, BUPT 4.6 上下文无关语言的性质上下文无关语言的性质 u2 2型语言的泵浦引理型语言的泵浦引理 u2 2型语言的封闭性型语言的封闭性 u2 2型语言的判定问题型语言的判定问题 u二义性问题二义性问题 2College of Computer Science & Technology, BUPT 1.2型语言的泵浦引理型语言的泵浦引理 n设设L L是上下文无关语言，存在常数是上下文无关语言，存在常数p p，如果，如果LL，且，且 pp，则，则可以写为可以写为1203412034，使，使2323， 203p

2、203p，对于，对于i0i0有有112 2i i0303i i4L4L。（不。（不 含含L L的情况）的情况） n物理意义: n线性语言的泵浦引理是说，在正规集合中，每个足够长的字 符串都包含一个短的字串，随便将这个子串在原处重复插入多 少次，所得的新字串还是在原正规集中。 n 2型语言的泵浦引理是说，有两个靠得很近的子串，它们可以 重复任意多次（但二者重复的次数相同），所得的新串依然属 于该2型语言。 3College of Computer Science & Technology, BUPT 设设G是是Chomsky文法（形如文法（形如ABC,Aa）,产生语言产生语言L, 若若L且且有一

3、定的长度，则边缘为有一定的长度，则边缘为的推导树有一定长度的的推导树有一定长度的 路径。路径。 对于对于Chomsky范式，设路径长度为范式，设路径长度为n，则有边缘长度，则有边缘长度 2n 1 ，如下图所示 ，如下图所示 证明：证明： S a A 路径 1 a 2 1 1 1 S AB a A a A 路径 2 aa22 1 2 4College of Computer Science & Technology, BUPT 设文法设文法G有有n个非终结符，取个非终结符，取p2n ,若若L，且，且 p （即（即 2n ）,则必有则必有 2n 1 ，即存在一条 ，即存在一条 长度长度 n的路径，

4、至少为的路径，至少为n+1。这时。这时,该路径上的结点数为该路径上的结点数为 n+2(包括最高层顶点及最底层叶子）。包括最高层顶点及最底层叶子）。 G中只有中只有n个非终结符个非终结符 在这条路径上必然有某两个结点相同在这条路径上必然有某两个结点相同 S a aa aa 路径4 24-18 （ 第 i 层 最 多 有 2 i 个非终结符。第i+1 层若全为终结符，则 与第i层非终结符个 数相等。） 5College of Computer Science & Technology, BUPT 设为设为v1= v2=A, v1靠近树根，靠近树根，v1到叶子的最长路径为到叶子的最长路径为n+1。

5、形如形如 如图：Z1203 Z1 2 n p （v1到叶子的路径最多为n+1） 而v1 * =2v23， v2 * =0 v1v2A v1 * =2v23 =22v233 =2i2v233i =2iv23i =2i03i S =12034 * =12i 03i4 S C AB AB CB AB B b b bb bb 路径P 在该路径上： v1靠近根，其子树为T1， 边为Z1 v2远离根，其子树为T2， 边为0 20 3 = 4 1 6College of Computer Science & Technology, BUPT 2 2型文法泵浦引理的用途：判断一给型文法泵浦引理的用途：判断一给

6、 定语言不是上下文无关文法。定语言不是上下文无关文法。 思路：用反证法。 例：证明 Lanbncn n1 不是2型语言 证：假设L是2型语言。 取常数p，apbpcp , 3pp 将写成12034, 其中231 且 203p. 考虑203在中所处的位置： 如果2含有a，3含有c， apbpcp , 则有203最小为abpc p+2p 不满足泵浦引理的条件。 如果2、3都含有a，（b或c） apbpcp 可写成akam an al ajbpcp 20 320 3 其中m+n+lp, m+l1,k+m+n+l+j=p. 将2、3重复i=2次，将有 = akamianaliajbpcp =ap+m+

7、lbpcpL (a的个数大于b和c的个数) 与2型语言的假设矛盾。 7College of Computer Science & Technology, 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的个数） 与2型语言假设矛盾。 综上，L不是2型语言。 8College of Computer Science & Technology, BUPT 例：证明例：证明L ak2 k1不是不是

8、2型语言型语言 证：假设证：假设L是是2型语言。型语言。 由泵浦引理，取常数由泵浦引理，取常数p，当，当L时，时， k2 p 将将ak2 写为写为12034，并有，并有 203 p 且且 23即即231 则应有则应有12i03i4 L 203 p，231 1203p 又又ak2 ，特别是当取，特别是当取kp时，时， 有有=p2 12034 p2 12 20324 p2 +p 即导致即导致p2 12 20324 受限型文法受限型文法 一、线性文法：一、线性文法： 生成式为生成式为A1C2 A1C2 或或 A1 A1 形式的形式的2 2型文法型文法, ,其中其中 11、2 T2 T* * , A,

9、CN , , A,CN ,且且1212。 n由线性文法产生的语言称为线性语言。由线性文法产生的语言称为线性语言。 n正则文法为线性文法。反之不成立。正则文法为线性文法。反之不成立。 13College of Computer Science & Technology, BUPT n例：例：G1（S,a,b,P,S） SaSabSb L(G1)a,b* n例：例：G2（S,a,b,P,S） SaSbab L(G2)anbn n1 n L(G1)和和L(G2)都是线性语言，但不是正则集。都是线性语言，但不是正则集。 14College of Computer Science & Technolog

10、y, BUPT n二、顺序文法：二、顺序文法： 设设G（N,T,P,S）,若非终结符可被排序为若非终结符可被排序为 A1A2An，NA1,A2,An，当，当P中有生成式中有生成式 Ak，则，则内不含有内不含有lk的的Al。此时称文法。此时称文法G为顺为顺 序文法。序文法。 n由顺序文法产生的语言为顺序语言。由顺序文法产生的语言为顺序语言。 n例：（书例：（书P181,例例2） 15College of Computer Science & Technology, BUPT 作业：作业：ch4ch4习题习题 23,24,25 23,24,25 16College of Computer Science & Technology, BUPT 第四章第四章 上下文无关文法与下推自动机上下文无关文法与下推自动机 n推导树与二义性推导树与二义性 n上下文无关文法的变换上下文无关文法的变换 nChomsky范式和范式和Greibach范式范式 n下推自动机下推自动机 n上下文无关文法与下推自动机上下文无关文法与下推自动机 n上下文无关语言的性质上下文无关语言的性质 n受限型上下文无关文法受限型上下文无关文法 17College of Computer Science & Technology, BUP