问什么是Layman术语中的Pumping引理？

EN

pumping引理是一个简单的证明，表明一种语言不是正则的，这意味着不能为它构建有限状态机。典型的例子是(a^n)(b^n)语言。这是一种简单的语言，它是任意数量的a，后跟相同数量的b，所以字符串

ab
aabb
aaabbb
aaaabbbb

等都在语言中，但是

aab
bab
aaabbbbbb

等等都不是。

为这些示例构建一个FSM非常简单：

​

​

这将一直工作到n=4，问题是我们的语言没有对n施加任何约束，有限状态机必须是有限的。无论我在这台机器中添加了多少个状态，都会有人给我一个输入，其中n等于状态数加1，我的机器就会失败。因此，如果可以构建一台机器来读取这种语言，那么一定有一个循环在其中，以保持有限的状态数量。添加这些循环后：

​

​

我们语言中的所有字符串都将被接受，但有一个问题。在前四个a之后，机器失去了已经输入了多少个a的计数，因为它保持在相同的状态。这意味着在四次之后，我可以在字符串中添加任意数量的a，而不需要添加任何b，并且仍然可以得到相同的返回值。这意味着字符串：

aaaa(a*)bbbb

使用(a*)表示任意数量的a，都将被机器接受，即使它们显然并不都在语言中。在这种情况下，我们可以说字符串(a*)的一部分可以被抽出。有限状态机是有限的，而n是无界的，这一事实保证了任何接受该语言中所有字符串的机器都必须具有此属性。机器必须在某个点上循环，并且在它循环的点上，语言可以被抽出。因此，不能为该语言构建有限状态机，并且该语言不是正规的。

记住Regular Expressions and Finite State Machines are equivalent，然后用可以相互嵌入的开始标记和结束标记替换a和b，您就会明白为什么使用it is not possible to use regular expressions to parse Html

这是一种旨在证明给定语言不能属于某一类的工具。

让我们考虑一下平衡括号的语言(表示符号'(‘’和')'，包括通常意义上平衡的所有字符串，而不包括不平衡的字符串)。我们可以使用泵浦引理来证明这不是正则的。

(语言是一组可能的字符串。解析器是一种机制，我们可以使用它来查看字符串是否在语言中，因此它必须能够区分语言中的字符串和语言之外的字符串。一种语言是“常规的”(或“上下文无关的”或“上下文敏感的”等等)，如果有一个常规的(或其他的)解析器可以识别它，区分该语言中的字符串和非该语言中的字符串。)

LFSR Consulting提供了一个很好的描述。我们可以为常规语言绘制一个解析器，作为框和箭头的有限集合，箭头表示字符，框连接字符(充当“状态”)。(如果比这更复杂，它就不是一种常规语言。)如果我们可以得到一个比盒子数量更长的字符串，这意味着我们不止一次地通过了一个盒子。这意味着我们有一个循环，我们可以想要多少次就循环多少次。

因此，对于常规语言，如果我们可以创建一个任意长的字符串，我们可以将它划分为xyz，其中x是我们需要到达循环开始的字符，y是实际的循环，z是我们在循环后使字符串有效所需的任何东西。重要的是x和y的总长度是有限的。毕竟，如果长度大于盒子的数量，我们显然在执行此操作时穿过了另一个盒子，因此会有一个循环。

因此，在我们的平衡语言中，我们可以从写任意数量的左括号开始。特别是，对于任何给定的解析器，我们可以编写比方框更多的左括号，因此解析器无法判断有多少左括号。因此，x是一定数量的左括号，这是固定的。Y也是一定数量的左括号，并且可以无限增加。我们可以说z是一些右括号。

这意味着我们的解析器可能会识别一个包含43个左对和43个右对的字符串，但是解析器无法从包含44个左对和43个右对的字符串中辨别出来，这不是我们的语言，所以解析器无法解析我们的语言。

因为任何可能的常规解析器都有固定数量的框，所以我们总是可以编写比这个数量更多的左括号，然后通过pumping引理，我们可以以解析器无法分辨的方式添加更多的左括号。因此，平衡括号语言不能被正则解析器解析，因此不是正则表达式。

用外行的术语来说，这是一件很困难的事情，但基本上正则表达式中应该有一个非空子串，它可以重复你想要的次数，而整个新词对语言仍然有效。

在practice中，泵送引理不足以证明一种语言是正确的，而是作为一种通过矛盾进行证明的方式，并通过证明泵送引理对其不起作用来表明一种语言不适合语言类(规则或上下文无关)。