证明这种语言是否可判定和可识别

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. 可识别？

我知道如何显示这种语言是正则的。 对于可判定的，我不太确定..

这是我的想法：

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。

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

  • 给定输入 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.

证明与'decidable'属性的证明非常相似。

• 如果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 也会永远循环 ("automatically")。如果 R1 拒绝此输入，则 R 拒绝其输入并完成，否则（如果 R1 接受其输入）：
  • 运行 R2 输入 x2 x4 x6 .. xn。如果 R2 永远循环，那么 R 也会永远循环。如果 R2 拒绝此输入，则 R 拒绝其输入，否则 R 接受其输入。

---

P.S。事实上，你快到了 ;)