theory - 用 Layman 的话来说，抽水引理是什么？

Question

我看到了这个问题，并且很好奇引理是什么（维基百科没有太大帮助）。

我知道这基本上是一个理论证明，为了使一种语言进入某个类别，它必须是正确的，但除此之外，我真的不明白。

有人愿意尝试以非数学家/计算机科学博士可以理解的方式在相当细化的层面上解释它吗？

Answer 1

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

ab
aabb
aaabbb
aaaabbbb

等等都在语言中，但是

aab
bab
aaabbbbbb

等等都不是。

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

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

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

aaaa(a*)bbbb

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

记住正则表达式和有限状态机是等价的，然后将aand替换b为可以相互嵌入的打开和关闭 Html 标签，您就会看到为什么不能使用正则表达式来解析 Html

Answer 2

它是一种旨在证明给定语言不能属于某个类别的设备。

让我们考虑平衡括号的语言（意思是符号'（'和'）'，包括所有在通常含义中平衡的字符串，没有一个不是）。我们可以使用抽水引理来证明这不是规则的。

（语言是一组可能的字符串。解析器是我们可以用来查看字符串是否属于该语言的某种机制，因此它必须能够区分该语言中的字符串或外部的字符串语言。如果有一个可以识别它的常规（或其他）解析器，区分该语言中的字符串和不在该语言中的字符串，则该语言是“常规”（或“无上下文”或“上下文敏感”或其他）语言。）

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

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

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

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

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

Answer 3

用外行的话来说是一件困难的事情，但基本上正则表达式中应该有一个非空子字符串，可以根据需要重复多次，而整个新词对该语言仍然有效。

在实践中，泵引理不足以证明语言正确，而是作为一种通过矛盾进行证明并通过显示泵引理来表明语言不适合语言类别（常规或无上下文）的方法不为它工作。

Answer 4

基本上，您有一种语言的定义（如 XML），这是一种判断给定字符串（“单词”）是否属于该语言的一种方法。

抽水引理建立了一种方法，您可以通过该方法从语言中选择一个“单词”，然后对其进行一些更改。该定理指出，如果语言是规则的，这些变化应该产生一个仍然来自同一种语言的“词”。如果您想出的词不在该语言中，那么该语言一开始就不可能是常规的。

Answer 5

简单的泵引理是常规语言的引理，它是由有限自动机描述的字符串集，等等。有限自动化的主要特征是它只有有限数量的内存，由其状态描述。

现在假设你有一个字符串，它被一个有限自动机识别，并且它的长度足以“超过”自动机的记忆，即其中的状态必须重复。然后有一个子串，其中自动机在子串开头的状态与子串末尾的状态相同。由于读取子字符串不会改变状态，因此它可能会被删除或复制任意次数，而自动机不会更聪明。所以这些修改后的字符串也必须被接受。

对于上下文无关语言，还有一个更复杂的抽水引理，您可以在其中删除/插入可能直观地被视为匹配括号的字符串中的两个位置。

Answer 6

By definition regular languages are those recognized by a finite state automaton. Think of it as a labyrinth : states are rooms, transitions are one-way corridors between rooms, there's an initial room, and an exit (final) room. As the name 'finite state automaton' says, there is a finite number of rooms. Each time you travel along a corridor, you jot down the letter written on its wall. A word can be recognized if you can find a path from the initial to the final room, going through corridors labelled with its letters, in the correct order.

The pumping lemma says that there is a maximum length (the pumping length) for which you can wander through the labyrinth without ever going back to a room through which you have gone before. The idea is that since there are only so many distinct rooms you can walk in, past a certain point, you have to either exit the labyrinth or cross over your tracks. If you manage to walk a longer path than this pumping length in the labyrinth, then you are taking a detour : you are inserting a(t least one) cycle in your path that could be removed (if you want your crossing of the labyrinth to recognize a smaller word) or repeated (pumped) indefinitely (allowing to recognize a super-long word).

There is a similar lemma for context-free languages. Those languages can be represented as word accepted by pushdown automata, which are finite state automata that can make use of a stack to decide which transitions to perform. Nonetheless, since there is stilla finite number of states, the intuition explained above carries over, even through the formal expression of the property may be slightly more complex.

Answer 7

In laymans terms, I think you have it almost right. It's a proof technique (two actually) for proving that a language is NOT in a certain class.

Fer example, consider a regular language (regexp, automata, etc) with an infinite number of strings in it. At a certain point, as starblue said, you run out of memory because the string is too long for the automaton. This means that there has to be a chunk of the string that the automaton can't tell how many copies of it you have (you're in a loop). So, any number of copies of that substring in the middle of the string, and you still are in the language.

This means that if you have a language that does NOT have this property, ie, there is a sufficiently long string with NO substring that you can repeat any number of times and still be in the language, then the language isn't regular.

Answer 8

例如，采用这种语言L = a ⁿ b ⁿ。

现在尝试为一些n可视化上述语言的有限自动机。

如果n = 1，则字符串w = ab。在这里，如果n = 2，字符串w = a ² b ² ，我们可以制作一个没有循环的有限自动机。在这里我们可以制作一个没有循环的有限自动机

如果n = p，则字符串w = a ^p b ^p。本质上可以假设一个有限自动机具有 3 个阶段。第一阶段，它需要一系列输入并进入第二阶段。同样从第 2 阶段到第 3 阶段。让我们将这些阶段称为x、y和z。

有一些观察

1. 肯定x将包含 'a' 而z将包含 'b'。
2. 现在我们必须清楚y：
   • case a : y可能只包含 'a'
   • case b : y可能只包含 'b'
   • case c : y可能包含 'a' 和 'b' 的组合

所以阶段y的有限自动机状态应该能够接受输入 'a' 和 'b' 并且它不应该接受更多不可数的 a's 和 b's。

1. 如果阶段y只取一个“a”和一个“b”，那么需要两个状态
2. 如果它需要两个“a”和一个“b”，则需要三个状态而没有循环，依此类推....

所以阶段y的设计纯粹是无限的。我们只能通过放置一些循环来使其有限，如果我们放置循环，有限自动机可以接受L = a ⁿ b ⁿ之外的语言。所以对于这种语言，我们不能构造一个有限自动机。因此它是不规则的。

Answer 9

这不是一个解释，但它很简单。对于 a^nb^n，我们的 FSM 应该以这样一种方式构建，即 b 必须知道已经解析的 a 的数量，并且将接受相同的 n 个 b。FSM 不能简单地做那样的事情。