派生和解析树
考虑语言
L ={1米宽1米宽1米宽}
这是这种语言的语法。
S→a→b
A→0 A | 0
B→0 B→1 | ε
对于任何给定的x∈L，我们必须能够使用给定的语法构造x的派生。下面是一个例子：要派生字符串x = 000011，我们这样做
S→a b→0 a b→00b→000b1→0000b11→000011
提供派生的另一种方法是构造解析树。与推导一样，解析树显示了哪些变量被替换为右边的哪些变量。例如，如果我们用这个规则
B→0→0
在派生中，解析树将包含一个相关的子树，看起来像这样：
下面是字符串x = 000011的完整解析树：
节能灯的抽运引理
引理如果L是CFL，那么有一个数p使得对于赢博体育s∈L，当|≥p时，我们有它
- S = uvwxy
- |v| > 0或|x| > 0
- |vwx|≤p
- uvnwxny∈L，对于赢博体育n≥0
证明如果L是一个CFL，那么对于L就存在某种语法G。G的arity是G中最长右手边的长度k，设n为G中变量的个数。此字符串的解析树的高度大于或等于n + 1。这意味着解析树中从根节点到叶节点的路径至少有n + 1个内部节点。这就意味着至少有一个变量需要重复。设A是这条路径上第一个重复出现的变量当我们沿着这条路径从叶节点到根节点时。
这将导致一个包含如下结构的解析树：
如果这是一个有效的解析树，那么这也是字符串uv2wx2y的有效解析树：
这是一个有效的字符串解析树：
通过使用类似的技巧，我们可以为任何形式为uvnwxny的字符串构造有效的解析树。
使用抽运引理来证明一种语言不是CFL
考虑语言
L = {zz | z∈Σ*}
如果我们假设L是CFL，设p为L的抽运长度
s = 0p1p0∈L
现在考虑当我们用|vwx|≤p分解s = uvwxy时会发生什么。因为我们有后一种约束，子串uvw最多可以跨出s中的四个子群中的两个。如果我们形成新的字符串uv2wx2y，新字符串将在s中的四个子群中最多引入两个新的0或1。
例如，新字符串可以等于0p1p+k0p+k1p。这个字符串不在L中。在赢博体育类似的情况下，我们将看到没有办法选择v和x来得到uv2wx2y∈L。