形式语言与自动机11ch4.6-4.7-1要点.pptVIP

College of Computer Science Technology, BUPT * College of Computer Science Technology, BUPT §4.6 上下文无关语言的性质 2型语言的泵浦引理 2型语言的封闭性 2型语言的判定问题 二义性问题 * College of Computer Science Technology, BUPT 1. 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型语言。 * College of Computer Science Technology, BUPT 设G是Chomsky文法（形如A→BC,A→a）,产生语言L－{ε}, 若ω∈L且ω有一定的长度，则边缘为ω的推导树有一定长度的路径。 对于Chomsky范式，设路径长度为n，则有边缘长度 ︱ω︱≤ 2n－1 ，如下图所示 证明： S a A 路径 ＝1 ︱ω︱＝︱a︱＝21－1 ＝1 S A B a A a A 路径 ＝2 ︱ω︱＝︱aa︱＝22－ 1 ＝2 * College of Computer Science Technology, BUPT 设文法G有n个非终结符，取p＝2n ,若ω∈L，且︱ω︱≥p （即︱ω︱≥ 2n ）,则必有︱ω︱≥ 2n－1 ，即存在一条长度 n的路径，至少为n+1。这时,该路径上的结点数为n+2(包括最高层顶点及最底层叶子）。 ∵G中只有n个非终结符 ∴在这条路径上必然有某两个结点相同 S a a a a a 路径＝4 ︱ω︱≤24-1＝8 （第i层最多有2i 个非终结符。第i+1层若全为终结符，则与第i层非终结符个数相等。） * College of Computer Science Technology, BUPT 设为v1= v2=A, v1靠近树根，v1到叶子的最长路径为n+1。 形如 如图：Z1＝ω2ω0ω3 ︱Z1∣≤2 n ＝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ω4 S C A B A B C B A B B b b b b b b 路径P 在该路径上： v1靠近根，其子树为T1，边为Z1 v2远离根，其子树为T2，边为ω0 ω2 ω0 ω3=ε ω4 ω1 * College of Computer Science Technology, BUPT 2型文法泵浦引理的用途：判断一给定语言不是上下文无关文法。 思路：用反证法。 例：证明 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 可写成ω＝akam an al ajbpcp ω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