两种非常规语言的结合可以正常吗？

Question

鉴于两种非常规语言，它们的联合是否正常？另外，为什么why1 = {a ⁱ b ^j | i> = j}和𝐿2= {a ⁱ b ^j | i = 0是𝐿=𝐿1∪𝐿2= {𝑎∗𝑏∗}？那么{a ⁱ b ^j | i> j}和𝐿2= {a ⁱ b ^j | i

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。尽管L4c与上下文无关，但它是

not DCFL。因此，DCFL不会在联合下关闭。我们可以应用德摩根定律和补正封闭DCFL的事实得出DCFL在交叉点不封闭的事实。
问题2：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的格式均为a*b*，因此u ∈ L3。
如果为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}。