##### 泵引理 - 泵引理 - **泵引理**表示对某种[[形式语言]], 如果足够长的字符串属于该语言, 那么它的某个部分可以被重复任意次, 并且新的字符串仍属于该语言, 常用于[[正则语言]]和[[上下文无关语言]] - 如果 $A$ 是正则语言, 则存在一个泵送长度 $p$, 对于任意字符串 $s \in A$ 且 $|s| \geq p$, 可以将 $s$ 分解为三部分 $s = xyz$, 满足以下条件 - 对于任意 $i \geq 0$, $xy^i z \in A$ - $|y| > 0$, 即 $y \neq \varepsilon$ - $|xy| \leq p$, 即 $x, y$ 两个部分的长度总和不超过 $p$ - 如果 $A$ 是一个上下文无关语言, 则存在一个泵送长度 $p$, 对于任意字符串 $s \in A$ 且 $|s| \geq p$, 可以将 $s$ 分解为五个部分 $s = uvxyz$, 满足以下条件 - 对于任意 $i \geq 0$, 字符串 $uv^ixy^iz \in A$ - $|vy| > 0$, 即 $v$ 和 $y$ 不能同时为空 - $|vxy| \leq p$, 即 $v, x, y$ 三个部分的长度总和不超过 $p$