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

Question

如果L1和L2是语言,我们有一种新语言

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

例如,if abc ? L1和123 ? L2thena1b2c3 ? INTERLACE(L1, L2)

我怎样才能证明INTERLACE:

1. 可判定的？
2. 可识别？

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

这就是我的想法:

为了表明在操作中关闭可判定语言的类INTERLACE需要表明如果A和B是两种可判定的语言,那么有方法可以找到INTERLACE语言是否可判定.假设A,B可判定语言M1,M22 TM谁决定,分别.

在我想我必须说如何构建识别语言的DFA之后？

Answer 1

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

\n\n

引用自Wikipedia：

\n\n

\n

递归（也可判定）语言的概念有两个等效的主要定义：
\n ...
\n 2. 递归语言是一种形式语言，存在图灵机，当呈现任何有限输入字符串时，该图灵机，如果字符串是该语言，则停止并接受，否则停止并拒绝。

\n

\n\n

使用这个定义：

\n\n

\n

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

  \n\n
  \n
  • M1接受所有输入w \xe2\x88\x88 L1并拒绝所有输入w \xe2\x88\x89 L1。
  \n
  • M2接受所有输入v \xe2\x88\x88 L2并拒绝所有输入v \xe2\x88\x89 L2。
  \n
\n

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

  \n\n
  \n
  • 给定一个输入x1 x2 .. xn。
  \n
  • 如果n是奇数，则拒绝输入，否则 (n是偶数)：
  \n
  • 运行M1输入x1 x3 x5 .. xn-1。如果M1拒绝此输入，则M拒绝其输入并完成，否则（M1接受其输入）：
  \n
  • 运行M2输入x2 x4 x6 .. xn。如果M2拒绝该输入，则M拒绝其输入，否则M接受其输入。
  \n
\n

\n\n

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

\n\n

L1并且L2 可识别==>INTERLACE(L1, L2)可识别

\n\n

引用自Wikipedia：

\n\n

\n

递归可枚举（也可识别）语言有三个等效定义：
\n ...
\n 3. 递归可枚举语言是一种形式语言，存在图灵机（或其他可计算函数），该图灵机将停止并接受当提供该语言中的任何字符串作为输入时，但当提供不属于该语言的字符串时，可能会停止并拒绝或永远循环。与递归语言相比，递归语言要求图灵机在所有情况下都停止。

\n

\n\n

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

\n\n

\n

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

  \n\n
  \n
  • R1接受所有输入w \xe2\x88\x88 L1并拒绝或永远循环所有输入w \xe2\x88\x89 L1。
  \n
  • R2接受所有输入v \xe2\x88\x88 L2并拒绝或永远循环所有输入v \xe2\x88\x89 L2。
  \n
\n

• 让我们构建R接受所有输入x \xe2\x88\x88 INTERLACE(L1, L2)并拒绝或永远循环所有输入的算法x \xe2\x88\x89 INTERLACE(L1, L2)：

  \n\n
  \n
  • 给定一个输入x1 x2 .. xn。
  \n
  • 如果n是奇数，则拒绝输入，否则 (n是偶数)：
  \n
  • 运行R1输入x1 x3 x5 .. xn-1。如果R1永远循环，则R也永远循环（“自动”）。如果R1拒绝此输入，则R拒绝其输入并完成，否则（如果R1接受其输入）：
  \n
  • 运行R2输入x2 x4 x6 .. xn。如果R2永远循环，那么R也永远循环。如果R2拒绝该输入，则R拒绝其输入，否则R接受其输入。
  \n
\n

\n\n\n\n

PS实际上你已经快到了;)

\n