Diseñe la máquina de Turing para invertir la string que consta de a y b

Tarea:
Nuestra tarea es diseñar una máquina de Turing para invertir una string que consta de a y b.

Ejemplos:

Input-1 : aabb
Output-1 : bbaa

Input-2 : abab
Output-2 : baba

Enfoque:
la idea básica es leer la entrada de derecha a izquierda y reemplazar Blank(B) con el alfabeto y reemplazar el alfabeto con ‘X’. Cuando leemos todas las letras a y b, reemplazamos todas las ‘X’ con Blank (B) y obtenemos la string requerida.

Entendamos este enfoque tomando el ejemplo “aabb”.

La primera tarea es que tenemos que llevar nuestro puntero a la derecha para que podamos leer nuestra string de derecha a izquierda. Para hacer eso, leemos todas las letras a y b de izquierda a derecha y cuando obtenemos el primer espacio en blanco (B), giramos el puntero hacia la izquierda y obtenemos el carácter más a la derecha.
Ahora habrá dos casos:
- El carácter que obtenemos es ‘a’.
- El carácter que obtenemos es ‘b’.
En este ejemplo, obtenemos nuestro primer carácter como ‘b’, es decir, el último carácter de aabb. Reemplazamos b con ‘X’ y hacemos Blank(B). Un espacio en blanco adicional se agregará automáticamente al final. Nuestra string se ve así:

Ahora tenemos que conseguir nuestro segundo personaje. Para eso, movemos el puntero de derecha a izquierda y lo movemos hasta obtener una ‘a’ o ‘b’ después de ‘X’. En este caso, obtenemos ‘b’. Ahora repetimos la misma tarea, es decir, reemplazamos esa ‘b’ con X y movemos el puntero desde esa posición hacia la derecha hasta que obtengamos un Espacio en blanco (B). Cuando obtenemos un espacio en blanco (B), lo reemplazamos con el carácter que obtenemos en este caso ‘b’ y un negro (B) se agregará automáticamente al final. Nuestra string se ve así:

Ahora tenemos que conseguir o el tercer personaje. Para eso, movemos el puntero de derecha a izquierda y lo movemos hasta obtener una ‘a’ o ‘b’ después de ‘X’. En este caso, obtenemos ‘a’. Ahora repetimos la misma tarea, es decir, reemplazamos esa ‘a’ con X y movemos el puntero desde esa posición hacia la derecha hasta obtener un Espacio en blanco (B). Cuando obtenemos un espacio en blanco (B), lo reemplazamos con el carácter que obtenemos en este caso ‘a’ y un negro (B) se agregará automáticamente al final. Nuestra string se ve así:

De manera similar, obtenemos nuestro último carácter, que es ‘a’, y realizamos la misma tarea que se describe en los pasos anteriores. Nuestra string se verá así:

Ahora hemos visto que hemos atravesado todos los cuatro caracteres y obtenemos el carácter en orden «bbaa», que es el reverso de «aabb», es decir, después de eliminar todas las ‘X’ obtenemos la string requerida.
Para eliminar todas las ‘X’, reemplazamos todas las ‘X’ con espacios en blanco (B), es decir, obtenemos 4 espacios en blanco (B) después de reemplazar ‘X’, que es equivalente a un solo espacio en blanco (B). Significa que tenemos nuestra string final.