Problem 1. Let S denote the collection of all binary strings that have length at least one, begin with 0 (when reading left to right), and are such that each occurrence of 0 in the string is followed by a block of either one or two consecutive ls. (For example, 011011101 is not allowed, because the second zero is followed by three consecutive ls.) (a) Find a decomposition of S using only finite sets, disjoint unions, unambiguous concatena- tions, and unambiguous * operations. (You do not have to use every available operations.) (b) We declare the weight of a binary string to be its length and we let s(x) denote the generating function for S. Find a simplified rational expression for s(x). Problem 1. Let S denote the collection of all binary strings that have length at least one, begin with 0 (when reading left to right), and are such that each occurrence of 0 in the string is followed by a block of either one or two consecutive ls. (For example, 011011101 is not allowed, because the second zero is followed by three consecutive ls.) (a) Find a decomposition of S using only finite sets, disjoint unions, unambiguous concatena- tions, and unambiguous * operations. (You do not have to use every available operations.) (b) We declare the weight of a binary string to be its length and we let s(x) denote the generating function for S. Find a simplified rational expression for s(x)