Pushing Strings Around (Part I). For this question, imagine nite 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 0n when we mean exaclty 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 1 with 11- To x notation, we will write this as 1 1> 11. Rule 2: You may replace 1] with a U. More succinctly, 11 2) 0. Rule 3: You may erase 00. We can write this as 00 3> null. The following sequence is legal: 0412 =m00113; @113) EA 0. Therefore, the string 0'412 has been transformed into the string 0, and we can write 0'12 > 0. 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) Prove or disprove 0313 > null. (b) Let 0"1\" denote a string with n zeros followed by n ones. Prove or disprove 0" l\" > null. (c) What can you say about Oml"? Pushing Strings Amend (Part II). Pie-acquaint yourself with Part I. Rule 3 is the same, but there are some new ones: Rule 3: 00 Jl null. Rule 4: 1 i) 000. Rule 5: o 3+ 111. Rule 6: 11 \"> 00. (a) Prove that. Rule 4 is a consequence of Rules 13. (b) Prove that Rule 1 cannot be derived from Rules 36. (c) Prove that 0"1" > null is possible using only Rules 36