The following are the copies of the problems

4. Let X = {aa, bb} and Y = {?, b, ab}.?

a) List the strings in the set XY. ?

b) How many strings of length 6 are there in X* ??

c) List the strings in the set Y* of length three or less.

d) List the strings in the set X*Y* of length four or less.

5. Let L be the set of strings over {a, b} generated by the recursive definition?

i) Basis: bL. (the E is the Element)

?ii) Recursive step: if u is in L then ubL, uabL, and ubaL, and buaL.?

iii) Closure: a string v is in L only if it can be obtained from the basis by a finite number of iterations of the recursive step.

a) List the elements in the set L0, L1, and L2.?

b) Is the string bbaaba in L? If so, trace how it is produced. If not, explain why not.

c) Is the string bbaaaabb in L? If so, trace how it is produced. If not, explain why not.

6. Give a recursive definition of the set of strings over {a, b} that contain at least one b and have even number of as before the first

b. For example, bab, aab, and aaaabababab are in the set, while aa, abb are not.