用抽引理证明语言不规则
来证明以下语言不规则
我试图使用泵引理L= { a^ib^j | a^ib^j | 。 i^2> j}
对此有什么建议吗？我完全被困住了。
谢谢。
I am trying to prove that the following language is not regular using the pumping lemma
L= { a^i b^j | i^2 > j}
Any tips on this? I am completely stuck.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
泵送引理说：
如果语言 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.
If you have any doubt, feel free to ask :)
Cheers.
对于上面的答案，“泵引理说：如果语言 A 是正则的 => 有一个数字 p（泵长度），其中，如果 s 是 L 中的任何字符串，使得 |s| >= p，则 s可以分为三块 s=xyz，满足以下条件：”
你的意思是“如果语言 L 是正则的”
另外，三个条件
1. 对于每个 i>=0，xy^iz 在 L 中
2. |y|>=0
3. p>=|xy|
第二个应该只是 |y| > 0 不 >=
To the above answer, "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:"
You mean "If a language L is regular"
Also, the three conditions
1. xy^iz is in L for each i>=0
2. |y|>=0
3. p>=|xy|
The second should be just |y| > 0 not >=
假设您选择字符串：
a^2b^5
aabbbbb。这是语言中的。
现在你的对手可以选择 XYZ。
他们的选择：
1.) X(空)Y(一些a)
2.) X(一些a)Y(一些a和一些b)
3.) X(some a's)Y(some a's)
根据他们可能的选择，您使用 Y^i 来泵送 Y，其中 i 是您选择的任意数字。
假设他们选择 1。)
X(-)Y(a)Z(abbbbb)
如果你“泵” Y^i 选择 i = 0。新字符串变为 abbbbb。这不是语言中的。
对对手的每个可能选择重复此操作，如果您可以以产生不属于语言 L 的字符串的方式提高 Y，那么您就成功证明了该语言不是正则语言。
Say you choose the string:
a^2b^5
aabbbbb. Which is in the language.
Now your opponent can choose XYZ.
Their options:
1.) X(empty)Y(some a's)
2.) X(some a's)Y(some a's and some b's)
3.) X(some a's)Y(some a's)
Based on their possible choices, you pump up Y using Y^i where i is an arbitrary number of your choice.
Say they choose 1.)
X(-)Y(a)Z(abbbbb)
If you "pump" up Y^i choosing i = 0. The new string becomes abbbbb. Which is not in the language.
Repeat this for each possible choice of the opponent, if you can pump up Y in a way that produces a string that is not in the language L, then you've succeeded in proving that the language is not regular.