5

如果 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？

4

1 回答 1

2

L1可L2 判定==>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并且L2 可识别==>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接受其输入。

PS你几乎在那里，实际上;）

于 2017-04-01T21:33:15.443 回答