computation-theory - 证明该语言是否可判定和可识别

Question

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

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

例如，如果 abc ∈ L1和 123 ∈ L2 ，然后 a1b2c3 ∈ INTERLACE(L1, L2)
我如何证明 INTERLACE是:

可决定的？

可识别？

我知道如何表明这种语言是规则的。
对于可决定的，我不太确定..

这是我的想法:

To show that the class of decidable languages is closed under operation INTERLACE need to show that if A and B are two decidable languages, then there is method to find if INTERLACE language is decidable. Suppose A, B decidable languages and M1, M2 two TM who decide, respectively.

之后我想我不得不说如何构建识别语言的DFA？

Answer 1

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

引自 Wikipedia :

There are two equivalent major definitions for the concept of a recursive (also decidable) language:
...
2. A recursive language is a formal language for which there exists a Turing machine that, when presented with any finite input string, halts and accepts if the string is in the language, and halts and rejects otherwise.

使用这个定义:

如 L1和 L2是可判定的，然后是算法(或图灵机)M1和 M2存在，所以:

M1接受所有输入 w ∈ L1并拒绝所有输入 w ∉ L1 .

M2接受所有输入 v ∈ L2并拒绝所有输入 v ∉ L2 .

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

给定一个输入 x1 x2 .. xn .

如 n为奇数，拒绝输入，否则(n 为偶数):

运行 M1对于输入 x1 x3 x5 .. xn-1 .如 M1拒绝此输入，然后 M拒绝其输入并完成，否则( M1 接受其输入):

运行 M2对于输入 x2 x4 x6 .. xn .如 M2拒绝此输入，然后 M拒绝它的输入，否则 M接受它的输入。

很容易证明 M是 INTERLACE(L1, L2) 的决策算法，因此，语言是可判定的。
L1和 L2 recognizable ==> INTERLACE(L1, L2)可识别的

引自 Wikipedia :

There are three equivalent definitions of a recursively enumerable (also recognizable) language:
...
3. A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any string in the language as input but may either halt and reject or loop forever when presented with a string not in the language. Contrast this to recursive languages, which require that the Turing machine halts in all cases.

该证明与“可判定”性质的证明非常相似。

如 L1和 L2是可识别的，然后是算法 R1和 R2存在，所以:

R1接受所有输入 w ∈ L1并拒绝或永远循环所有输入 w ∉ L1 .

R2接受所有输入 v ∈ L2并拒绝或永远循环所有输入 v ∉ L2 .

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

给定输入 x1 x2 .. xn .

如 n为奇数，拒绝输入，否则(n 为偶数):

运行 R1对于输入 x1 x3 x5 .. xn-1 .如 R1永远循环，然后 R也永远循环(“自动”)。如 R1拒绝此输入，然后 R拒绝其输入并完成，否则(如果 R1 接受其输入):

运行 R2对于输入 x2 x4 x6 .. xn .如 R2永远循环，然后 R也永远循环。如 R2拒绝此输入，然后 R拒绝它的输入，否则 R接受它的输入。

附言你快到了，实际上;)