-----------------------------------

sockoo

Tue May 17, 2005 11:59 am


Brain Boggling

-----------------------------------

This boggles my mind .. i wanna see if anyone else is able to figure this out ... 

Given the following rules, determine if the string MU is derivable from the string MI. 
Rule 1: If you generate a string whose last letter is I, you may add on a U to the end

Rule 2: If you have Mx. Then you may generate Mxx such that from MIU you would get MIUIU or from MIIIU get MIIIUIIIU.

Rule 3: If III occurs you may replace it with a U

Rule 4: If UU occurs inside a string you may drop it.

*must display the process by which a solution was found. *


-----------------------------------

Delos

Tue May 17, 2005 2:12 pm



-----------------------------------

Yes, it is possible, just did it.  The trick is to get an odd number of I's after the M (but not just 1!).  I'm not sure if this is supposed to be a comp sci question, but it probably can be done w/ OOT anyhow.