非正则上下文无关语言和无限正则子语言
我为大学做了一份工作，基本上是这样说的：
“证明非常规语言 L={0^n 1^n : n natural} 没有无限的常规子语言。”
我用反证法证明了这一点。 我基本上说有一种语言 S，它是 L 的子语言，并且它是一种常规语言。 由于 S 可能的正则表达式为 0*、1*、(1+0)* 和 (0o1)*。 我检查了每个语法并证明它们都不是语言 L 的一部分。
但是，我如何证明任何非正则上下文无关语言不能包含任何正则无限子语言？
我并不想要证明本身，我只是想指出正确的方向。
I had a work for the university which basically said:
"Demonstrates that the non-regular language L={0^n 1^n : n natural} had no infinite regular sublanguages."
I demonstrated this by contradiction. I basically said that there is a language S which is a sublanguage of L and it is a regular language. Since the possible Regular expressions for S are 0*, 1*, (1+0)* and (0o1)*. I check each grammar and demonstrate that none of them are part of the language L.
However, how I could prove that ANY non regular context free language could not contain any regular infinite sublanguages?
I don't want the prove per se, I just want to be pointed in the right direction.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
L = {0^n 1^n : n natural} 是非常规上下文无关的。
M = 2*3* 是无限正则。
N = L∪M 是非常规上下文无关的。 N包含M。
L = {0^n 1^n : n natural} is non-regular context free.
M = 2*3* is infinite regular.
N = L∪M is non-regular context free. N contains M.
对于 0^n 1^n 语言，通过 Wikipedia 查看 泵浦引理。我想当我学习泵浦引理时，它被用在 a^nb^n 语言上（同样的事情。）泵浦引理可能会对你的证明有所帮助。
您还可以考虑常规语言在补码、并集、交集和小星号下是封闭的。
也就是说，如果 L1 和 L2 是正则的：
那么您可以通过使用其中一些规则来证明任何包含正则无限子语言的语言是正则的。
For the 0^n 1^n language, it might be valuable to look into the pumping lemma. I think when I learned the pumping lemma it was used on the a^n b^n language (same thing.) Possibly the pumping lemma might help in your proof.
Also you can consider that regular languages are closed under complement, union, intersection, and the kleene star.
That is if L1 and L2 are regular then:
It's possible that you could prove that any language that contains an regular infinite sublanguage is regular by using some of these rules.
你的直觉很好。 这里有两件事。
首先，几乎总是当问题采用“表明 L 不是正则/不是 CF”的形式时，答案将涉及使用泵引理。 类似地，当你遇到诸如“表明不存在 X ......”之类的问题时，简单的方法（几乎总是）将是反证法。
Your instincts are good. Two things here.
First, almost always when the question takes the form "show that L is not regular/not CF" the answer is going to involve using the pumping lemmas. Similarly, when you get a question like "show there are no X that ..." the easy route is (almost always) going to be a proof by contradiction.
编辑：错误陈述，仅适用于上下文无关语言
EDIT: false statement, only applies to context free language
既然你只是想要提示（谢天谢地，因为我从大学开始就忘记了如何做证明），请查看 常规语言的定义以及它具有哪些属性。 仅仅从那里我就得到了足够的信息来证明这一说法。
Since you just want hints (and thankfully so, since I forgot how to do proofs since college), look at the definition of a regular language and what properties it has. Just from looking there I had enough info to prove the statement.