union - 两种非正则语言的结合是正则的吗？

Question

给定两种非常规语言，它们的联合是正规的吗？

另外，为什么 L = L1 ∪ L2 = {aibj | i,j >= 0} L1 的并集 = {aibj | i >= j} 和 L2 = {aibj |我
那么，L1 = {aibj | 的并集是什么？ i > j} 和 L2 = {aibj |我

Answer 1

问题 1:两种非正则语言的并集是正则的吗？

有时。常规的、上下文无关的、上下文敏感的、递归的和递归可枚举的语言在 union 下是封闭的。然而，deterministic context-free (DCFL) 语言接受 deterministic pushdown automaton (DPDA) 不是。标准证明是这样的。考虑以下语言:

L1 = {aibjck : i,j,k ≥ 0}
L2 = {aibicj : i,j ≥ 0}
L3 = {aibjcj : i,j ≥ 0}
L4 = {aibici : i ≥ 0}

第一种语言是常规语言，第二种和第三种 DCFL，第四种 not context-free .如果 DCFL 在联合下封闭，那么由于它在互补下封闭，语言

L4c = L1c ∪ L2c ∪ L3c

必须是 DCFL。同理，L4必须是 DCFL。这是矛盾的，因为L4甚至不是上下文无关的。因此，DCFL 在 union 下不是封闭的。最后，我们可以应用德摩根定律和 DCFL 在互补下闭合的事实来得出 DCFL 在相交下不闭合的结论。

相反，有些非正则语言的联合是正则的。您的第二个问题的答案表明，存在联合由 a*b* 给出的 DCFL 语言。 .

问题二:L1 = {aibj : i ≥ j}的并集和 L2 = {aibj : i < j} .

工会L1和 L2是 L3 = {aibj : i,j ≥ 0} .由于这是一个涉及集合的等式，我们必须证明 L1 ∪ L2 ⊆ L3和 L3 ⊆ L1 ∪ L2 .

如 u ∈ L1 ∪ L2然后 u ∈ L1或 u ∈ L2 .如 u ∈ L1然后 u = aibj哪里i ≥ j .如 u ∈ L2然后 u = aibj哪里i < j .通过三分法，u = aibj哪里i,j ≥ 0 .因此，u ∈ L3 .

如 u ∈ L3然后 u = aibj哪里i,j ≥ 0 .通过三分法，要么i ≥ j或 i < j .如果是前者，则u ∈ L1 .如果是后者，则 u ∈ L2 .因此，u ∈ L1 ∪ L2 .

问题三:L1 = {aibj : i > j}的并集和 L2 = {aibj : i < j}
工会L1和 L2是字符串集 aibj哪里i < j或 i > j .这相当于说i ≠ j通过三分法。因此，L1 ∪ L2 = {aibj : i ≠ j} .