Se trata de una máquina de Turing generadora. Las cadenas generadas son las correspondientes a:
Lenguaje a generar: L={ anb2nan, con n mayor o igual a 0}
Cadenas generadas: abba#aabbbbaa#aaabbbbbbaaa#...#anb2nan
El alfabeto interno es {0,B} y el de salida {a,b,#} (siendo # el separador de cadenas).
El funcionamiento es el siguiente:
- La en la cinta 1 se van introduciendo 0's, uno por cada cadena (sería lo correspondiente a n>=0)
- Recorre los 0's de la cinta uno y escribe tantas a's como 0's hayan.
- Vuelve al inicio de la cinta 1 y la recorre anotando tantas b's como 0's hay.
- Al volver atrás en la cinta 1, vuelve a anotar una b por cada 0.
- Finalmente la recorre por última vez volviendo a anotar a's
- Vuelve al comienzo, donde se continua añadiendo 0's a la cinta 1 y continua el proceso
Finalmente, la M.T. queda como sigue:
