Automata Theory 简明教程 Pumping Lemma for CFG Automata Theory 简明教程 Pumping Lemma for CFG Lemma 如果 L 是上下文无关语言，那么存在一个泵长 p ，使得任何长度为 ≥ p 的字符串 w ∈ L 均可写为 w = uvxyz ，其中 vy ≠ ε 、 |vxy| ≤ p ，且对于所有 i ≥ 0, uvixyiz ∈ L 。 Applications of Pumping Lemma 泵引理用于检查语法是否上下文无关。让我们举一个例子来说明它是如何检查的。 Problem 找出语言 L = {xnynzn | n ≥ 1} 是否上下文无关。 Solution 令 L 是无上下文的。然后， L 必须满足抽空引理。 首先，选择抽空引理中的一个数字 n 。然后，将z视为0n1n2n。 将 z 分解为 uvwxy, ，其中 |vwx| ≤ n and vx ≠ ε. 因此 vwx 不可能同时包含0和2，因为最后一个0和第一个2至少相隔(n+1)个位置。有两种情况 − Case 1 − vwx 没有2。然后 vx 只包含0和1。然后 uwy ，它必须在 L 中，有 n 2，但少于 n 0或1。 Case 2 − vwx 没有0。 这里出现了矛盾。 因此， L 不是无上下文语言。