HQ7 [3 full pages, 6 + 4 = 10 points] For a language L, define Half2(L) = { y : there exists some string x such that |x|=|y| and xy is in L}.
(a) Prove that regular languages are closed under Half2 by showing how to construct an automaton for Half2(L) given an automata for L and proving its correctness.

Define an operation on binary strings fatten(w) = a string that inserts 0 after every symbol of w. For example, fatten(e) = 0, fatten(0) = 00, fatten(1) = 10,fatten(01) = 0010, etc.

(b) Show that regular languages are closed under FATTEN(L) = { fatten(w) : w in L }. Explicit construction of an automaton is not needed, but you need to justify the correctness of your approach. If you are constructing an automaton, then explain what do the states represent and explain the rationale behind the transition functions. Finally, justify why should the automaton accept the correct language.