(3) The MIU system. Consider the following rules for generating strings consisting of the letters M, I, and U (we use x and y to denote variable strings): (Given) You start with the string MI. (Rule 1) If you possess a string whose last letter is I, you can acquire the new string obtained by adding a U at the end. (Vx,xl 3xIU) (Rule 2) If you possess a string of the form Mx, you can acquire the new string Mxx. (Vx, Mx Mxx) (Rule 3) If you possess a string containing the sequence III, you can acquire the new string obtained by replacing III by U. (Vx, Vy, xIlly = xUy) (Rule 4) If you possess a string containing the sequence UU, you can acquire the new string obtained by deleting UU. (Vx, Vy, xUUy xy) For example, here is a circular derivation of MI (remember, all derivations must start with MI): Statement Justification (1) MI Given (2) MII from (1) by rule 2 (3) MIIII from (2) by rule 2 (4) MIMIU from (3) by rule 1 (5) MIUU from (4) by rule 3 (6) MI from (5) by rule 4. (Note that in going from step 4 to step 5 we could have applied rule 3 in a different way, to deduce MUIU.) The Problem: For each of the following strings, explain whether the above rules allow you to generate it (always starting from the given MI). If so, provide a step-by-step deriva- tion, with each step justified by one of the 4 rules. If not, prove that the string cannot be obtained (a) MIUIU (b) MUIIU (c) MU (Suggestion: start by playing with some examples, deriving some collection of deducible strings, to get used to the rules.) (3) The MIU system. Consider the following rules for generating strings consisting of the letters M, I, and U (we use x and y to denote variable strings): (Given) You start with the string MI. (Rule 1) If you possess a string whose last letter is I, you can acquire the new string obtained by adding a U at the end. (Vx,xl 3xIU) (Rule 2) If you possess a string of the form Mx, you can acquire the new string Mxx. (Vx, Mx Mxx) (Rule 3) If you possess a string containing the sequence III, you can acquire the new string obtained by replacing III by U. (Vx, Vy, xIlly = xUy) (Rule 4) If you possess a string containing the sequence UU, you can acquire the new string obtained by deleting UU. (Vx, Vy, xUUy xy) For example, here is a circular derivation of MI (remember, all derivations must start with MI): Statement Justification (1) MI Given (2) MII from (1) by rule 2 (3) MIIII from (2) by rule 2 (4) MIMIU from (3) by rule 1 (5) MIUU from (4) by rule 3 (6) MI from (5) by rule 4. (Note that in going from step 4 to step 5 we could have applied rule 3 in a different way, to deduce MUIU.) The Problem: For each of the following strings, explain whether the above rules allow you to generate it (always starting from the given MI). If so, provide a step-by-step deriva- tion, with each step justified by one of the 4 rules. If not, prove that the string cannot be obtained (a) MIUIU (b) MUIIU (c) MU (Suggestion: start by playing with some examples, deriving some collection of deducible strings, to get used to the rules.)