Please only answer question 4b. Also please can you present your solution in a format of proof and answer. Thank you.

4. Pushing Strings Around (Part I). For this question, imagine finite binary strings consisting of 0 and 1. For instance, 00111 is a string. Order does not matter, so the string 1100 is considered equivalent to 0011. We will therefore always write Os before writing Is. For ease of notation, we will write (" when we mean exactly n zeros. Therefore, 0412 = 000011. These exponents do not indicate multiplication! Here are three rules for manipulating a string Rule 1: You may always replace a I with 11. To fix notation, we will write this as 1 - 11. Rule 2: You may replace 11 with a 0. More succinctly, 11 - 0. Rule 3: You may erase (0. We can write this as (0 _ null. The following sequence is legal: 0'13 = 000011 - 0011 , 11 5 0. Therefore, the string 0'18 has been transformed into the string 0, and we can say the trans- formation 0 12 -> 0 is possible. For any bean counters out there. we used Rule 2 once and Rule 3 twice. We did not use Rule 1 at all. Note that, for clarity, we have boldfaced and underlined the characters that are being operated on. a) Is the transformation 0'18 > null possible? (b) Let 0" 1" denote a string with a zeros followed by z ones. Is ()"1" > null possible