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

Question

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

另外，为什么 L = L ₁？L ₂ = {a ⁱ b ^j | i,j >= 0} L ₁ = {a ⁱ b ^j | 的并集 i >= j} 和 L ₂ = {a ⁱ b ^j | 我<j}？

那么，L ₁ = {a ⁱ b ^j |的并集是什么？i > j} 并且 L ₂ = {a ⁱ b ^j | 我<j}？

Answer 1

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

\n\n

有时。常规的、上下文无关的、上下文相关的、递归的和递归可枚举的语言在联合下是封闭的。然而，确定性下推自动机 (DPDA)接受的确定性上下文无关 (DCFL) 语言则不然。标准证明是这样的。考虑以下语言：

\n\n

L1 = {aibjck : i,j,k \xe2\x89\xa5 0}\nL2 = {aibicj : i,j \xe2\x89\xa5 0}\nL3 = {aibjcj : i,j \xe2\x89\xa5 0}\nL4 = {aibici : i \xe2\x89\xa5 0}

\n\n

第一种语言是常规语言，第二种和第三种是 DCFL，第四种不是上下文无关的。如果 DCFL 在并集下封闭，那么由于它在补集下封闭，因此该语言

\n\n

L4c = L1c \xe2\x88\xaa L2c \xe2\x88\xaa L3c

\n\n

必须是 DCFL。同样的道理，必须是DCFL。这是一个矛盾，因为它甚至不是上下文无关的。因此，DCFL 在联盟下并未关闭。最后，我们可以应用德摩根定律和 DCFL 在补集下闭合的事实得出 DCFL 在交集下不闭合的结论。L4L4

\n\n

相反，也有一些非正则语言，其并集是正则的。第二个问题的答案表明，有些 DCFL 语言的并集由 给出a*b*。

\n\n

问题2：和的并集L1 = {aibj : i \xe2\x89\xa5 j}L2 = {aibj : i < j}。

\n\n

和 的并集是。由于这是涉及集合的等式，因此我们必须证明和。L1L2L3 = {aibj : i,j \xe2\x89\xa5 0}L1 \xe2\x88\xaa L2 \xe2\x8a\x86 L3L3 \xe2\x8a\x86 L1 \xe2\x88\xaa L2

\n\n

\n
1. 如果那么或. 如果那么在哪里。如果那么在哪里。通过三分法，其中. 因此， 。u \xe2\x88\x88 L1 \xe2\x88\xaa L2u \xe2\x88\x88 L1u \xe2\x88\x88 L2u \xe2\x88\x88 L1u = aibji \xe2\x89\xa5 ju \xe2\x88\x88 L2u = aibji < ju = aibji,j \xe2\x89\xa5 0u \xe2\x88\x88 L3
\n
2. 如果那么在哪里。通过三分法，要么要么。如果是前者，那么. 如果是后者，那么. 因此，。u \xe2\x88\x88 L3u = aibji,j \xe2\x89\xa5 0i \xe2\x89\xa5 ji < ju \xe2\x88\x88 L1u \xe2\x88\x88 L2u \xe2\x88\x88 L1 \xe2\x88\xaa L2
\n

\n\n

问题3：和 的并集L1 = {aibj : i > j}L2 = {aibj : i < j}

\n\n

和的并集是其中或的字符串集合。这相当于按三分法说。所以，。L1L2aibji < ji > ji \xe2\x89\xa0 jL1 \xe2\x88\xaa L2 = {aibj : i \xe2\x89\xa0 j}

\n