regular-language - 两个（不规则）上下文无关语言的联合结果是规则语言？

Question

给定 L1 和 L2（不规则）上下文无关语言 - L1 U L2 是否可能是规则的？

我知道这是可能的，但我找不到一个例子来说明这一点。很想得到一些帮助。

Answer 1

两个 CFL 的联合可以是规则的吗？

给定和上下文无关（但不是常规）语言，两者的结合是否有可能是常规的？L1L2L1 ∪ L2

是的可能！

假设，第一语言 L ₁是：

L ₁ : { | 其中}anbmn = m

语言 L ₁是 CFL 但不是常规语言。_{L 1}语言的 另一种书写方式是. 我认为这是在任何正式语言教科书中都可以找到的 CFL 最狡猾的例子之一。anbn

第二语言 L ₂是：

L ₂ : { | 其中}anbmn ≠ m

L ₂再次是 CFL，但不是常规的。基本上 L _{2是 L 1}的补语.

现在，L ₁和 L ₂的并集是：

大号：{ | 和值没有限制}anbmnm

Language L=是一种正则语言， is的正则表达式。L1 ∪ L2La*b*

所以提示是补码 CFL 的联合是规则的。

注意：上下文无关语言在联合操作下是封闭的，因此两个 CFL 的联合始终是 CFL（可以是常规语言，因为常规语言类是 CFL 类的子集），但它不能是非 CFL，例如 CSL .

在评论的基础上添加：

两个 CFL 的交点可以是规则的吗？

给定和上下文无关（但不是常规）语言，两者的交集是否有可能是常规的？L1L2L1 ∩ L2

是的可能！

假设，第一语言 L ₁是：

L ₁ : { | 其中}anbmn = m

第二语言 L ₂是：

L ₂ : { | 其中}anbmn <= 3 or n ≠ m

Language L= =是一个有限集，因此也是一个常规集。L1 ∩ L2{ab, aabb, aaabbb}