regex - 非正则上下文无关语言和无限正则子语言

Question

我为大学做了一份工作，基本上说：

“证明非正则语言 L={0^n 1^n : n natural} 没有无限的正则子语言。”

我通过矛盾证明了这一点。我基本上说有一种语言 S 是 L 的子语言，它是一种常规语言。因为 S 可能的正则表达式是 0*、1*、(1+0)* 和 (0o1)*。我检查每个语法并证明它们都不是语言 L 的一部分。

但是，我如何证明任何非常规上下文无关语言都不能包含任何常规无限子语言？

我不想要证明本身，我只想指出正确的方向。

score 2 · Accepted Answer

对于 0^n 1^n 语言，研究抽水引理可能很有价值。我认为当我学习泵引理时，它被用于 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

通过使用其中一些规则，您可以证明任何包含常规无限子语言的语言都是常规的。

score 2 · Accepted Answer

L = {0^n 1^n : n natural} 是非常规上下文无关的。

M = 2*3* 是无限规则的。

N = L∪M 是非常规上下文无关的。N 包含 M。

score 1 · Accepted Answer

你的直觉很好。这里有两件事。

首先，几乎总是当问题采用“表明 L 不是正则/非 CF”的形式时，答案将涉及使用抽水引理。同样，当您收到诸如“表明没有 X ……”之类的问题时，简单的方法（几乎总是）将成为矛盾的证明。

score 0 · Accepted Answer

0

编辑：虚假陈述，仅适用于上下文无关语言

于 2009-03-19T01:19:40.553 回答

score 0 · Accepted Answer

由于您只需要提示（谢天谢地，因为我从大学起就忘记了如何做证明），请查看常规语言的定义及其具有的属性。只是从那里看，我有足够的信息来证明这一说法。

5 回答 5