Layman的术语是什么？
我看到了这个问题 ，并且对抽水论是什么感到好奇（ 维基百科没有多大帮助）。
我知道这基本上是一个理论上的certificate，一个语言要在某个阶级才是真的，但除此之外，我真的不明白。
任何人都会试图用非math家/科学博士能够理解的方式在一个相当细致的层面上解释它？
抽水引理是一个简单的certificate，表明一种语言是不规则的，这意味着一个有限状态机不能为它build立。 规范的例子是语言(a^n)(b^n) 。 这是一个简单的语言，它只是任意数量的s，随后是相同数量的b s。 所以string
ab aabb aaabbb aaaabbbb
等在语言中，但是
aab bab aaabbbbbb
等等都不是。
为这些例子build立一个FSM是很简单的：
这个将一直工作到n = 4。 问题是我们的语言没有对n进行任何约束，而有限状态机必须是有限的。 无论我添加到这台机器的状态有多less，有人可以给我一个input，其中n等于状态数加一，我的机器将失败。 所以如果有一台机器可以读取这种语言，就必须有一个循环来保持有限的状态数。 添加这些循环：
我们语言中的所有string都会被接受，但是有一个问题。 在前四个a之后，由于机器处于相同的状态，机器丢失了多lessainput的计数。 这意味着在四次之后，我可以添加尽可能多a s，而不添加任何b ，并且仍然得到相同的返回值。 这意味着string：
aaaa(a*)bbbb
(a*)表示任何数量的s，都将被机器接受，尽pipe它们显然不是全部在语言中。 在这种情况下，我们可以说string(a*)可以被抽出。 有限状态机是有限的而n不受限制的事实保证任何接受语言中所有string的机器都必须拥有这个属性。 机器必须在某个点上循环，并且在循环语言的时刻可以被泵送。 所以不能为这种语言build立有限状态机，语言不规则。
请记住， 正则expression式和有限状态机是等价的 ，然后用打开和closures的Html标签replacea和b ，这些标签可以embedded到对方中，你可以看到为什么不能用正则expression式来parsingHtml
这是一个旨在certificate给定的语言不能是某一类的设备。
让我们考虑平衡括号的语言（意思是符号（'和'）'，包括所有平常的含义的string，而不是）。 我们可以使用抽象引理来表明这是不规则的。
（一种语言是一组可能的string，parsing器是我们可以用来查看一个string是否在语言中的一种机制，所以它必须能够区分语言中的string或外部的string语言如果有一个能识别它的规则（或任何）分析器，语言是“规则的”（或“上下文无关”或“上下文相关的”或其他），区分语言中的string和不在语言。）
LFSR咨询提供了一个很好的描述。 我们可以将一个正则语言的parsing器作为一个有限的框和箭的集合，用箭头表示字符和连接它们的框（作为“状态”）。 （如果比这更复杂，那就不是一般的语言）。如果我们可以得到比string长的string，这意味着我们不止一次地经过了一个字符。 这意味着我们有一个循环，我们可以根据需要多次循环。
因此，对于一个正规的语言，如果我们可以创build一个任意长的string，我们可以将它分成xyz，其中x是我们需要到达循环开始的字符，y是实际循环，z是我们在循环之后需要使string有效。 重要的是x和y的总长度是有限的。 毕竟，如果长度大于盒子的数量，我们显然在做这件事的时候经过了另一个盒子，所以有一个循环。
所以，用我们平衡的语言，我们可以先写任意数量的左括号。 特别是，对于任何给定的parsing器，我们可以编写更多的左边栏，而不是有框，所以parsing器无法知道有多less左边栏。 因此，x是一些左侧包的数量，这是固定的。 y也是一些左撇子的数量，这可以无限增加。 我们可以说z是右边的一些数字。
这意味着我们可能有一串43个左撇子和43个右撇子被我们的parsing器识别，但是parsing器不能从44个左撇子和43个右撇子的string中知道，这不是我们的语言，parsing器不能parsing我们的语言。
由于任何可能的常规parsing器都有固定数量的框，所以我们总是可以编写更多的左边的文件，然后通过抽象的引理，我们可以添加更多的左边的文件，parsing器无法辨别。 因此，平衡括号语言不能被常规parsing器parsing，因此不是正则expression式。
从外行的angular度来说，这是一件困难的事情，但基本上，正则expression式中应该有一个非空的子string，可以按照您的意愿多次重复，而整个新字词仍然对该语言有效。
在实践中 ，抽象引理不足以certificate一种语言是正确的，而是作为通过矛盾进行certificate的一种方式，并通过显示抽象引理来显示一种语言不适合语言类别（Regular或Context-Free）不为它工作。
基本上，你有一个语言的定义（如XML），这是一种判断一个给定的string（“单词”）是否是该语言的成员的方法。
抽吸引理build立了一种方法，您可以从中select一个语言的“单词”，然后对其应用一些更改。 该定理指出，如果语言是规则的，这些变化应该产生一个仍然来自同一种语言的“词”。 如果你提出的这个词不在语言中，那么语言本来就不是一成不变的。
简单的抽象引理是用于规则语言的抽象引理，它是由有穷自动机描述的string集合等等。 有限自动化的主要特点是它只有一个有限的内存量，由它的状态来描述。
现在假设你有一个string，这个string被有限自动机所识别，并且长度足以“超过”自动化的内存，即在哪些状态必须重复。 然后有一个子string，其中子string开头的自动机状态与子string结尾的状态相同。 由于读取子string不会改变状态，所以可以将其删除或复制任意次数，而不需要使用自动机。 所以这些修改过的string也必须被接受。
对于上下文无关的语言，还有一个更复杂的抽象引理，你可以在string的两个地方删除/插入可以直观地看作匹配圆括号的内容。
按定义，常规语言是由有限状态机自动机识别的。 把它想象成一个迷宫：国家是房间，过渡是房间之间的单向走廊，有一个初始房间和一个出口（最后）房间。 正如名称“有限状态自动机”所说，有一定数量的房间。 每次你走过一条走廊，你都会记下写在墙上的字母。 如果你能find一个从最初的房间到最后一个房间的path，以正确的顺序穿过带有字母标记的走廊，就可以识别出一个单词。
抽吸引理说，有一个最大的长度（抽水长度），你可以在迷宫中漫步，而不必回到你以前走过的房间。 这个想法是因为只有很多不同的房间，你可以走过去，经过一定的时间，你必须离开迷宫或者穿过你的轨道。 如果你设法在迷宫中走的路程长于这个抽水长度，那么你正在绕道：在你的道路上插入一个（至less一个）周期，可以被移走（如果你想要穿越迷宫到识别更小的单词）或无限地重复（抽取）（允许识别超长单词）。
上下文无关的语言有一个类似的引理。 这些语言可以表示为被下推自动机接受的单词，这是有限状态自动机，它可以利用堆栈来决定执行哪个转换。 尽pipe如此，由于存在有限的状态数，所以上面所解释的直觉就可以inheritance，即使通过formsexpression的财产可能会稍微复杂一些 。
用一般的术语来说，我认为你说得对。 这是一个certificate技巧（实际上是两个），用于certificate语言不在某个类别中。
例如，考虑一个正则语言（正则expression式，自动机等），其中包含无限数量的string。 正如starblue所说的那样，在某一点上，由于string对于自动机来说太长，所以你的内存耗尽。 这意味着必须有一个string块，自动机不能告诉你有多less个副本（你在循环中）。 所以，在string中间的任何数量的子string的副本，你仍然在语言中。
这意味着如果你有一种没有这个属性的语言，也就是说，有一个足够长的没有子string的string，你可以重复任意次数并且仍然在语言中，那么这个语言是不规则的。
例如，采取这种语言L = a ^ nb ^ n
现在尝试为有些n的上述语言显示有限自动机
如果n = 1，则stringw = ab。 在这里，如果n = 2，我们可以制作一个有循环的有穷自动机，stringw = a ^ 2b ^ 2。 在这里，我们可以制作一个没有循环的有限自动机
如果n = p，则stringw = a ^ pb ^ p。 实质上，有限自动机可以假定为3个阶段。 第一阶段，需要一系列的投入，进入第二阶段。 同样从阶段2到阶段3.让我们称这些阶段为x，y和z
有一些观察1.绝对x将包含'a'和z将包含'b'。 现在我们要明确一下情况了。 y可能包含'a'唯一的情况b。 y只能包含'b'的情况c。 y可以包含“a”和“b”的组合。因此阶段y的有限自动机状态应该能够接受input“a”和“b”，并且不应该采用更多不可数的a和b。
- 如果阶段y只有一个“a”和一个“b”，那么就需要两个状态
- 如果需要两个“a”和一个“b”，则需要三个状态，带外循环，等等。
所以阶段y的devise是纯粹无限的。 我们只能通过放置一些循环来使其变得有限，如果我们放置循环，有限自动机可以接受超过L = a ^ nb ^ n的语言。 所以对于这种语言我们不能构造一个有穷自动机。 因此它是不规则的。
这不是一个解释，但它很简单。 对于一个nb ^ n我们的FSM应该build立在这样一种方式，b必须知道已经被parsing的a的数量，并且会接受相同的n个b。 FSM不能简单地做这样的事情。
