Prove if this language is allowed 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 INTERLACE :

• solvable?
• recognizable?

I know how to display this language regularly. For solvable, I'm not sure.

That's what I think:

To show that the class of resolvable languages ​​is closed during the INTERLACE operation, it is necessary to show that if A and B are two resolvable languages, then there is a method for determining whether the INTERLACE language is resolved. Suppose that A , B solvable languages, and M1 , M2 two TM that make decisions accordingly.

After I think I should say how to build a DFA that recognizes a language?

Answer 1

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

Link from Wikipedia :

There are two equivalent basic definitions of the concept of a recursive (also decidable) language:
...
2. A recursive language is a formal language for which there is a Turing machine that, when presenting any final input line, stops and accepts if the line is in the language and stops and rejects otherwise.

Using this definition:

• If L1 and L2 decidable, then there are algorithms (or Turing machines) M1 and M2 , 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 build an algorithm M that accepts all inputs x ∈ INTERLACE(L1, L2) and rejects all inputs x ∉ INTERLACE(L1, L2) as follows:

  • To enter x1 x2 .. xn .
  • If n is odd, reject the input, otherwise ( n equals):
  • Run M1 to enter x1 x3 x5 .. xn-1 . If M1 rejects this input, then M rejects its input and terminates, otherwise ( M1 accepted its input):
  • Run M2 to enter x2 x4 x6 .. xn . If M2 rejects this input, then M rejects its input, otherwise M accepts its input.

It is easy to prove that M is a solution algorithm for INTERLACE(L1, L2) ; therefore, the language is decidable.

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

Link from Wikipedia :

There are three equivalent definitions of a recursively enumerated (also recognizable) language:
...
3. A recursively enumerated language is a formal language for which there is a Turing machine (or other computable function) that will stop and be accepted when any string in the language is presented as input, but it can either stop, reject, or quote forever when The string representation is not in the language. Compare this to recursive languages ​​that require the Turing machine to stop in all cases.

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

• If L1 and L2 recognized, then there are algorithms R1 and R2 , so that:

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

• Let's build an algorithm R that takes all inputs x ∈ INTERLACE(L1, L2) and forever rejects or cycles for all inputs x ∉ INTERLACE(L1, L2) :

  • To enter x1 x2 .. xn .
  • If n is odd, reject the input, otherwise ( n equals):
  • Run R1 to enter x1 x3 x5 .. xn-1 . If R1 loops forever, then R also loops forever ("automatically"). If R1 rejects this input, then R rejects its input and terminates, otherwise (if R1 accepts its input):
  • Run R2 to enter x2 x4 x6 .. xn . If R2 loops forever, then R also hung forever. If R2 rejects this input, then R rejects its input, otherwise R accepts its input.

---

PS you were almost there, actually;)