Tuesday, October 21, 2008

Transformations

Given a set S={M,I,U} and the following transformation rules
1) xI -> xIU
2) Mx -> Mxx
3) III -> U
4) UU -> ignore, i.e. empty

  • The above rules can only be applied on complete strings and not partially.
  • x represents 'any' string
e.g. if given MU then you can get MUU.

Find out whether MI -> MU exists or not, if yes, what are the set of rules

No comments: