MT Generadora de L={ a^nb^2na^n, con n mayor o igual a 0}

Esta MT genera cadenas del lenguaje L={a^n b^2n a^n, con 0≤n}.

Para realizar esta MT, hemos utilizado una MT multicinta, en la que, en la primera cinta, pondremos  0's que equivaldrá a n y en la segunda cinta iremos almacenando la cadena resultante.

Situación inicial:

Cinta 1: ...qoBBBBB...

Cinta 2: ...qoBBBBB...

Salida:

Cinta 1: 000....

Cinta 2: lambda$abba$aabbbbaa$aaabbbbbbaaa$...

Funcionamiento:

En q0 ponemos lambda en la cinta de resultados. Pasamos a q5 encontrando [B,B] por lo que pondremos el separador $ en la cinta2 y pasamos al bucle que empieza en q1.

En q1 añade un 0 al principio de la cadena de la cinta 1, entonces pasa a q2 donde pone en la cinta 2 tantas a's como ceros haya en la cinta 1, es decir, n a's.

Entre q3 y q4 pone en la cinta 2, dos b's por cada 0 que hay en la cadena de la cinta 1. 

En q5 pone otra vez por cada cero de la cinta 1, una a en la cinta 2 y vuelva a q1 añadiendo el separador en la cinta 2 y volvemos a por el siguiente valor de n.

Es una MT bastante sencilla. Hemos elegido multicinta porque nos facilita mucho el trabajo, ya que mientras vamos recorriendo la cadena de 0's de la Cinta 1 vamos generando la cadena del lenguaje L.

Resumen Semanal (21 a 27)

Lunes: Toma de contacto con las tareas a realizar.

Martes: Realización de la MT simple para contar los bloques de 0's.

Miércoles: Discusión sobre como realizar la MT modificada, si multicabezal o multicinta. Como nos gustaron ambas ideas, realizamos las dos maquinas.

Jueves: Realización de la MT simple para saber si los bloques de 0's estan ordenados.

Viernes:  Realización de la MT modificada para saber si los bloques de 0's estan ordenados.

Sábado:  Corrección de las MT's, en las que encontramos varios fallos, sobretodo en casos puntuales, para saber que cadenas acepta, cuales no, con cuales funcionan bien las MT's y con cuales no.

Domingo:  Último repaso por si las moscas.

MT "multicabezal" para saber si los BLOQUES de 0's estan en ORDEN CRECIENTE

Esta MT acepta cadenas con bloques de 0's separados con 1's, ordenados en orden creciente. Es decir, aceptará las cadenas del estilo ...B01001000B... y no aceptará aquellas del estilo...B01000100B...

Hemos elegido multicabezal porque así analizamos dos bloques de 0's a la vez, por lo que es mucho mas simple y rapido.

Situacion inicial: Ambos cabezales en el primer 0 de la cadena, el de mas a la izquierda.

Funcionamiento: 

En q0 dejamos un cabezal en el primer bloque de 0's y el otro lo movemos al segundo bloque de 0's.

En q1 vamos recorriendo los dos bloques mientras hayan 0's en los dos bloques, o si hay dos 1's (mismo numero de 0's en ambos bloques).

Si se llega a la situación de que en el primer cabezal tenemos 1 y en el segundo 0, significa que el primer bloque es mas pequeño por lo que pasamos a q2 y colocamos los cabezales para analizar el siguiente grupo de bloques de 0's.

Si en q1 o en q2 llegamos a la situación de que el segundo cabezal lee un B, es porque hemos recorrido toda la cadena y está ordenada.

MT "simple" para saber si los BLOQUES de 0's estan en ORDEN CRECIENTE

Esta MT acepta cadenas con bloques de 0's separados con 1's, ordenados en orden creciente. Es decir, aceptará las cadenas del estilo ...B01001000B... y no aceptará aquellas del estilo...B01000100B...

Para la realización de este problema, hemos utilizado la ventaja de marcaje de símbolos.

El cabezal, se coloca en el primer 0 de la cadena, el de mas a la izquierda.

Funcionamiento: 

En q0 marcamos el primer cero sin marcar que se encuentra.

En q1 se va hasta el primer 1, y si se encuentra B en vez de un 1 es que ya hemos comprobado toda la cadena.

En q2 se marca tambien el primer 0 sin marcar y se va a q3. 

Entre q3 y q4 se coloca el cabezal otra vez en el primer 0 sin marcar del primer bloque.

Si en q0 se recorre la primera cadena entonces es porque el primer bloque es mas pequeño o igual que el segundo, asi que vamos a q5.

En q5 y q6  se desmarca el segundo bloque y  se coloca el cabezal en el 1 que separaba los dos bloques.

Si en q5 se llega al B entonces tambien se acaba la cadena por lo que la cadena de bloques de 0 esta ordenada.

MT "multicabezal" COMO CONTADOR DE 0's SEPARADOS POR 1's

La MT que se muestra a continuación sólo acepta dos tipos de cadenas y solo pueden ser del tipo que se indica, es decir, no valen cadenas con varios 1`s seguidos:

TIPO1: ....B01001000001000101B......
SALIDA: ..B00000B...
TIPO2: ....B00101000B.......
SALIDA: ...B000B...

Es decir, que acabe la cadena en (1) o que no acabe en (1).

La situacion inicial de los cabezales para cualquiera de las cadenas que acepte es, el primer cabezal en el primer simbolo util de la cadena de entrada y el segundo cabezal una posicion mas a partir del ultimo blanco de la cadena de entrada. Tal que así:

B(q0)01001000001000101B(qz)

B(q0)00101000B(qz)

El primer cabezal es q0 y el segundo es qz.



Funcionamiento: mientras el primer cabezal lea 0's, sobreescribe con 0 y se mueve a la derecha y el segundo cabezal sobreescribe con blanco y no se mueve.

Cuando el primer cabezal encuentre un 1 sobreescribe con 1 y se mueve a la derecha y el segundo cabezal sobreescribe con 0 y se mueve a la derecha. Llegara un momento en que los dos cabezales lean blanco-blanco, en ese momento mueve el primer cabezal a la derecha y segun se encuentre con un 0 o un 1, hago escribir un 0 o un 1 en el segundo cabeza. ( Fila q1 de la tabla).

Este ultimo comportamiento lo hago para que en el caso de tener un cadena del tipo2 en la cinta me cuente el ultimo grupo de 0`s en el resultado final.

MT "multicinta" como CONTADOR de GRUPOS de 0's separados por 1's

ENTRADA: .....B01001000000100010100B.......
SALIDA: .........B000000B..........

Situacion inicial de la maquina: La MT consta de 2 cintas. La primera contiene la cadena de entrada, y la segunda almacenará el resultado. Los cabezales se encuentran en la siguiente posicion. En la cinta 1: al principio de la cadena, es decir, sobre el primer 0. En la cinta 2: Encima de un blanco cualquiera.

Funcionamiento: En el estado q0 se mira si el primer símbolo es un 0, y solo continua si realmente es así, para rechazar la cadena vacía o cadenas que empiecen por 1. 

En el estado q1 vamos avanzando en la cinta 1 pasando por encima de 0's hasta encontrar un 1 o hasta llegar al final de la cadena. Si encontramos un 1, pasamos a q2 para comprobar que el próximo símbolo sea un 0, así evitamos que hayan mas de un 1 seguido como separador. Si llegamos al final de la cadena, colocamos un 0 en la cinta de abajo, movemos su cabezal a la derecha y finalizamos.

En q2 leemos el primer 0 del siguiente grupo de 0's y en la cinta 2 escribimos un 0 y avanzamos a la derecha, indicando así que hemos leído un grupo de 0's.

Este proceso se repite hasta que solo queden 0's, es decir, al llegar al último grupo de 0's, que empezará leyendo 0's hasta encontrar el B, por lo que escribirá en la cinta de salida otro 0 indicando que se ha leído el último grupo y finalizará.

MT "simple" como CONTADOR de GRUPOS de 0's separados por 1's

ENTRADA: ....B0001010010000B.......
Como hay 4 grupos de 0's la salida deberá ser:
SALIDA: .....B0000B........

El cabezal se situa inicialmente a la izquierda del primer 0 de la cadena, es decir:

...Bqo0001010010000B...

Condiciones: La MT solo aceptará como validas, cadenas que tengan grupos de 0's separados por un solo 1 o una cadena de 0's. Es decir, acepta cadenas del estilo 001000100  y 0000, pero no acepta la cadena vacía, ni cadenas del tipo 100100 o 01100001000111000 etc.

Funcionamiento: En el estado q0 se mira si el primer símbolo es un 0, y solo continua si realmente es así, para rechazar la cadena vacía o cadenas que empiecen por 1.

En el estado q1 vamos borrando un grupo de 0's y su 1 separador. 

En q2 miramos que el siguiente símbolo a un 1 sea un 0, para evitar que haya mas de un 1 seguido como separador.

En q3 recorremos el resto de la cadena hasta el final, y para el primer grupo, colocamos un $ al final tras el que se almacenará el resultado.

En q4 se coloca un 0 tras el $ para indicar que hemos leído uno de los grupos de 0's.

En q5 volvemos al principio de la "nueva" cadena, es decir, de la cadena que queda sin borrar, para posteriormente, ir a por el siguiente grupo.

Cuando llegamos al último grupo de 0's, este no tiene al final un 1, sino el $ por lo que borramos el grupo y el $ y metemos un 0 al final de la cadena. Con esto llegamos al estado final q7.

Resumen Semanal (14 a 20)

Lunes: Nos tomamos día festivo por mi acierto en el generador canónico :p.

Martes: Corrección de las MT's del grupo 1.

Miércoles: Nothing.

Jueves: Nothing too.

Viernes:  " "

Sábado:  " "

Domingo:  " "

MT "multicinta" para sacar Divisores

Maquina de Turing multicinta para calcular Divisores

Idea: Usamos 3 cintas. En la primera tenemos la cadena original, en la segunda apuntamos los posibles divisores, y en la tercera vamos apuntando los divisores separados por 1's

Es decir:

Cinta1: 000000

Cinta2:0000

Cinta3:01001000

A continuación explicamos que "hace" la MT en cada grupo de estados, es decir, la distintas fases del proceso de calculo de divisores:

En q0 ponemos el primer divisor, y como sabemos que el 1 es divisor de todos tambien lo añadimos al resultado.

En q1 ponemos el segundo divisor, que sera el 2.

En q2 Si vamos tachando parejas hasta que una cadena llega a blanco o las dos, si son las dos vamos a q4, si la segunda cadena llega a B vamos a q3.

En q3 ponemos a 0 las X de la segunda cadena y volvemos a q2 para tachar parejas. Y en q2 si la primera cadena llega a B entonces……

En q4 ponemos a cero los numeros del divisor y copiamos el divisor en la tercera cadena y vamos a q5, entonces en q5 ponemos a 0 todas las cadenas, sin X.

En q6 y q7 compruebo si el numero que miramos si es divisor es mayor que la mitad del que estamos buscando sus divisores.

En q9 es estado final, y en q8 se deja la cadena preparada para comparar el siguiente numero

Resumen Semanal ( 7 a 13 )

Lunes: Puesta en común de ideas sobre la MT simple para el cálculo de Divisores. Posterior realización de la misma (versión 1.0) :p.

Martes: Corrección de la MT simple 1.0 encontrando varios errores y su posterior modificación a MT simple 2.0 ya que nos metía un 1 de más y no limpiábamos del todo bien la cadena final.

Miércoles: Repaso sobre la versión 2.0 para eliminar transiciones "absurdas" y comprobación de su correcto funcionamiento. Obtención de la versión final.

Jueves: Cerrado por descanso del personal

Viernes: Puesta en común de ideas sobre la MT multicinta para el cálculo de Divisores. Discusión (pacífica) sobre número de cintas, etc.

Sábado: Es Sábado... no apetece acordarse del tío Alan. Aunque se empezó a realizar la máquina... se quedó en intento.

Domingo: Realización de la MT multicinta. Corrección y posterior subida al blog.

MT "simple" para sacar Divisores

Maquina de Turing simple para calcular Divisores

Hemos utilizado una maquina de turing en la que hemos dividido su cinta en dos sectores. Uno contiene la cadena en si y otro para marcar si hemos leído o no cierto símbolo.

Objetivo: Dado un numero entero, calcular sus divisores.

Entrada: ...BB000000BBB...

Salida: ...BBB000000101001000BB...

Como resultado, tenemos el numero inicial y sus divisores (incluido el 1) separados por 1's.

A continuación explicamos que "hace" la MT en cada grupo de estados, es decir, la distintas fases del proceso de calculo de divisores:

De q0 a q2 prepara la cadena poniendo el primer numero con el que vamos a comprobar si es divisor y el simbolo $.

De q3 a q9 se mira si es divisor el numero, si es divisor pasa a q10, si no a q11.

En q10 ( si es divisor ) ponemos el 1 al final de la cadena y vamos a q17, si no es divisor ( estamos en q11) vamos a q12 a ver el siguiente numero.

Desde q17 hasta q21 copia la cadena, o sea el numero que es divisor, al final de la cadena y despues va a q12 para comprobar si el siguiente numero es divisor.

Desde q12 a a q16 añade un 0 al numero que queremos ver si es divisor y comprobamos que sea menor o igual que la mitad del que queremos ver sus divisores.

En q22 y q23 preparamos la cadena para ver si el numero es divisor y vamos a q3 .

En q24 y 25 acabamos por dejar la cadena con solo el numero del que hemos calculado sus divisores y sus divisores detrás separados por "1".

MT para N Cuadrado

Maquina de Turing para N Cuadrado

Las caracteristicas de la MT son: 

Objetivo: Dado un entero n , obtener n^2.

Entrada:  ...B000B...

Salida:  ...B000000000B...

Proceso:

Primero hay que arreglar la cadena para que dada una cadena ...B00000000B... quede ...B00000000$B...

Luego hay que ir anotando el resultado tras el $.

Para acabar, una vez obtenida una cadena del estilo ...B000X$000000000B... arreglarla suprimiendo la parte de la izquierda del $ para que finalmente aparezca ...B000000000B...

MT para la Division

Maquina de Turing para la División

Las caracteristicas de la MT son: 

Objetivo: Dados dos enteros n y m, obtener n % m y n / m.

Entrada:  ...B000100000B...

Salida:  ...B0010B...

Proceso:

Primero hay que arreglar la cadena para que dada una cadena ...Booo1ooooB... quede ...B00010000$B...

Luego hay que ir anotando el resultado tras el $ realizando divisiones sucesivas de n sobre m.

Para acabar, una vez obtenida una cadena del estilo ...B1YYY0$00B... arreglarla para que finalmente aparezca ...B000100B...

MT para la Multiplicacion

Maquina de Turing para la Multiplicacion

 

Las caracteristicas de la MT son: 

Objetivo: Dados dos enteros n y m, obtener n x m.

Entrada:  ...B00010000B...

Salida:  ...B000000000000B...

Proceso:

Primero hay que arreglar la cadena para que dada una cadena ...Booo1ooooB... quede ...B00010000$B...

Luego hay que ir anotando el resultado tras el $ realizando la suma de m n veces.

Para acabar, una vez obtenida una cadena del estilo ...B10000$000000000000B... arreglarla para que finalmente aparezca ...B000000000000B...