外行人的抽水引理是什么? [英] What is the Pumping Lemma in Layman's terms?
问题描述
我看到了
这将一直工作到 n=4.问题是我们的语言没有对 n 施加任何限制，而且有限状态机必须是有限的.无论我向这台机器添加多少状态，有人可以给我一个输入，其中 n 等于状态数加 1，我的机器将失败.因此，如果可以构建一台机器来读取这种语言，那么在某处必须有一个循环来保持状态数量有限.添加这些循环后:
我们语言中的所有字符串都将被接受，但有一个问题.在前四个 a 之后，机器失去了输入了多少 a 的计数，因为它保持在相同的状态.这意味着在四个之后，我可以在字符串中添加任意数量的 a ，而无需添加任何 b ，并且仍然获得相同的返回值.这意味着字符串:
aaaa(a*)bbbb用 (a*) 表示任意数量的 a ，即使它们显然不是全部在语言中，也会被机器接受.在这种情况下，我们会说字符串 (a*) 的部分可以被抽空.有限状态机是有限的且 n 是无界的，这一事实保证了任何接受语言中所有字符串的机器都必须具有此属性.机器必须在某个时刻循环，而在它循环的那一刻，语言可以被泵送.因此无法为该语言构建有限状态机，并且该语言不是正则的.
记住正则表达式和有限状态机是等价的，然后替换a 和 b 带有可以相互嵌入的打开和关闭 Html 标签，您可以看到为什么 无法使用正则表达式解析Html
I saw this question, and was curious as to what the pumping lemma was (Wikipedia didn't help much).
I understand that it's basically a theoretical proof that must be true in order for a language to be in a certain class, but beyond that I don't really get it.
Anyone care to try to explain it at a fairly granular level in a way understandable by non mathematicians/comp sci doctorates?
The pumping lemma is a simple proof to show that a language is not regular, meaning that a Finite State Machine cannot be built for it. The canonical example is the language (a^n)(b^n). This is the simple language which is just any number of as, followed by the same number of bs. So the strings
ab
aabb
aaabbb
aaaabbbb
etc. are in the language, but
aab
bab
aaabbbbbb
etc. are not.
It's simple enough to build a FSM for these examples:
This one will work all the way up to n=4. The problem is that our language didn't put any constraint on n, and Finite State Machines have to be, well, finite. No matter how many states I add to this machine, someone can give me an input where n equals the number of states plus one and my machine will fail. So if there can be a machine built to read this language, there must be a loop somewhere in there to keep the number of states finite. With these loops added:
all of the strings in our language will be accepted, but there is a problem. After the first four as, the machine loses count of how many as have been input because it stays in the same state. That means that after four, I can add as many as as I want to the string, without adding any bs, and still get the same return value. This means that the strings:
aaaa(a*)bbbb
with (a*) representing any number of as, will all be accepted by the machine even though they obviously aren't all in the language. In this context, we would say that the part of the string (a*) can be pumped. The fact that the Finite State Machine is finite and n is not bounded, guarantees that any machine which accepts all strings in the language MUST have this property. The machine must loop at some point, and at the point that it loops the language can be pumped. Therefore no Finite State Machine can be built for this language, and the language is not regular.
Remember that Regular Expressions and Finite State Machines are equivalent, then replace a and b with opening and closing Html tags which can be embedded within each other, and you can see why it is not possible to use regular expressions to parse Html
这篇关于外行人的抽水引理是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
