Problem 1.1: Let L C {0, 1}* be the language defined recursively as follows: The empty string is in L. For any string x in L, the string 1x is also in L. For any strings x, y, z in L, the string OxOyoz is also in L. The only strings in L are those that can be obtained by the above rules. (a) Prove that L C {x {0,1}* : #0(x) is divisible by 3}, by using induction (for example, on the length of the string). Here, #o(a) denotes the number of O's in the string x. (As always, use strong induction.) (b) Prove that {x {0,1}* : #0(2) is divisible by 3} C L, by using induction. Problem 1.1: Let L C {0, 1}* be the language defined recursively as follows: The empty string is in L. For any string x in L, the string 1x is also in L. For any strings x, y, z in L, the string OxOyoz is also in L. The only strings in L are those that can be obtained by the above rules. (a) Prove that L C {x {0,1}* : #0(x) is divisible by 3}, by using induction (for example, on the length of the string). Here, #o(a) denotes the number of O's in the string x. (As always, use strong induction.) (b) Prove that {x {0,1}* : #0(2) is divisible by 3} C L, by using induction