Automata Theory 简明教程

Pumping Lemma for CFG

Lemma

如果 L 是上下文无关语言，那么存在一个泵长 p ，使得任何长度为 ≥ p 的字符串 w ∈ L 均可写为 w = uvxyz ，其中 vy ≠ ε 、 |vxy| ≤ p ，且对于所有 i ≥ 0, uvixyiz ∈ L 。

If L is a context-free language, there is a pumping length p such that any string w ∈ L of length ≥ p can be written as w = uvxyz, where vy ≠ ε, |vxy| ≤ p, and for all i ≥ 0, uvixyiz ∈ L.

Applications of Pumping Lemma

泵引理用于检查语法是否上下文无关。让我们举一个例子来说明它是如何检查的。

Pumping lemma is used to check whether a grammar is context free or not. Let us take an example and show how it is checked.

Problem

找出语言 L = {xnynzn | n ≥ 1} 是否上下文无关。

Find out whether the language L = {xnynzn | n ≥ 1} is context free or not.

Solution

令 L 是无上下文的。然后， L 必须满足抽空引理。

Let L is context free. Then, L must satisfy pumping lemma.

首先，选择抽空引理中的一个数字 n 。然后，将z视为0n1n2n。

At first, choose a number n of the pumping lemma. Then, take z as 0n1n2n.

将 z 分解为 uvwxy, ，其中

Break z into uvwxy, where

|vwx| ≤ n and vx ≠ ε.

因此 vwx 不可能同时包含0和2，因为最后一个0和第一个2至少相隔(n+1)个位置。有两种情况 −

Hence vwx cannot involve both 0s and 2s, since the last 0 and the first 2 are at least (n+1) positions apart. There are two cases −

Case 1 − vwx 没有2。然后 vx 只包含0和1。然后 uwy ，它必须在 L 中，有 n 2，但少于 n 0或1。

Case 1 − vwx has no 2s. Then vx has only 0s and 1s. Then uwy, which would have to be in L, has n 2s, but fewer than n 0s or 1s.

Case 2 − vwx 没有0。

Case 2 − vwx has no 0s.

这里出现了矛盾。

Here contradiction occurs.

因此， L 不是无上下文语言。

Hence, L is not a context-free language.