抽水引理是这样的：
对于常规语言L，存在一个p > 0使得对于所有w ∈ L
其中|w| ≥ p，存在一些分裂w = vxu，以下成立：
- |vx| ≤ p
- |x| > 0
- vx i u ∈ L对于所有i ≥ 0
我再说一遍的原因是因为你的一些不平等是错误的。
抽水引理有什么用？
抽水引理的唯一用途是确定一种语言是否特别不规则。即，如果一种语言不遵循泵引理，它就不可能是正则的。但仅仅因为一种语言泵，并不意味着它是规则的（这个引理用于反证）。
它如何显示它是否是正常的？
正如我上面所说，它没有，有一些不规则的可泵送语言（编辑维基百科有一个满足泵送引理但在这里不规则的语言示例），但是，我想也许你想要的问题请问是这样的：为什么所有的正则语言都可以抽？
为什么所有常规语言都可以抽？
考虑一个正则语言的特征，它被一些离散有限自动机M识别，具有一些有限数量的状态n。
然后，考虑M语言中的某个字符串，我们称之为w，其中|w| ≥ n成立。
在检查w时，M必须通过|w| + 1个状态（包括其开始和结束状态）。因此，根据鸽巢原理，M必须多次通过某些状态（因为|w| + 1 > n）。
令w = a 1 a 2 ...a n
想象一下，这些是M的状态转换，从q s开始，到q f结束，在处理w中：
a 1 a 2 a 3 ... a n
q s → q 1 → q 2 → ... → q n = q f
现在让我们看看这些状态转换中M重复一个状态的部分，我们称该状态为R：
a 1 a 2 a 3 a r a r+1 a r+2 a r+k a r+k+1 a r+k+2 a n
q s → q 1 → q 2 → ... → q r = R → q r+1 → ... → q r+k = R → q r+k+1 → ... → q n = q f
让我们在这里用一个简写来表达：
a 1 a 2 a 3 a r
q s → q 1 → q 2 → ... → q r
与此相同：
v
q s →* q r
其中v = a 1 a 2 ...a r
现在让我们按照以下方式将w分成三部分，w = vxu：
v = a 1 a 2 ...a r
x = a r+1 a r+2 ...a r+k
u = a r+k+1 a r+k+2 ...a n
现在我们看到v：
v
q s →* R
对于x：
X
R →* R
对你来说：
你
R →* q f
（我所做的只是将上面较长的状态转换图分成三个独立的）
在这里，您看到M也将接受vu，vxxu，vxxxu，...， vx i u for i ≥ 0 ，因为在状态R处理字符串x会使M保持在状态R。
本质上，抽引引理的目的是找到字符串中在处理时不会改变M状态的位。
现在你可能想知道。如果没有被M识别的字符串，|w|怎么办？≥n成立吗？
好吧，在这种情况下，您可以推断该语言是规则的，仅仅因为它是有限的（∑* 的所有有限子集都是规则的），此外，抽水引理是空洞的，您只需选择抽水长度p > n，您可以确定M识别的所有字符串也满足|w| ≥ p可以被抽（因为你知道不存在）。
上下文无关语言的引理是否不同？
是的，这里是：
对于上下文无关语言L，存在一个p > 0使得对于所有w ∈ L
其中|w| ≥ p，存在一些分裂w = uxyzv，以下成立：
- |xyz| ≤ p
- |xz| > 0
- ux i yz i v ∈ L对于所有i ≥ 0
它的证明有点复杂，而且这个答案已经很长了，所以这是草图：
本质上，这个引理利用的是另一个鸽笼原则风格的论点，但这一次，关注的是上下文无关语法中的变量数量，以及其最大产生式的长度。
使用此信息，可以看到对于给定的语法，有一些字符串足够大，以至于它们需要在自身内部复制解析树的一部分。解析树的这一部分是xyz，正在发生的事情是y被另一个xyz替换。
如果语言是有限的，这个引理也可以是空洞的，并且也用于对立式，就像常规语言的抽水引理一样。
如果您需要更多信息，我推荐Michael Sipser的《计算理论导论》。它对两个泵引理都有一些很好的部分，我觉得它很好地解释了它们。