5. (20 MARKS) Fix an alphabet . For k > 0, define the k-interleave operation, as follows: : * x * 2 That is, lk takes as input two strings , E E with lul = lvl = k and returns 1914202430... , where = ty... and v = t... We write for the l-interleave of u and v. For languages A, B C , we define AB, the interleave of A and B as follows: AB= { we' for some k > 0, W = 0, where u E A and v EB) Prove that if A is regular, and B is regular, then Al B is regular. This means that the regular languages are closed under the interleave operation. (HINT: Build a machine M that recognizes Al B from machines MA and MB that recognize A and B, respectively. M will need to "interleave the executions of MA and M .)