正则语言的泵引理

对于一个正则语言 存在一个整数 使得对于 中的每一个长度大于等于 的字符串 都可以写作 满足以下性质：

上下文无关语言的泵引理

对于每一个上下文无关语言 都存在一个整数 使得 满足：