1. (10 points) The nonnegative powers of a string w are defined recursively as w0 = ? w1 = w wi+1 = wi ? w for i ? 0

Given a language L, consider the operation P ower(L) = {wn | w ? L and n ? 0}.

1. (10 points) The nonnegative powers of a string w are defined recursively as Given a language L, consider the operation Power(L) {wn I w E L and n > 0} a. For ? = {0, 1} and L = {0n1 | n > 0), give an example of a string that is in L* but not in Power(L) and justify your example (Therefore, we can conclude that L*-Power(L) is not always true. As an aside (not for credit), does equality ever hold?) b. Let E be an enumerator that enumerates an infinite language L. Consider the high-level description of an enumerator E'. E' = "Ignore the input: I. For i = 1, 2, 3 , repeat the following 2. Run E until it prints i strings (recording those strings) 3. For each string x in this collection of i strings 4. Print ?, z, x2 , x3 , . . . ,r'." True or False: L(E') Power(L). Bricfly justify your answer. recognizable languages is closed under the operation Power(). Briefly justify your answer. languages is closed under the operation Power(). Briefly justify your answer. c. True or False: this construction is sufficient evidence to prove that the class of infinite Turing- d. True or False: this construction is sufficient evidence to prove that the class of infinite Turing-decidable