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 , then their shuffle is the language {w for some k 21, there exist k strings X1,..., xk in Li, and k strings yi,..., yk in L2 such that w = xi yi ... XX Yk }. Given NFAs that recognize two languages Li, 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 , then their shuffle is the language {w for some k 21, there exist k strings X1,..., xk in Li, and k strings yi,..., yk in L2 such that w = xi yi ... XX Yk }. Given NFAs that recognize two languages Li, L2, show how to construct another NFA that recognizes the language shuffle(L1, L2). Justify your constructions