泵引理是形式语言与自动机理论中判定一个语言不是正则语言的重要工具，下面介绍的是其通用的形式，除此之外还有其推广的强泵引理等。

外文名

pumping lemma

简介

在可计算性理论中的形式语言理论中，

泵引理

声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。

两个最重要例子是

正则语言的泵引理

和 上下文无关语言

的泵引理

。

鄂登引理

是另一种更强的上下文无关语言的泵引理。

这些引理可以用来确定特定语言

不

在给定语言类中。但是它们不能被用来确定一个语言在给定类中，因为满足引理是类成员关系的必要条件，但不是充分条件。

泵引理是1961年由Y. Bar-Hillel、M. Perles和E. Shamir首次发表的。

引理描述

若 L 是正则语言，则存在一常数 n > 0 ，对于语言 L 中每个满足|w| ≥ n的字符串w，存在一组x,y,z使得，w=xyz且：

1.|xy| ≤ n ；

2.|y| ≥ 1；

泵引理

3.对所有的 k ≥ 0 ，字串 属于 L。

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

证

：若L为正则语言，那么存在一个DFA识别它。设其状态数为n，那么对于任意字符串w∈ 它被DFA识别时的状态转换为： （qn为接受状态）。因为w≥ n，所以由鸽笼原理存在状态重复，记状态 所识别的字符串为y，那么易知（即是将重复状态重复k次）仍可被此DFA识别，故 ∈ 。

引理应用

泵引理

泵引理

例1

：字符串集合 ={ | m,n∈N ∧ n>m }不是正则的。

泵引理

泵引理

证明

：显然 ∈ ，所以由泵引理知当p足够大时字符串中存在子串可重复。若该子串中只有0，那么当k>1时将使得0多于1，这将导致矛盾。若同时存在0,1，那么这将使0,1交替出现，同样导致矛盾。若只出现1，由泵引理知k可为0，而此时将有1不多于0，这也是矛盾的。因此该语言不是正则的。

泵引理

泵引理

例2

：若 为所有素数的二进制表示的0,1串，那么 不是正则的。

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

泵引理

证明

：由初等数论易知存在任意大的素数，所以存在素数 使得其二进制串长度大于泵引理阈值。将 表示为，由泵引理知 的二进制位串也属于，因此 也是素数。由费马小定理知，所以 即，又（即其可逆）所以。因此，所以 | 这与 为素数矛盾，故 不是正则的。