两种非常规语言的结合是否正常？

Question

考虑到两种非常规语言，它们的联合是否正常？

同样，为什么L = L ₁∪L ₂ = {a ⁱ b ^j | i，j> = 0} L ₁的联合= {a ⁱ b ^j | i> = j}和L ₂ = {a ⁱ b ^j |我

然后，L ₁的联合是什么？= {a ⁱ b ^j | i> j}和L ₂ = {a ⁱ b ^j |我

Answer 1

问题1：两种非常规语言的结合是否正常？

有时。常规，无上下文，上下文敏感，递归和递归可枚举的语言在联合下关闭。但是，deterministic context-free（DPDA）接受的deterministic pushdown automaton（DCFL）语言不是。标准证明是这样的。考虑以下语言：

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不会在联合下关闭。最后，我们可以应用De Morgan定律和DCFL在互补条件下封闭的事实得出DCFL在交叉点不封闭的事实。

相反，有些非常规语言的联合是常规的。第二个问题的答案表明，有些DCFL语言的联合由正则表达式a*b*描述。

问题2：L1 = {aibj : i ≥ j}和L2 = {aibj : i < j}的并集。]

L1和L2的并集是L3 = {aibj : i,j ≥ 0}。由于这是一个涉及集合的等式，因此我们必须显示L1 ∪ L2 ⊆ L3和L3 ⊆ L1 ∪ L2。

1. 如果是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。
2. 如果为u ∈ L3，则为u = aibj，其中i,j ≥ 0。通过三分法，i ≥ j或i < j。如果是前者，则为u ∈ L1。如果是后者，则u ∈ L2。因此，u ∈ L1 ∪ L2。

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

L1和L2的并集是字符串aibj的集合，其中i < j或i > j。这相当于用三分法说i ≠ j。因此，L1 ∪ L2 = {aibj : i ≠ j}。