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.