2. (12 points) The Kleene star is an operation which, on input a set of strings A, outputs a new set of strings (that we call A*) which is defined recursively by Basis step. AEA" Recursive step: If u is in A'and v is in A, then uvE A" Note: uhen we write we mean the empty string (see definition on page 349) and then we write tw we mean the string concatenation of u and v. The formal definition is Definition 2 on page 350. For each of the following sets, give an example of a nonempty bit string that is an element of the set, and give an example of a nonempty bit string that is not an element of the set (make sure to label which is which). If it is not possible to give these two examples, say so and explain why (a) 1o1) (b) 0, 11,0001 (c) ou (d) f001)* n 001001) (e) 0* This erample might help you get started: {1}. This is the set defined recursively by E {1)', and if u E 1 and v E 1 then ue [1)*. Since there's only one element in {l), the only possible value for v is 1. In other words, as we recursively build up this set, ue start (at the basis step) with just {} . At the first application of the recursive step, the only choice for u is the one element that's been added to the set so far: u-. Therefore, tu-A1-1. So, at the end of this step, the set currently looks like {,1). At the next application of the recursive step, tE {1)" means u- or u-1; still, u-1. Thus, the possible values of uu are 1-1 and 11 . After adding these to the set being built, the set at this stage is {, 1,11). Continuing on, we see that {1)'-(, 1.11, 111, )! i E N) (where ue use the convention that, for any string x, X). Therefore, an erample of a nonempty bit string that is an element of this set is 1111. An erample of a nonempty bit string that is not an element of this set is 0