5. (20 MARKS) Fix an alphabet E. For k > 0, define the k-interleave operation, lk as follows: lk : Ik x k 32k That is, lk takes as input two strings u, v E * with |u| = |V] = k and returns U1V1U2V2U3V3 ... UkVk, where u = U1U2 ... Uk and v = V1V2 ... Vk. We write ulk v for the k-interleave of u and v. For languages A, B C E*, we define Al B, the interleave of A and B, as follows: A B = {w E * for some k > 0, w = ulk v, where u E A and v E B} Prove that if A is regular, and B is regular, then AlB 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 MB.)