A function f : N ! N will be called speedy if: • f(0) = 1, • For all n > 0, f(n) > f(0) + f(1) + f(2) + . . . + f(n - 1). (a) (2) Prove, by induction, that for any speedy function f, and all n 2 N, f(n)  2n. (b) (3) Prove that there are uncountably many speedy functions. (The proof will use a diagonal argument. Significant partial credit will be given for simply setting up the structure of the proof correctly.) 2. Give a regular expression for each of the languages over  = {a, b} defined below: (a) (1) The set of all strings that contain bab as a substring. (b) (1) The set of all strings that start and finish with different letters. (c) (1) The set of all strings that do not contain bbb as a substring. 3. Consider the language over  = {a, b} consisting of all the strings that contain no three consecutive a’s and no three consecutive b’s. For instance abbaaba is such a string, but ababbba is not. (a) (1) For 1  k  6 determine how many strings of length k there are in this language. (b) (1) Suggest a simple relationship that would allow the number of strings of length n+1 in the language to be computed if we knew that number of strings of length k for k  n. (c) (1) Prove that relationship.