在计算理论中，有两个重要的泵引理，分别对应于正规语言（Regular Languages）和上下文无关语言（Context-Free Languages）。
正规语言的泵引理
正规语言的泵引理指出，对于任何正规语言 L，存在一个整数 n，使得任何长度
≥ n 的字符串 x ∈ L 都可以被划分为 x = uvw，其中 u, v, w ∈ Σ*，并且满足以下条件：
≤ n
≥ 1
对于所有 i ≥ 0，u vⁱ w ∈ L
- 子串 v 可以被重复（即“泵”）任意次数，结果字符串仍然属于 L。
- 泵引理主要用于证明一个语言不是正规的。
- 如果任何经过“泵化”的字符串不属于 L，那么 L 就不是正规语言。
- 然而，满足泵引理的条件并不能保证一个语言是正规语言。
!p1
示例：
让我们来证明 L01 = {0n1n | n ≥ 0} 是非正规的。
假设 L 是正规语言。根据泵引理，上述规则必须成立。现在，设 x ∈ L 且
≥ n。根据泵引理，存在 u, v, w 使得条件 (1) – (3) 成立。
我们将证明对于所有的 u, v, w，条件 (1) – (3) 实际上无法同时满足。如果 (1) 和 (2) 成立，那么 x = 0n1n = uvw，其中
≤ n 且
≥ 1。
因此，我们可以设 u = 0a, v = 0b, w = 0c1n，其中：
- a + b ≤ n
- b ≥ 1
- c ≥ 0
- a + b + c = n
但是，当 i = 0 时，条件 (3) 就失效了：
uv⁰w = uw = 0a0c1n = 0a+c1n ∉ L
因为 a + c ≠ n，所以它不再属于 L。这与假设矛盾，因此 L01 不是正规语言。
!p2
上下文无关语言（CFL）的泵引理
上下文无关语言的泵引理指出，对于任何上下文无关语言 L，我们可以找到两个子串，它们可以被“泵”任意次数，并且生成的字符串仍然属于该语言。
对于任何语言 L，我们可以将其字符串分解为五个部分，并对第二和第四个子串进行“泵化”。与正规语言类似，这里的泵引理也是作为一个工具来证明一个语言不是上下文无关语言（CFL）。因为，如果有一个字符串不满足其条件，那么该语言就不是 CFL。
因此，如果 L 是一个 CFL，存在一个整数 n，使得对于所有 x ∈ L 且
≥ n，存在 u, v, w, x, y ∈ Σ*，使得 x = uvwxy，并且满足：
-
vwx ≤ n
-
vx ≥ 1
- 对于所有 i ≥ 0：uviwxiy ∈ L
!p3
证明题
让我们证明：
L012 = { 0n1n2n ∣ n ≥ 0 }
不是上下文无关语言。
证明：
假设 L012 = {0n1n2n | n ≥ 0} 是上下文无关语言。
根据 CFL 泵引理，存在一个整数 p，使得任何字符串 s ∈ L 且 ∣s∣ ≥ p 都可以被写成 s = uvwxy，满足：
∣vwx∣ ≤ p，∣vx∣ ≥ 1，并且对于所有 i ≥ 0，uviwxiy ∈ L。
让我们取 s = 0p1p2p。
由于 ∣vwx∣ ≤ p，子串 vwx 不能同时包含 0 和 2。因此，它必须完全位于一个字符块内，或者最多跨越两个相邻的字符块。
当我们进行泵化操作（例如取 i = 0 或 i = 2）时，只会改变其中一个或两个块中的符号数量，而第三个块保持不变。因此，0、1 和 2 的数量将不再相等，这意味着泵化后的字符串不再属于 L。
这产生了矛盾。
因此，L012 = {0n1n2n | n ≥ 0} 是非上下文无关语言。