(Igpay Atinlay.) Pig Latin is a simple word transformation that is popular among children, at least in the U.S. It involves rotating words, as in the example above. For this problem you are to investigate a simplified form of it. Well consider the alphabet {a, b}. First note that any string has a maximal prefix composed only of as. Call this the a-prefix. Note that every string x has a unique factorization as zw, where z is the a-prefix.

a) Let PL(zw) = wz, where z,w are as above. Show that a Mealy machine cannot compute PL. (Use the prefix property.)

b) Show how a one-tape Turing machine could compute PL. Suppose the input string has length n. Give a bound on the worst-case running time of your Turing machine, as a function of n. (A big-O result is acceptable.)

Does anyone know how to solve b)?