Prove whether this language is decidable and recognizable

Question

If L1 and L2 are languages we have a new language

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

For example, if abc ∈ L1 and 123 ∈ L2, then a1b2c3 ∈ INTERLACE(L1, L2)

How can I prove that the INTERLACE is:

1. decidable ?
2. recognizable ?

I know how to show this language is regular. For decidable I am not so sure..

Here's what I think:

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.

After I think I have to say how to construct the DFA that recognize the language?

Answer 1

L1 and L2 decidable ==> INTERLACE(L1, L2) decidable

Citation from 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.

Using this definition:

• If L1 and L2 are decidable, then algorithms (or Turing machines) M1 and M2 exist, so that:

  • M1 accepts all inputs w ∈ L1 and rejects all inputs w ∉ L1.
  • M2 accepts all inputs v ∈ L2 and rejects all inputs v ∉ L2.

• Now let's construct algorithm M which accepts all inputs x ∈ INTERLACE(L1, L2) and rejects all inputs x ∉ INTERLACE(L1, L2), as follows:

  • Given an input x1 x2 .. xn.
  • If n is odd, reject the input, otherwise (n is even):
  • Run M1 for the input x1 x3 x5 .. xn-1. If M1 rejects this input, then M rejects its input and finishes, otherwise (M1 accepted its input):
  • Run M2 for the input x2 x4 x6 .. xn. If M2 rejects this input, then M rejects its input, otherwise M accepts its input.

One can easily prove that M is the decision algorithm for INTERLACE(L1, L2), thus, the language is decidable.

L1 and L2 recognizable ==> INTERLACE(L1, L2) recognizable

Citation from 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.

The proof is very similar to the proof of the 'decidable' property.

• If L1 and L2 are recognizable, then algorithms R1 and R2 exist, so that:

  • R1 accepts all inputs w ∈ L1 and rejects or loops forever for all inputs w ∉ L1.
  • R2 accepts all inputs v ∈ L2 and rejects or loops forever for all inputs v ∉ L2.

• Let's construct algorithm R which accepts all inputs x ∈ INTERLACE(L1, L2) and rejects or loops forever for all inputs x ∉ INTERLACE(L1, L2):

  • Given an input x1 x2 .. xn.
  • If n is odd, reject the input, otherwise (n is even):
  • Run R1 for the input x1 x3 x5 .. xn-1. If R1 loops forever, then R loops forever as well ("automatically"). If R1 rejects this input, then R rejects its input and finishes, otherwise (if R1 accepts its input):
  • Run R2 for the input x2 x4 x6 .. xn. If R2 loops forever, then R loops forever as well. If R2 rejects this input, then R rejects its input, otherwise R accepts its input.

---

P.S. you were almost there, actually ;)