证明这种语言是否是可分辨的和可识别的

Question

如果L1和L2是语言，我们就有了一种新的语言

INTERLACE(L1, L2) = {w1v1w2v2 . . . wnvn | w1w2 . . . wn ∈ L1, v1v2 . . . vn ∈ L2}.

例如，如果abc ∈ L1和123 ∈ L2，那么a1b2c3 ∈ INTERLACE(L1, L2)

我如何证明INTERLACE是：

1. 可判定的？
2. 可辨认的？

我知道如何表达这种语言是正常的。我不太确定..。

以下是我的想法：

为了证明可判定语言类在操作下是封闭的，INTERLACE需要证明如果A和B是两种可判定语言，那么就有方法可以确定INTERLACE语言是否是可判定的。假设A，B可判定语言和M1，M2两种TM分别决定。

之后，我想我要说的是，如何构建识别语言的DFA？

Answer 1

L1和L2 可判定 ==> INTERLACE(L1, L2)可判定

Wikipedia引文：

递归(也可判定)语言的概念有两个等价的主要定义： ..。 2.递归语言是一种形式语言，存在图灵机，当出现任何有限输入字符串时，如果字符串在该语言中，则终止和接受，而停止和拒绝其他语言。

使用这一定义：

• 如果L1和L2是可判定的，则存在算法(或图灵机) M1和M2，因此：

- `M1` accepts all inputs `w ∈ L1` and rejects all inputs `w ∉ L1`. 
- `M2` accepts all inputs `v ∈ L2` and rejects all inputs `v ∉ L2`. 

​

• 现在让我们构建算法M，它接受所有输入x ∈ INTERLACE(L1, L2)，并拒绝所有输入x ∉ INTERLACE(L1, L2)，如下所示：

- Given an input `x1 x2 .. xn`. 
- If `n` is odd, reject the input, otherwise (`n` is even): 
- Run `M1` for the input `x1 x3 x5 .. xn-1`. If `M1` rejects this input, then `M` rejects its input and finishes, otherwise (`M1` accepted its input): 
- Run `M2` for the input `x2 x4 x6 .. xn`. If `M2` rejects this input, then `M` rejects its input, otherwise `M` accepts its input. 

​

可以很容易地证明M是INTERLACE(L1, L2)的决策算法，因此语言是可判定的。

L1和L2 可辨认 ==> INTERLACE(L1, L2)可识别

Wikipedia引文：

递归枚举语言有三个等价的定义(也是可识别的)： ..。 3.递归可枚举语言是一种形式语言，其存在图灵机(或其他可计算函数)，当在语言中显示任何字符串作为输入时，这种语言将停止并接受，但如果出现不以该语言表示的字符串，则可能会停止和拒绝或永远循环。与递归语言相比，递归语言要求图灵机器在所有情况下都停止运行。

这种证明与“可判定”财产的证明非常相似。

• 如果L1和L2是可识别的，则存在算法R1和R2，因此：

- `R1` accepts all inputs `w ∈ L1` and rejects _or loops forever_ for all inputs `w ∉ L1`. 
- `R2` accepts all inputs `v ∈ L2` and rejects _or loops forever_ for all inputs `v ∉ L2`. 

​

• 让我们构建算法R，它接受所有输入，x ∈ INTERLACE(L1, L2)，并永远拒绝或循环所有输入，x ∉ INTERLACE(L1, L2)：

- Given an input `x1 x2 .. xn`. 
- If `n` is odd, reject the input, otherwise (`n` is even): 
- Run `R1` for the input `x1 x3 x5 .. xn-1`. If `R1` loops forever, then `R` loops forever as well ("automatically"). If `R1` rejects this input, then `R` rejects its input and finishes, otherwise (if `R1` accepts its input): 
- Run `R2` for the input `x2 x4 x6 .. xn`. If `R2` loops forever, then `R` loops forever as well. If `R2` rejects this input, then `R` rejects its input, otherwise `R` accepts its input. 

​

实际上，你差一点就到了;)