En la cadena de entrada sólo recibiremos cadenas de 0´s, recorreremos el primer cabezál hasta encontrar un blanco (B), mientras por cada 0 que leamos escribiremos una (a), en la cinta de salida. Luego volvemos a recorrer la cadena hacia atras escribiendo 2 b´s, por cada 0 que encontramos, para ello utilizamos los estados q1 y q2. Para finalizar, cuando encontremos un blanco (B), volceremos a escribir en la cinta de salida a`s hasta encontrarnos al la derecha de la cadena de entrada una B, (blanco). Por finalizar escribiremos una almoadilla (#), en la cinta de salida para dejarla preparada para generar la siguiente cadena.
Aquí dejamos la tabla de transiciones de esta M.T. generadora:
|
| {0,B} | {B,B} |
| q0 | (q0, {0,R}, {a,R}) | (q1, {B,L}, {B,Z}) |
| q1 | (q2, {0,Z}, {b,R}) | (q3, {B,R}, {B,Z}) |
| q2 | (q1, {0,L}, {b,R}) |
|
| q3 | (q3, {0,R}, {a,R}) | (q4, {B,R}, {#,R}) |
| q4 |
|
|
Funciona bien, ni un problem