M.T. multicinta reconocedora de bloques de 0's ordenados ascendentemente

Recibe una cadena de entrada de bloques de 0's separados por 1's, devuelve en la cinta 2 el número de 0's más alto, dejando la cadena original intacta.

Cadena de entrada: B00100010000B

Cadena de salida:    B0000B (cinta 2)

Se ha elegido el diseño multicinta frente al multicabezal porque el segundo requeriría tantos cabezales como bloques de 0's hayan en la cadena para conseguir una buena eficiencia y como este dato no se conoce de antemano, se ha elegido multicinta.

Se han usado 2 cintas. En la primera se encontraría la cadena de entrada, mientras que la segunda se usará para guardar el número de 0's del ultimo bloque leído. Su funcionamiento es el siguiente:

1. Recorre la cadena de entrada anotando los 0's encontrados en la segunda cinta hasta encontrar un 1 y rebobina la cinta 2.
2. Si se encuentra en una posición 1,0 o B,0 la rechaza o bien borra la cinta 2 (dependiendo de la solucion escogida)
3. Si se encuentra en la posicion B,B, acaba satisfactoriamente.

El alfabeto empleado ha sido {0,1,B}. Se asume que la posición inicial en la cinta 1 es el primer símbolo de la cadena de entrada. La posición de la segunda cinta es indiferente. Se han implementado 2 posibles soluciones, una que cuando encuentra una cadena no valida, simplemente acaba y otra que borra la cinta 2.

M.T. multicinta para calcular bloques de 0's

Funciona del mismo modo que la M.T. anterior. Recibiendo una cadena de entrada de bloques de 0's separados por 1's, devuelve el número de bloques que existen en la cadena de entrada. 

Cadena de entrada: B0010001000B

Cadena de salida:    B000B

Se ha elegido el diseño multicinta frente al multicabezal porque el segundo requiere estados para posicionarse en el lugar donde se van a escribir los resultados y también porque en este caso, el diseño multicinta, no requiere copiar ninguna cadena en la cinta extra, con el consiguiente ahorro de estados que ello conlleva. 

Para ello se han usado esta vez 2 cintas. En la primera se encontraría la cadena de entrada, mientras que la segunda se usará para guardar el número de bloques que va encontrando y por tanto es la de salida. Funciona de la siguiente manera:

1. Recorre la cadena de entrada borrando los 0's hasta encontrar un 1 que también borra.
2. En ese momento si la cadena se encuentra en [0, B] marca un 0 en la cinta dos. Si se encuentra en [B,B] también marca un 0 y acaba, puesto que se encuentra al final
3. Repetición de lo anterior.

En esta M.T. también se ha usado el alfabeto {0,1,B}. Se asume que la posición inicial en la cinta 1 es el primer símbolo de la cadena de entrada. La posición de la segunda cinta es indiferente. También recoge la posibilidad de que acepte 1's al principio y al final, con lo que si no se quiere que lo haga, se deberían eliminar las funciones f(q0,1,B) y f(q2,B,B).

Descarta las cadenas con varios 1's consecutivos (B00110010B), aunque tan sólo habría que añadir el estado (q2,1,B) para que también las reconociera.

MT divisores (Multicinta)

Esta M.T. calcula los divisores de un número. La diferencia con la anterior es que esta M.T. es multicinta. Usa 3 cintas, guardando en la primera el número, en la segunda los candidatos a divisores desde n/2 y en la tercera los que son divisores. El alfabeto usado sigue siendo {0,1,B}.

Formato de entrada: B000000000B (cinta 1)

Formato de salida   : B00010B  (cinta 3)

Y la definición queda así: