小编the*_*dor的帖子

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