Tarea 6: Generador de códigos válidos de MT universales

¡¡Última tarea!! :-)

a)
Según el enunciado del problema se pide una máquina generadora de cadenas que serán códigos sintácticamente válidos de MT (las cadenas generadas las podría comparar con comparar con la tarea de compilar un programa, sintácticamente puede estar correcto y compilar sin errores, otra historia es que no de errores de ejecución).

Para realizar este último generador de cadenas (del curso :-P ), vamos a utilizar una MT multicinta con 2 cintas.

La posicion inical del los cabezales en las cintas serán:
Cinta1: ...B0B... (primera cadena que aceptaría el generador sería 111010101010111)
Cinta2: ...BBB...

La cinta 1 tendrá una cadena que la máquina de Turing deberá comprobar si es sintácticamente correcta, en cuyo caso se escribirá en la cinta 2. Independientemente de si es o no válida la cadena se sustituirá la cadena de la cinta 1 por la siguiente que la sucede.

Tras mucho pensar y como no se nos ocurría otra manera de tratar la cadena, la usamos como si fuera un número binario al que se le incrementa en 1 el valor. Se rechazarían muchas cadenas pero sacamos todas las válidas en orden canónico (total... hay infinitas cadenas, de las cuales infinitas cadenas se rechazarían y otras infinitas serían válidas... antes de agotarse las infinitas combinaciones posibles de cadenas nuestro sol se convierte en supernova ).

Funcionamiento:
- Desde f(q₀,1,B) hasta f(q₁₉,1,B) la MT recorre la cadena de la cinta 1. Si la recorre sin error se escribirá en la cinta 2 un delimitador "#" para separar cada una de las cadenas válidas y a su vez el cabezal de la cinta 1 se desplazará hacia la izquierda.
- Desde f(q₂₀,1,B) hasta f(q₂₀,B,B) se seguirá desplazando en la cinta 1 hacia la izquierda hasta llegar al inicio de la cadena.
- Desde f(q₂₁,0,B) hasta f(q₂₁,B,B) copia simbolo a simbolo de izquierda a derecha la cadena de la cinta 1 en la cinta 2.
- Desde f(q₂₂,0,B) hasta f(q₂₃,1,B) trata de colocar en la cinta 1 la siguiente cadena en orden canónico, tratando la cadena de la cinta 1 como un número binario se le suma 1, dejando preparada la siguiente cadena para la siguiente iteracción del generador.
- Finalmente en el estado q₂₄ el cabezal de la cinta 1 se desplaza hacia la izquierda hasta el inicio de la nueva cadena y salta al estado q₀ para comenzar de nuevo el proceso de validación de cadena.


A continuación, las transiciones del MT del "a)" de la tarea:
f(q₀,1,B) = (q₁,{1,R},{B,Z})
f(q₁,1,B) = (q₂,{1,R},{B,Z})
f(q₂,1,B) = (q₃,{1,R},{B,Z})
f(q₃,0,B) = (q₄,{0,R},{B,Z})
f(q₄,0,B) = (q₄,{0,R},{B,Z})
f(q₄,1,B) = (q₅,{1,R},{B,Z})
f(q₅,0,B) = (q₆,{0,R},{B,Z})
f(q₆,0,B) = (q₇,{0,R},{B,Z})
f(q₇,0,B) = (q₈,{0,R},{B,Z})
f(q₈,1,B) = (q₉,{1,R},{B,Z})
f(q₇,1,B) = (q₉,{1,R},{B,Z})
f(q₆,1,B) = (q₉,{1,R},{B,Z})
f(q₉,0,B) = (q₁₀,{0,R},{B,Z})
f(q₁₀,0,B) = (q₁₀,{0,R},{B,Z})
f(q₁₀,1,B) = (q₁₁,{1,R},{B,Z})
f(q₁₁,0,B) = (q₁₂,{0,R},{B,Z})
f(q₁₂,0,B) = (q₁₃,{0,R},{B,Z})
f(q₁₃,0,B) = (q₁₄,{0,R},{B,Z})
f(q₁₃,1,B) = (q₁₅,{1,R},{B,Z})
f(q₁₄,1,B) = (q₁₅,{1,R},{B,Z})
f(q₁₂,1,B) = (q₁₅,{1,R},{B,Z})
f(q₁₅,0,B) = (q₁₆,{0,R},{B,Z})
f(q₁₆,0,B) = (q₁₇,{0,R},{B,Z})
f(q₁₇,1,B) = (q₁₈,{1,R},{B,Z})
f(q₁₆,1,B) = (q₁₈,{1,R},{B,Z})
f(q₁₈,1,B) = (q₁₉,{1,R},{B,Z})
f(q₁₉,0,B) = (q₄,{0,R},{B,Z})
f(q₁₉,1,B) = (q₂₀,{1,L},{#,R})
f(q₂₀,1,B) = (q₂₀,{1,L},{B,Z})
f(q₂₀,0,B) = (q₂₀,{0,L},{B,Z})
f(q₂₀,B,B) = (q₂₁,{B,R},{B,Z})
f(q₂₁,0,B) = (q₂₁,{0,R},{0,R})
f(q₂₁,1,B) = (q₂₁,{1,R},{1,R})
f(q₂₁,B,B) = (q₂₂,{B,L},{B,Z})
f(q₂₂,0,B) = (q₂₄,{1,L},{B,Z})
f(q₂₂,1,B) = (q₂₃,{0,L},{B,Z})
f(q₂₃,0,B) = (q₂₄,{1,L},{B,Z})
f(q₂₃,1,B) = (q₂₃,{0,L},{B,Z})
f(q₂₄,0,B) = (q₂₄,{0,L},{B,Z})
f(q₂₄,1,B) = (q₂₄,{1,L},{B,Z})
f(q₂₄,B,B) = (q₀,{B,R},{B,Z})


b)
El pensamiento que creemos que se acerca más es la opción 2 ("¡Anda! salen infinitas máquinas pero va a ser que no tengo bastantes...") porque a pesar de haber infinitas máquinas puede darse el caso que el resultado no se encuentre entre todas esas máquinas (por ejemplo: cuando un programa no puede detenerse porque cae en un bucle infinito, hay infinitos resultados pero ninguno de ellos es el válido para continuar).

Tarea 5: Demostración de intersección de dos LRE.

Por las propiedades de clausura de los LRE, podemos demostrar que la intersección de dos LRE da como resultado otro lenguaje LRE.
Para el lenguaje interesección de dos Lenguajes sólo aceptará cadenas que pertenezcan a ambos lenguajes.

Para demostrarlo utilizaremos 2 MT, ambas máquinas (M1 y M2) reconocen lenguajes recursivamentes enumerables.

Procedimiento:
Tomamos una cadena x tal que si la M2 acepta la cadena, habilitará la M1. Si esta última acepta la cadena, tendremos la intersección entre L1 y L2.

Si x € L1 AND x € L2 => x € L1 intersección L2 = L

Trabajo 4 - Generador de cadenas: anb2ncn

Funcionamiento:
Para realizar este generador, vamos a utilizar un MT multicinta con 2 cintas.
La primera sera una cinta con el numero de 0´s (el valor de n) y la otra sera la cinta en la que generaremos las cadenas del lenguage L={aⁿb^²ⁿc^ⁿ, para todo n mayor o igual que 0}.

La posicion inical del los cabezales en las cintas serán:
Cinta1: ...B000B...
Cinta2: ...BBB...

Por cada 0 que se lea en la cinta uno se escribirá en la cinta dos una a. El proceso se repite hasta que en la cinta uno lea un B. En este caso, se cambia la dirección de lectura en la cinta 1 hacia la izquierda cambiando de estado. Para escribir las b´s en las cinta de salida, haremos un barrido a la izquierda imprimiendo por cada 0 una b y despues otro barrido hacia la derecha repitiendo el mismo proceso de escritura dos. Finalmente, haremos un ultimo barrido para escribir el ultimos conjunto de a´s. En este caso, cuando en la cinta 1 se encuentre un B, escribiremos un 0 para la siguiente iteración, al tiempo que en la cinta dos escribimos un delimitador(#)para separar las siguiente cadena del lenguaje. Se vuelve al estado incial para volver a escribir la nueva cadena.

La salida será:
Cinta 2: ...Baaabbbbbbaaa#aaaabbbbbbbbaaaa#.......

	[0,B]	[B,B]
q0	{q0,{0,R},{a,R}}	{q1,{B,L},{B,Z}}
q1	{q1,{0,L},{b,R}}	{q2,{B,R},{B,Z}}
q2	{q2,{0,R},{b,R}}	{q3,{B,L},{B,Z}}
q3	{q3,{0,L},{a,R}}	{q0,{0,Z},{#,R}}

Trabajo 3 - parte 4 (final)

Ahora vamos a resolver el problema propuesto con una maquina de Turing modificada.
Usamos en este caso la MT multicabezal:

En q0 mientras el 1º cabezal no se mueve el 2º cabezal recorre la cadena de 0's hasta que encuentra un 1 momento que termina de colocarse ambos cabezales en sus respectivos grupos de 0's para ser analizados por parejas y se pasa a q₁. Hay un caso particular en q₀ en el que el 2º cabezal se tropieza con el B antes de leer un 1, significa que en la caden a de entrada sólo nos han dado un grupo de 0's y por lo tanto se sonsidera que está en orden creciente ( :P ) terminando con éxito la MT en el estado final q₃.
En q₁ hacemos todo el rato parejas de 0's hacia la derecha hasta que el 1º cabezal lea un 1, momento en el que se pasa a q₂.
En q₂ sólo movemos el 2º cabezal hacia la derecha para que busque la siguiente cadena de 0's y así repetir el proceso del estado q1 para hacer parejas de 0's.
Si en q2 el segundo cabezal lee un B se considera que no hay más cadenas de 0's que comparar y se envia a q3, estado final.
f(q₀,0,0) = (q₀,{0,Z},{0,R})
f(q₀,0,1) = (q₁,{0,Z},{1,R})
f(q₀,0,B) = (q₃,{0,Z},{B,Z})
f(q₁,0,0) = (q₁,{0,R},{0,R})
f(q₁,1,0) = (q₂,{1,R},{0,R})
f(q₂,0,0) = (q₂,{0,Z},{0,R})
f(q₂,0,1) = (q₁,{0,Z},{1,R})
f(q₂,0,B) = (q₃,{0,Z},{B,Z})
q₃ = ESTADO FINAL

Trabajo 3 - Parte 3

Bueno, para resolver el siguiente problema, primero lo diseñaremos con la maquina de Turing "clásica" y después modificar la máquina para que el diseño sea mas sencillo.

Para la máquina de Turing clasica, en el estado q₀ marcamos con una X el primer 0 y cambiamos al estado q1, ignora los 0 y va recorriendo la cadena hasta que encuentra un 1 que cambia de nuevo de estado a q₂. Recorre hacia la derecha la cadena saltandose todos los posibles X's (si lo hubiera) hasta que encuentra un o, momento que lo sustituye por una X y mueve el cabezal hacia la izquierda cambiando de estado a q₃. Si hay X's por su camino hacia la izquierda se los salta hasta que lee un 1, cambiando de estado a q₄₀ y moviendose a la izquierda_. Recorre todos los 0´s que pueda encontrarse el cabezal hasta que lee un X, momento que se desplaza a la derecha y cambia de estado a q₀. Repite el proceso todo el tiempo que encuentre parejas del grupo de 0's inicial y el grupo de 0's contiguo hasta que estando en q0 encuente 1, momento que significa que la cadena de 0's se ha agotado, pasamos a q5 y recorremos el siguiente grupo de 0's que estabamos analizando también para comprobar que aún le quedaban 0's que tachar, una vez comprovado que aún quedaban ceros nos vamos a q6 para movemos al inicio de esa cadena y dejando las X's marcadas en 0's para dejarla lista para la siguiente comprobación entre ese grupo de 0's y el siguiente.
Si estando en q₁ encuentra el blanco, significando que no hay grupo de 0's a la derecha del actual terminando con éxito la MT clásica en el estado q₇.

ENTRADA: ...B01001000100000B...
FINALIZA: Acepta si los grupos de o's separados por 1's están ordenados por orden creciente.

	0	1	X	B
q0	(q1,X,R)	(q5,1,R)
q1	(q1,0,R)	(q2,1,R)		(q7,B,L)
q2	(q3,X,L)		(q2,X,R)
q3		(q4,1,L)	(q3,X,L)
q4	(q4,0,L)		(q0,X,R)
q5	(q6,0,L)		(q5,X,R)
q6		(q0,1,R)	(q6,0,L)
q7

Trabajo 3 - Parte 2

Ahora vamos a resolver el problema propuesto con una maquina de Turing modificada. Inicialmente se nos habia ocurrido de 2 maneras:

- Utilizar una máquina multicabezal con 2 cabezales, uno para recorrer la cadena y otro para guardar el resustado.
- En caso de la multicinta, usariamos 2 cintas. Hemos observado que con la primera cinta recorremos la cadena de entrada y con la otra cinta se escribe el resultado.

Finalmente hemos escogido la multicabezal porque es ligeramente más eficiente (para nosotros :P ) a la hora de escribir las transiciones.

Poscionamiento inicial de los cabezales

...B00001001001000100BB...
Rojo= Posicion inical del cabezal 1
Azul= Posición inicial del cabezal 2

Procedimiento: Utilizaremos el estado q₀ para desplazar el cabezal 2 a la derecha hasta que encuentre un blanco, momento que mueve a la derecha el cabezal 2 situandose en el segundo blanco de la derecha y cambia al estado q₁. En estado q₁, cada vez que leamos en los cabezales (0,B) marcamos en el primer cabezal un blanco y los desplazamos a la derecha y no modificamos el cabezal 2 ni lo desplazamos. En el estado q₁, cuando encontramos (1,B) marcamos con el cabezal 1 un blanco y desplazamos a la derecha y con el cabezal 2 escribimos un 0 y lo desplazamos a la derecha. Seguiremos en el estado q₁ hasta que encontremos (B,B) no haremos nada con el cabezal 1 y en cabezal marcamos un 0 y terminamos en el estado final q₂.

ENTRADA: ...B0001001001000100B...
SALIDA: ...B00000B...

Las transiciones del MT multicabezal son:

f(q₀,0,0) = (q₀,{0,Z},{0,R})
f(q₀,0,1) = (q₀,{0,Z},{1,R})
f(q₀,0,B) = (q₁,{0,Z},{B,R})
f(q₁,0,B) = (q₁,{B,R},{B,Z})
f(q₁,1,B) = (q₁,{B,R},{0,R})
f(q₁,B,B) = (q₂,{B,Z},{0,R})
f(q₂,B,B) = ESTADO FINAL

Trabajo 03 - Parte 1

Bueno, pues para resolver el nuevo problema propuesto, primero lo diseñaremos con la maquina de Turing de "toda la vida"y después modificarla la máquina para que el diseño sea mas sencillo.

Para la máquina de Turing tradicional,en el estado q0 marcamos con una X el primer 0 y cambiamos al estado q1, ignora los 0 y va recorriendo la cadena hasta que encuentra un 1 sustituyendolo por un 0 y cambiando al estado q2 moviendose a la izquierda. Recorre todos los 0´s hasta que encuentre una X y cambia al estado q0 va hacia la derecha y no cambia el valor. Se repite el bucle hasta que encuentre el blanco, cambiando de estado a q3 y moviendose hacia la izquierda. Recorre hacia la izquierda cambiado los 0´s por blancos y las X por 0´s hasta que encuentra un blanco y va al estado final q5.

ENTRADA: ...B0001001001000100B...
SALIDA: ...B00000B...

	0	1	B	X
q0	(q1,X,R)
q1	(q1,0,R)	(q2,0,L)	(q3,B,L)
q2	(q2,0,L)			(q0,X,R)
q3	(q3,B,L)		(q4,B,R)	(q3,0,L)
q4