Problem 6. [20 points] a. If L is any language, then max(L) = {w w is in L and there is no nonempty string y such that wy is in L}. Given a DFA that recognizes a language L, show how to construct another DFA that recognizes the language max(L). b. If L1, L2, are any two languages over an alphabet E, then their shuffle is the language { w for some k 21, there exist k strings x1,..., xk in Li, and k strings y1,..., yk in L2 such that w = xi yi ... XK Yk }. Given NFAs that recognize two languages L1, L2, show how to construct another NFA that recognizes the language shuffle(L1, L2). Justify your constructions. Problem 6. [20 points] a. If L is any language, then max(L) = {w w is in L and there is no nonempty string y such that wy is in L}. Given a DFA that recognizes a language L, show how to construct another DFA that recognizes the language max(L). b. If L1, L2, are any two languages over an alphabet E, then their shuffle is the language { w for some k 21, there exist k strings x1,..., xk in Li, and k strings y1,..., yk in L2 such that w = xi yi ... XK Yk }. Given NFAs that recognize two languages L1, L2, show how to construct another NFA that recognizes the language shuffle(L1, L2). Justify your constructions