The shuffle of two strings w and x is the set of all strings that one

The shuffle of two strings w and x is the set of all strings that one can get by interleaving the positions of w and x in any way. More precisely, shuffle(w, x) is the set of strings z such that Each position of z can be assigned to w or x, but not both. The positions of z assigned to w form w when read from left to right. The positions of z assigned to x form x when read from left to right. For example, if w = 01 and x = 110, then shuffle(0l, 110) is the set of strings {01110,01101,10110,10101,11010,11001}. To illustrate the necessary reasoning, the third string, 10110, is justified by assigning the second and fifth positions to 01 and positions one, three, and four to 110. The first string, 01110 has three justifycations. Assign the first position and either the second, third, or fourth to 01. the other three to 110. We can also define the shuffle of languages, shuffle(L1- L2) to the the union over all pairs of strings, w from L1 and x from L2, of shuffle(w,x). What is shuffle(00,111)? What is shuffle(L1 L2) if L1 = L(0*) and L2 = {0^n1^n | n Ge 0}. Show that if L1 and L2 are both regular languages, then so is shuffle(L1, L2) Solution