泵引理

泵引理是形式语言与自动机理论中判定一个语言不是正则语言的重要工具，下面介绍的是其通用的形式，除此之外还有其推广的强泵引理等。在可计算性理论中的形式语言理论中，泵引理声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。