regular-language - 连接和联合 - 常规和上下文无关语言

Question

给定 L1 上下文无关的非正则语言。给定 L2 常规语言。

L1 U L2 =常规语言有可能吗？另外，L1*L2 = 常规语言有可能吗？

我认为第二个是不可能的。但我不确定。

如果上述陈述之一（或两者）为真，希望看到一个例子。

Answer 1

有可能L1 U L2=常规语言吗？

是的，可能。

一个简单的例子是：如果 L _{1是 L 2}的子集，那么L1 U L2将是正则 ( )，例如： L ₁ : { | 其中} 和=L2anbnn >= 0L2 = (a + b)*

有可能L1 * L2 =常规语言吗？

不，上下文无关和常规的连接将是上下文无关的（因为 L1 模式中的约束仍然存在于 中L1 * L2）。

_{添加参考：CS 273：上下文无关语言的闭包属性}

Answer 2

有可能L1 U L2=常规语言吗？

对的，这是可能的。但最好举个例子：

L1 = {0*1*}（常规）和L2 = {0^n1^n |n>=0}（无上下文）。

L = L1 U L2 = {0*1*}这是常规语言，但因为每种常规语言都是无上下文的。所以，我们可以说两者的结合总是产生上下文无关的语言。

有可能L1·L2=常规语言吗？

常规语言和上下文无关语言的连接总是会产生上下文无关语言。再看上面的例子：

L = L1·L2 = {(0*1*)·(0^n1^n) |n>=0}（上下文无关）。

如果例如其中一个L1or L2is ，它也可以是规则的Ø，L1·L2将导致Ø(regular)。但是既然，所有常规语言都是上下文无关的，Ø也是上下文无关的。

看看这个：极客的极客

Answer 3

是的，上下文无关和常规的连接将是常规的

取 L1= a^nb^n 这是 CFL 并取 L2 = Ø 这是常规的。

所以 L1.L2 = (a^nb^n).Ø = Ø 这是常规的

注意：对于两种语言的连接必须是正则的，必须至少有一种语言是正则的。