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

Organización del trabajo en grupo.

El lunes después de clase, nos estubimos repartiendo las tareas futuras para que cada uno en cada trabajo tenga una función distinta, publicar los trabajos, correguir los trabajos del grupo que nos corresponde y solucionar los problemas propuestos. En caso de ayuda se le pide al resto del grupo.

Ya veremos como funciona...

Trabajo 02 (final) - Averiguar divisores de un número

Miembros del grupo 1:
Javier Garcés Niño
Manuel Alberto Bolós Doñate
José Simó Albiol

MT para sacar divisores (MT sin modificaciones):
Dados un enteros n, obtener su lista de divisores.
ENTRADA: ...B0000000000B... (0ⁿ)
SALIDA: ...B0100100000B... (0ⁱ¹10ⁱ²10ⁱ³1... donde i1, i2, i3,... son los divisores de n)
Nota: a la hora de colgar el diseño de la MT normal al blog descubrí un error en el momento que guardaba el valor en la lista de divisores y posteriormente el incremento en un "0" al inicio de la cinta para hacer la comprobación con el siguiente posible divisor. Dicho error no comprobaba si el nuevo divisor a analizar era de mayor tamaño que el número n inicial, provocando un bucle infinito... :-S Bastó con incluir nuevos estados al final de la tabla que comprobaran si el nuevo divisor era de mayor tamaño que n.

	0	1	$	B	X
q0	(q0,0,R)			(q1,$,L)
q1	(q1,0,L)			(q2,$,L)
q2				(q3,0,L)
q3	(q4,x,R)			(q3,B,R)
q4	(q4,0,R)		(q5,$,R)
q5	(q6,X,L)				(q5,X,R)
q6	(q6,0,L)		(q7,$,L)		(q6,X,L)
q7	(q12,0,R)				(q8,x,R)
q8			(q9,$,R)
q9	(q10,0,L)		(q17,$,R)		(q9,X,R)
q10			(q11,$,L)		(q10,X,L)
q11				(q3,B,R)	(q11,0,L)
q12			(q13,$,R)
q13	(q15,0,L)		(q14,$,L)		(q13,X,R)
q14	(q14,0,L)		(q14,$,L)	(q3,0,L)	(q14,0,L)
q15			(q16,$,L)		(q15,X,L)
q16	(q16,0,L)				(q3,x,R)
q17	(q17,0,R)	(q17,1,R)		(q18,0,L)
q18	(q18,0,L)	(q18,1,L)	(q19,$,L)
q19			(q20,$,L)		(q19,X,L)
q20	(q20,0,L)				(q21,0,L)
q21				(q25,0,R)	(q27,X,R)
q22	(q22,0,R)	(q22,1,R)	(q22,$,R)	(q18,0,L)	(q22,X,R)
q23	(q23,0,R)	(q23,1,R)	(q23,$,R)	(q24,1,L)	(q23,0,R)
q24	(q24,0,L)	(q24,1,L)	(q24,$,L)	(q3,B,R)
q25	(q25,0,R)		(q26,$,L)
q26	(q27,X,R)			(q23,B,R)	(q26,X,L)
q27			(q28,$,R)		(q27,X,R)
q28	(q28,0,R)		(q31,B,L)		(q29,0,L)
q29	(q29,0,L)		(q26,$,L)
q30					(q30,X,L)
q31	(q31,B,L)		(q31,B,L)	(q32,B,R)	(q31,B,L)
q32

MT para sacar divisores (MT multicabezal):
Nota: entrada y salida son iguales que con la MT normal sin modificaciones.

Descripción:
Para realizar la MT multicabezal del problema hemos usado 3 cabezales de L/E:
- 1 para trabajar con los "posibles" divisores durante el proceso.
- 1 para trabajar con el número de entrada n.
- 1 para escribir los divisores en la lista ubicada a la derecha del segundo símbolo "$", separados por un 1 cada divisor.
Nota: a pesar de que Jose realizó unas últimas trazas esta mañana con distintos casos no se ha comprobado que falle el modelo multicabezal mostrado a continuación, así que finalmente se ha colgado el modelo... (y crucemos los dedos de que no hubiera un fallo muy rebuscado aún sin detectar :-P )

f(q₀,0,0,0) = (q₁,{0,L},{0.Z},{0,R})
f(q₁,B,0,0) = (q₂,{$,L},{0,Z},{0,R})
f(q₂,B,0,0) = (q₃,{0,Z},{0,Z},{0,R})
f(q₃,0,0,0) = (q₃,{0,Z},{0,Z},{0,R})
f(q₃,0,0,B) = (q₄,{0,Z},{0,Z},{$,R})
f(q₄,0,0,B) = (q₄,{X,R},{X,R},{B,Z})
f(q₄,$,0,B) = (q₅,{$,L},{0,Z},{B,Z})
f(q₅,X,0,B) = (q₅,{0,L},{0,Z},{B,Z})
f(q₅,B,0,B) = (q₄,{B,R},{0,Z},{0,Z})
f(q₄,0,$,B) = (q₅,{0,L},{0,L},{B,Z})
f(q₅,X,X,B) = (q₅,{0,L},{0,L},{B,Z})
f(q₅,B,X,B) = (q₆,{0,R},{0,L},{B,Z})
f(q₆,0,X,B) = (q₆,{0,Z},{0,L},{B,Z})
f(q₆,0,$,B) = (q₄,{0,Z},{$,R},{B,Z})
f(q₄,$,$,B) = (q₇,{$,L},{$,L},{B,Z})
f(q₇,X,X,B) = (q₇,{Q,L},{0,L},{0,R})
f(q₇,B,X,B) = (q₈,{0,Z},{0,L},{1,R})
f(q₈,0,$,B) = (q₄,{0,Z},{$,R},{B,Z})
f(q₇,B,$,B) = (q₉,{B,R},{B,R},{B,Z})
f(q₉,0,0,B) = (q₉,{B,R},{B,R},{B,Z})
f(q₉,B,$,B) = (q₁₀,{B,Z},{B,Z},{B,Z})
f(q₁₀,B,B,B) = ESTADO FINAL

Trabajo 02 (1º resumen) - Averiguar divisores de un número

Tras varias reuniones de mi grupo después de las clases del lunes y del viernes (que son los días cuando podemos quedar los 3, excepto el viernes 11 que Jose no pudo ir a clase) realizamos un diseño de la MT normal que tenía que averiguar todos los divisores de un numero dado y un diseño preliminar de la misma máquina pero aplicándole múltiples cabezales (creo que no tiene fallos pero hasta que alguno de nosotros detecte algún fallo se dejará tal y como está).

Mañana colgaré los problemas del trabajo, revisad si hay fallos y así mañana los corregimos... y si se os ocurre una mejor forma de hacerlos pues se comprueban y comparan con los que hay ;-)


PD: Menos mal que cumplí con las fechas y publiqué el sábado el material del trabajo del blog, pues nada, mañana lunes se subirá todo ¬¬'

Trabajo 01 - Escribir MTs de multiplicar, dividir y n^2

Miembros del grupo 1:
Javier Garcés Niño
Manuel Alberto Bolós Doñate
José Simó Albiol


MT para multiplicar:
Dados dos enteros n y m, obtener el resultado de la multiplicación.
ENTRADA: ...B00010000B...
SALIDA: ...B000000000000B...

	0	1	B	$
q0	(q0,0,R)	(q0,1,R)	(q1,$,L)
q1	(q1,0,L)	(q1,1,L)	(q2,B,R)
q0	(q1,B,R)	(q7,B,R)	(cambiar estados)	()
q1	(q1,0,R)	(q2,1,R)
q2	(q3,B,R)			(q5,$,L)
q3	(q3,0,R)		(q4,0,L)	(q3,$,R)
q4	(q4,0,L)		(q2,B,R)	(q4,$,L)
q5		(q6,1,L)	(q5,0,L)
q6	(q6,0,L)		(q0,B,R)
q7	(q7,B,R)			(q8,B,R)
q8

MT para dividir:
Dados 2 enteros n y m, obtener el resto y el cociente de la división.
Nota: El final de la MT tiene una versión distinta a la propuesta en clase.
ENTRADA: ...B000100000B...
SALIDA: ...B0010B...

	0	1	B	Y	$
q0	(q0,0,R)	(q1,1,R)
q1	(q1,0,R)		(q2,B,L)
q2	(q3,$,L)
q3	(q3,0,L)	(q4,1,L)
q4	(q4,0,L)		(q5,B,R)
q5	(q6,B,R)
q6	(q6,0,R)	(q7,1,R)
q7	(q8,Y,R)			(q7,Y,R)
q8	(q9,0,L)				(q10,$,R)
q9	(q9,0,L)	(q9,1,L)	(q5,B,R)	(q9,Y,L)	(q9,$,L)
q10	(q10,0,R)		(q11,0,L)
q11	(q11,0,L)				(q12,$,L)
q12	(q12,0,L)			(q13,0,L)
q13	(q14,Y,R)	(q13,1,L)	(q17,B,R)	(q13,Y,L)
q14	(q12,0,L)	(q14,1,R)		(q14,Y,R)	(q15,$,L)
q15		(q16,1,L)		(q15,Y,L)
q16	(q16,0,L)		(q5,B,R)	(q16,0,L)
q17	(q18,B,R)	(q17,B,R)		(q17,B,R)
q18	(q18,0,R)				(q19,1,L)
q19

MT para N²:
Dado un entero n, obtener el cuadrado de ese entero.
Nota: El procedimiento es diferente al propuesto en clase.
ENTRADA: ...B000B...
SALIDA: ...B000000000B...

	0	B	X	Y	Z	$
q0	(q1,X,R)
q1		(q2,B,R)		(q2,Y,R)
q2	(q3,Y,R)		(q3,Z,R)			(q6,$,L)
q3	(q3,0,R)		(q3,X,R)	(q3,Y,R)	(q3,Z,R)	(q4,$,R)
q4	(q4,0,R)	(q5,0,L)
q5	(q5,0,L)		(q2,Y,R)		(q2,Z,R)	(q5,$,L)
q6		(q7,B,R)		(q6,0,L)	(q6,X,L)
q7	(q7,0,R)		(q8,0,R)
q8	(q9,X,L)					(q10,B,L)
q9	(q9,0,L)	(q0,B,R)
q10	(q10,B,L)	(q11,B,R)
q11

probando, probando...

¡Hola m... (frase típica de los tutoriales de programación del 99% de los lengajes existentes... otros lenguajes para parecer diferentes/modernos dicen otras cosas como "¡adiós mundo!")

:P