我在大学工作，基本上说：
“证明非常规语言L = {0 ^ n 1 ^ n：n natural}没有无限的常规子语言 . ”
我通过矛盾证明了这一点 . 我基本上说有一种语言S是L的子语言，它是一种常用语言 . 由于S的可能正则表达式是0 *，1 *，（1 0）和（0o1） . 我检查每个语法并证明它们都不是语言L的一部分 .
但是，我怎么能证明任何非常规的上下文无关语言都不能包含任何常规的无限子语言？
我不想要证明本身，我只想指出正确的方向 .
L = {0 ^ n 1 ^ n：n natural}是非常规的无上下文 .
M = 2 * 3 *是无限规则的 .
N =L∪M是非常规的无上下文 . N包含M.
对于0 ^ n 1 ^ n语言，查看pumping lemma.可能是有 Value 的我认为当我学习它在a ^ nb ^ n语言中使用的泵浦引理时（同样的事情） . 泵浦引理可能有助于你的证据 .
您还可以考虑常规语言在补语，并集，交集和kleene星下关闭 .
那就是如果L1和L2是规则的那么：
L1 L2 (concatenation) is also regular. L1 n L2 is regular L1 U L2 is regular ¬L1 is regular L1* is regular
您可以通过使用其中一些规则来证明包含常规无限子语言的任何语言都是常规语言 .
你的直觉很好 . 这里有两件事 .
首先，几乎总是当问题采取“表明L不是常规/不是CF”的形式时，答案将涉及使用泵浦引理 . 同样地，当你得到一个类似“显示没有X ......”的问题时，简单的路径（几乎总是）将成为矛盾的证明 .
编辑：false语句，仅适用于上下文无关语言
因为你只想要提示（谢天谢地，因为我忘了自大学以来如何做校样），看看definition of a regular language以及它有什么属性 . 只是从那里看，我有足够的信息来证明这个陈述 .
5 回答
L = {0 ^ n 1 ^ n：n natural}是非常规的无上下文 .
M = 2 * 3 *是无限规则的 .
N =L∪M是非常规的无上下文 . N包含M.
对于0 ^ n 1 ^ n语言，查看pumping lemma.可能是有 Value 的我认为当我学习它在a ^ nb ^ n语言中使用的泵浦引理时（同样的事情） . 泵浦引理可能有助于你的证据 .
您还可以考虑常规语言在补语，并集，交集和kleene星下关闭 .
那就是如果L1和L2是规则的那么：
您可以通过使用其中一些规则来证明包含常规无限子语言的任何语言都是常规语言 .
你的直觉很好 . 这里有两件事 .
首先，几乎总是当问题采取“表明L不是常规/不是CF”的形式时，答案将涉及使用泵浦引理 . 同样地，当你得到一个类似“显示没有X ......”的问题时，简单的路径（几乎总是）将成为矛盾的证明 .
编辑：false语句，仅适用于上下文无关语言
因为你只想要提示（谢天谢地，因为我忘了自大学以来如何做校样），看看definition of a regular language以及它有什么属性 . 只是从那里看，我有足够的信息来证明这个陈述 .