有关常规语言泵引理的详细信息
我有一个关于常规语言的泵引理的小问题 - 它是否足以证明如果属于语言 L 的特定字符串无法泵送，那么该语言是不规则的？例如 - 如果我选择语言 L1 的形式为 a^nb^n (ab, aabb, aaabbb ...) 并且我表明字符串 aabb 无法被泵送并且仍然是 L1 的一部分，那么它是我可以立即得出 L1 不规则的结论吗？
干杯。
I have one small question about the pumping lemma for regular languages - is it good enough to show that if a specific string belonging to a language L can't be pumped, then the language is irregular? For example - if I choose language L1 being of the form a^nb^n (ab, aabb, aaabbb ...) and I show that the string aabb can't be pumped and still be a part of L1, then is it valid for me to immediately conclude that L1 is irregular?
Cheers.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
是的，这就是泵送引理的工作原理。它仅适用于证明语言不是规则的。对于正则语言来说，满足泵引理只是一个必要条件，而不是充分条件。
（注意：对于上下文无关语言和相应的泵引理也是如此）
Yes, that's how the pumping lemma works. It's only useful for proving languages to not be regular. Satisfying the pumping lemma is only a necessary but not a sufficient condition for a language being regular.
(Nota bene: Likewise for context-free languages and the respective pumping lemma there)
这还不足以证明单个有限长度的字符串不会泵送。对于严格的论证，您还必须证明示例字符串的长度大于语言的泵送长度。通常你假设一些泵送长度
p 存在，则构造一个比 p 长且无法泵送的字符串。
It's not quite sufficient to demonstrate that a single, finite-length string does not pump. For a rigorous argument, you'd also have to prove that length of your example string is greater than the pumping length of the language. Usually you assume that some pumping length
p exists, then construct a string longer than p that cannot be pumped.
是的，这就是它的工作原理，但要小心地显示字符串如何“无法泵送”
为此，您必须将 L 中的字符串 w 分解为子字符串 xyz 并显示 xy^1z 的某些版本，对于 int i i>=0 导致字符串不在 L 中，但仍被 DFA M 接受（因为 M 构建为接受 L），从而产生矛盾。
请注意，您无法选择 y 的位置，因此必须考虑它的 3 个可能位置。我认为这是关键。
Yes, this is how it works, but be careful in showing how a string "cannot be pumped"
To do that you have to break a string w in L, into substrings xyz and show that some versions of xy^1z, for int i i>=0 lead to strings not in L, but are still accepted by DFA M (for M built to accept L), arriving at a contradiction.
Note that you cannot pick the location of y and therefore must consider 3 possible positions of it. That's the key, in my opinion.
泵送引理说：
如果语言 A 是常规的 =>存在一个数字 p（泵送长度），其中，如果 s 是 L 中的任意字符串，则 |s| >= p，则 s 可以分为三块 s=xyz，满足以下条件：
证明某种语言 L 不规则的正确方法是假设 L 是规则的并尝试得出矛盾。
让我们尝试证明 L = {0n1n}|n>=0} 不是正则。
我们开始相反地假设 L 是正则的。
你可以把这种演示想象成一个游戏：
挑战者：他选择泵送长度p。你不能对此做任何推测。
你：现在轮到你了：选择代表语言不规则性的字符串“种类”。
假设该字符串的格式为 0p1p。
这一步的一个好技巧是尝试限制对手的下一步行动。
挑战者：他向您呈现一个形式为 0p1p 的字符串 s。
你：该吸奶了！如果你在上一步中正确选择了字符串的形式，你就可以做一些假设。
例如，在我们的例子中，我们知道子字符串 y 仅由 0 组成（至少有一个 0，因为 |y|>0），因为 |xy|<=p 并且第一个 p 元素是 0。
现在我们证明存在 i>=0 使得 xyiz 不在 L 中。例如，对于 i=2，字符串 xyyz 的 0 多于 1，因此不是 L 的成员这个案例是矛盾的。 => L 不是正则。
永远不要忘记证明为什么泵送的字符串不能是 L 的成员。
可能现在来帮助你已经太晚了，但其他人可能需要这种解释......也许 ^^
干杯。
The pumping lemma says:
If a language A is regular => there is a number p (pumping length) where, if s is any string in L such that |s| >= p, then s may be divided into three pieces s=xyz, satisfying the following condition:
The right way to show that a certain language L is not regular is to suppose L regular and try to reach a contradiction.
Lets try to demonstrate that L = {0n1n}|n>=0} is not regular.
We start assuming to the contrary that L is regular.
You can think about this kind of demonstration as a game:
Challenger: He choose the pumping length p. You cannot do any presumption on it.
You: Now it is your turn: choose the "kind" of string that represents the irregularity of the language.
Lets say that the string is in the form 0p1p.
A good tip in this step is to try to limit the adversary next move.
Challenger: He presents to you a string s in the form 0p1p.
You: It's time to pump! If you chose correctly the form of the string in your previous move, you can do some assumption.
In our case, for example, we know that the substring y consists only of 0s (at least one 0 because |y|>0), because |xy|<=p and first p-elements are 0s.
Now we show that it exists i>=0 such that xyiz is not in L. For example, for i=2 the string xyyz has more 0s than 1s and so is not a member of L. This case is a contradiction. => L is not regular.
Never forget to demonstrate why the pumped string cannot be a member of L.
Probably it is late to help you, but someone else may need this kind of explanation...maybe ^^
Cheers.