计算理论 - 对上下文无关语言使用泵引理
我正在复习计算理论课程的笔记，但我无法理解如何完成某个证明。问题是：
A = {0^n 1^m 0^n | n>=1, m>=1} Prove that A is not regular.
很明显，必须使用泵引理来实现这一点。所以，我们有
- |vy| >= 1
- |vxy| <= p（p 是泵浦 length, >= 1)
- uv^ixy^iz 存在于 A 中，对于所有 i >= 0
尝试考虑选择正确的字符串似乎有点不确定。我在想 0^p 1^q 0^p，但我不知道我是否可以隐晦地制作 aq，并且由于 u 没有界限，这可能会使事情变得不守规矩..
那么，人们会如何做呢？ ？
I'm reviewing my notes for my course on theory of computation and I'm having trouble understanding how to complete a certain proof. Here is the question:
A = {0^n 1^m 0^n | n>=1, m>=1} Prove that A is not regular.
It's pretty obvious that the pumping lemma has to be used for this. So, we have
- |vy| >= 1
- |vxy| <= p (p being the pumping
length, >= 1) - uv^ixy^iz exists in A for all i >= 0
Trying to think of the correct string to choose seems a bit iffy for this. I was thinking 0^p 1^q 0^p, but I don't know if I can obscurely make a q, and since there is no bound on u, this could make things unruly..
So, how would one go about this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您使用适用于常规语言的泵引理的定义，而不是适用于 CFG 的定义，事情会简单得多。任何正则字符串 s = xyz 必须满足的三个条件是：
使用这三个条件再次尝试使用 0^p1^q0^p。
提示：因为我们有 0^p，所以 y 将仅由 0 组成。因此，当我们“输入”更多 y（考虑 xyyz）时，我们将不会得到该语言中的字符串。
It'll be much simpler if you use the definition of the pumping lemma applying to regular languages, not the one applying to CFGs. The three conditions that any regular string s = xyz must have are:
Try using 0^p1^q0^p again using these three conditions.
Hint: Because we have 0^p, y will only consist of 0's. Therefore, when we "pump in" more y's (consider xyyz), we will not get a string in the language.
您使用了错误的泵引理... A 在这里是上下文无关的，但它不规则。
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
这应该向您展示引理需要...如果你从这个开始，你可能会找到答案。如果没有，请告诉我，我将编辑我的答案以给您一些提示。
You're using the wrong pumping lemma... A is context-free here, but it is not regular.
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
That should show you the lemma you need... If you start with that, you might come up with an answer. If not, let me know and I'll edit my answer to give you a few hints.
我会在没有引理的情况下解决它：
- 考虑 h(a)，其中 h(1)=1 h(2)=0 h(0)=0。对您的语言应用 h^-1，然后与 0^*1^2^ 相交，得到语言 0^n1^m2^n。
- 现在使用 h'(a)，其中 h'(0)=a，h'(1)=epsilon，h'(2)=b。你会得到一个不规则的^nb^n。
为什么这更容易？因为学会了这些基本技巧之后你就可以很容易地解决这个问题。
至于引理：
- 您将需要 A 中单词的任何子字符串用作子字符串时都会破坏您的语言。我可以看到 6 种情况（从一开始只有 0，从一开始就是 0，后面跟着 1，等等...）
正如其他已经添加的那样，您不需要 CF 引理。 CF引理通常用于表明一种语言不是CF。
I would solve it without the lemma:
- Consider h(a) where h(1)=1 h(2)=0 h(0)=0. Applying h^-1 on your language and then intersection with 0^*1^2^ give you the language 0^n1^m2^n.
- Now use h'(a) where h'(0)=a, h'(1)=epsilon, h'(2)=b. You get a^nb^n which is not regular.
Why is this easier? Because after learning this basic tricks you can very easily solve this problems.
As for the lemma:
- You will need that any substring of a word in A when used as the substring ruins you language. There are 6 cases which I can see (Only 0s from the start, 0s from the start folllowed by 1, etc...)
As other already added, you don't need the CF-lemma. The CF-lemma is used to show a language is not CF usually.