This is a challenge from the book Godel, Escher, Bach: An Eternal Golden Braid.

You are given the string MI and you need, by following the rules, change it to MU.


#1: If the last letter is I, you may add a letter U at the end.

#2: If you have Mx, you may duplicate the x, like: MIU becomes MIUIU, MUM becomes MUMUM, MU becomes MUU.

#3: If III occurs, you may replace it with U, like: MIII becomes MU, MUIIIU becomes MUUU, MIIII becomes MUI or MIU; The reverse is not aplicable, you cannot turn a U into III.

#4: If UU occurs, you may drop it, like: UUU becomes U, MUUUIIU becomes MIIU

You do not need to apply the rules whenever possible but only when you judge necessary.

An example:

Given MI
Rule 2: MII
Rule 2: MIIII
Rule 1: MIIIIU
Rule 3: MIUUI