證明這個語言是否可判定和識別

Question

如果L1和L2語言中，我們有一個新的語言

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

例如，如果abc ∈ L1和123 ∈ L2，然後a1b2c3 ∈ INTERLACE(L1, L2)

我怎麼能證明INTERLACE是：

1. decidable？
2. 可識別？

我知道如何顯示這種語言是正常的。 對於可判定的，我不是很確定..

這裏就是我想：

要說明的是類可判定語言下操作INTERLACE關閉需要證明，如果A和B是兩個可判定語言，那麼有辦法找到INTERLACE語言是否可判定。假設A,B可判定語言和M1,M2兩個TM誰分別決定。

我想我不得不說如何構建識別語言的DFA？

Answer 1

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

引文從Wikipedia：

有一個遞歸的（也可判定）語言的概念兩個等價主要定義：
。 ..
2.遞歸語言是一種形式語言，其中存在一個圖靈機，與任何有限的輸入字符串一起，如果字符串在語言中，則停止並接受，否則停止並拒絕。

利用該定義：

• 如果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和L2recognizable ==>INTERLACE(L1, L2)識別

引文從Wikipedia：

有一個遞歸可枚舉（也識別）語言三個等價定義：
...
3.遞歸可枚舉語言是一種形式語言，其中存在一個圖靈機（或其他可計算函數），當以語言中的任何字符串作爲輸入提交時，它將停止並接受，但當呈現不屬於該語言的字符串時，它可以暫停和拒絕，或者永久循環。將其與遞歸語言進行對比，遞歸語言要求圖靈機在所有情況下都停止。

該證明與「可判定」財產的證明非常相似。

• 如果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接受其輸入。

---

附：你幾乎在那裏，實際上;）