MT generadora del lenguaje anb2nan

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:

1. La en la cinta 1 se van introduciendo 0's, uno por cada cadena (sería lo correspondiente a n>=0)
2. Recorre los 0's de la cinta uno y escribe tantas a's como 0's hayan.
3. Vuelve al inicio de la cinta 1 y la recorre anotando tantas b's como 0's hay.
4. Al volver atrás en la cinta 1, vuelve a anotar una b por cada 0.
5. Finalmente la recorre por última vez volviendo a anotar a's
6. 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:

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. simple reconocedora de bloques de 0's ordenados ascendentemente

Al recibir una cadena de entrada de bloques de 0's separados por 1's, debe aceptar las cadenas que sus bloques de 0's estén ordenados de forma ascendente, es decir, aceptar las cadenas tipo ...B0010010000100000B... y rechazar cadenas como ...B001000100100000B...

Cadena de entrada: B0010001000B

Cadena de salida:    B0010001000B (cadena aceptada)

Cadena de salida:    BBBBBBBBBBBB (cadena rechazada)

 El funcionamiento es el siguiente:

1. Recorre la cadena de entrada marcando los primeros 0's de cada bloque hasta llegar al final, marcando siempre el primero que encuentra con el simbolo Y. (q0, q1, q2)
2. Vuelve atrás hasta el símbolo Y y repite el paso 1.  (q3)
3. Si en el primer marcaje (q0) encuentra un 1, sigue al siguiente bloque, si encuentra un B, la cadena es válida y la recorre para cambiar todos los X e Y por 0's (q4)
4. Si en el segundo marcaje o sucesivos (q1) encuentra un 1 o un B, la cadena no es válida y la recorre borrando todos los símbolos (q5, q6)

En esta M.T. se ha usado el alfabeto {0,1,B,X,Y}. Se asume que la posición inicial es el primer símbolo de la cadena de entrada. Si tan sólo debiera rechazar la cadena y no dejarla a 0's se pueden comentar todos los estados q5 y q6 y f(q1,1), f(q1,B).

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.

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

Esta M.T. calcula algo parecido a lo que sería en C la variable "argc". Se encarga de devolver la cantidad de bloques de 0's que hay en la entrada, separados entre ellos por el símbolo 1. Así, un ejemplo sería:

Cadena de entrada:  B0010001000B

Cadena de salida:     B000B

En la M.T. construida, se han tenido en cuenta dos casos más. La posibilidad de que se encuentre un 1 al principio o un 1 al final:

B1001000100B

B0010001001B

En caso de no considerarse cadenas válidas, tan sólo debería eliminarseel estado q0 para que no acepte el 1 inicial y la f(q5,1) para que no acepte el 1 final.

El funcionamiento básico del autómata es el siguiente:

1. Borra todos los 0's hasta encontrarse un 1 (BBB10001000B)
2. Borra ese 1 y se mueve al final (BBBB0001000Bq3B)
3. Una vez encontrado un B salta a la derecha y anota un 0 (BBBB0001000B0B)
4. Vuelve y repite la operación hasta encontrar un blanco después de tachar 0's (BBBBBBBBBBBB000B)

Como se puede ver, el alfabeto utilizado vuelve a ser {0,1,B}. Además suponemos que la posición inicial del autómata se sitúa en el primer símbolo de la cadena de entrada.

EDITADO: Se ha modificado la M.T. para que acepte cadenas B00011100B. Si no se debieran aceptar, tan sólo habría que eliminar el estado f(q7,1)

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í:

M.T. para calcular los divisores (OK)

Esta es la buena. Para solucionar el problema que teníamos de la cantidad de estados de la M.T. se ha programado un pequeño script en perl para simular máquinas de Turing simples. Hemos cambiado los formatos de entrada y salida de acuerdo a lo que se pedía y el resultado parece hacer sido satisfactorio. El alfabeto se mantiene el mismo {0,1,B} y ahora los 0's se toman como indicadores del número y los 1's como separadores:

Formato de entrada: B000000000B

Formato de salida   : B00010B

Por cierto, la otra M.T. definitivamente estaba mal, pero la dejo por si tenéis curiosidad por saber en que fallaba. Así ha quedado esta nueva versión:

M.T. para calcular los divisores

Esta M.T. la hemos realizado al igual que las anteriores con un alfabeto {0,1,B}. Ha llegado un momento en que la cantidad de estados nos superaban, así que la vamos a dejar a modo de curiosidad y teniendo en cuenta que ni siquiera está repasada para ver si funciona bien en todos los casos. Así que si os da por comprobarla, ¡informad de fallos y se os agradecerá!.

Formato de entrada: B111111111B

Formato de salida:     B11101B

El 0 se usa de separador y el 1 para marcar los números. La B además se usa para marcar pares (Glub!).

M.T. para calcular la división

Usamos el mismo alfabeto de siempre {0,1,B}, mismo poder computacional, más trabajo, masoquismo. El "0" se usa en este caso como separador y cada "1" indica un numero. Los formatos de entrada/salida son:

Entrada: ...B11111011B...

Salida:    ...B1011B...

Los primeros números que encontramos en la salida son el resto de la división. El número final es el cociente.

Descipción:

M.T. para calcular N cuadrado

Al igual que la anterior, esta Máquina de Turing se ha diseñado con un alfabeto reducido a los símbolos {0,1,B}. Incluye la M.T. de la multiplicación, aunque se añadieron estados previos para adecuar la cadena:

Entrada:                   ..B1111B.. 

Paso intermedio: ..B111101111B..

Salida:                       ..B1111111111111111B..

Descripción:

M.T. para calcular la multiplicación

La siguiente máquina de Turing se encarga de calcular la multiplicación de dos números enteros. Los formatos de entrada y salida son los siguientes:

Entrada:  ..B11101111B..

Salida:      ..B111111111111B...

Se ha usado un alfabeto reducido a los símbolos {0,1,B}, usando el símbolo "0" como separador.