¡¡Ú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(q0,1,B) hasta f(q19,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(q20,1,B) hasta f(q20,B,B) se seguirá desplazando en la cinta 1 hacia la izquierda hasta llegar al inicio de la cadena.
- Desde f(q21,0,B) hasta f(q21,B,B) copia simbolo a simbolo de izquierda a derecha la cadena de la cinta 1 en la cinta 2.
- Desde f(q22,0,B) hasta f(q23,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 q24 el cabezal de la cinta 1 se desplaza hacia la izquierda hasta el inicio de la nueva cadena y salta al estado q0 para comenzar de nuevo el proceso de validación de cadena.
A continuación, las transiciones del MT del "a)" de la tarea:
f(q0,1,B) = (q1,{1,R},{B,Z})
f(q1,1,B) = (q2,{1,R},{B,Z})
f(q2,1,B) = (q3,{1,R},{B,Z})
f(q3,0,B) = (q4,{0,R},{B,Z})
f(q4,0,B) = (q4,{0,R},{B,Z})
f(q4,1,B) = (q5,{1,R},{B,Z})
f(q5,0,B) = (q6,{0,R},{B,Z})
f(q6,0,B) = (q7,{0,R},{B,Z})
f(q7,0,B) = (q8,{0,R},{B,Z})
f(q8,1,B) = (q9,{1,R},{B,Z})
f(q7,1,B) = (q9,{1,R},{B,Z})
f(q6,1,B) = (q9,{1,R},{B,Z})
f(q9,0,B) = (q10,{0,R},{B,Z})
f(q10,0,B) = (q10,{0,R},{B,Z})
f(q10,1,B) = (q11,{1,R},{B,Z})
f(q11,0,B) = (q12,{0,R},{B,Z})
f(q12,0,B) = (q13,{0,R},{B,Z})
f(q13,0,B) = (q14,{0,R},{B,Z})
f(q13,1,B) = (q15,{1,R},{B,Z})
f(q14,1,B) = (q15,{1,R},{B,Z})
f(q12,1,B) = (q15,{1,R},{B,Z})
f(q15,0,B) = (q16,{0,R},{B,Z})
f(q16,0,B) = (q17,{0,R},{B,Z})
f(q17,1,B) = (q18,{1,R},{B,Z})
f(q16,1,B) = (q18,{1,R},{B,Z})
f(q18,1,B) = (q19,{1,R},{B,Z})
f(q19,0,B) = (q4,{0,R},{B,Z})
f(q19,1,B) = (q20,{1,L},{#,R})
f(q20,1,B) = (q20,{1,L},{B,Z})
f(q20,0,B) = (q20,{0,L},{B,Z})
f(q20,B,B) = (q21,{B,R},{B,Z})
f(q21,0,B) = (q21,{0,R},{0,R})
f(q21,1,B) = (q21,{1,R},{1,R})
f(q21,B,B) = (q22,{B,L},{B,Z})
f(q22,0,B) = (q24,{1,L},{B,Z})
f(q22,1,B) = (q23,{0,L},{B,Z})
f(q23,0,B) = (q24,{1,L},{B,Z})
f(q23,1,B) = (q23,{0,L},{B,Z})
f(q24,0,B) = (q24,{0,L},{B,Z})
f(q24,1,B) = (q24,{1,L},{B,Z})
f(q24,B,B) = (q0,{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).
miércoles, 28 de mayo de 2008
lunes, 12 de mayo de 2008
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
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
miércoles, 30 de abril de 2008
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={anb^2nc^n, 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#.......
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={anb^2nc^n, 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}} |
lunes, 28 de abril de 2008
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 q1. Hay un caso particular en q0 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 q3.
En q1 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 q2.
En q2 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(q0,0,0) = (q0,{0,Z},{0,R})
f(q0,0,1) = (q1,{0,Z},{1,R})
f(q0,0,B) = (q3,{0,Z},{B,Z})
f(q1,0,0) = (q1,{0,R},{0,R})
f(q1,1,0) = (q2,{1,R},{0,R})
f(q2,0,0) = (q2,{0,Z},{0,R})
f(q2,0,1) = (q1,{0,Z},{1,R})
f(q2,0,B) = (q3,{0,Z},{B,Z})
q3 = ESTADO FINAL
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 q1. Hay un caso particular en q0 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 q3.
En q1 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 q2.
En q2 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(q0,0,0) = (q0,{0,Z},{0,R})
f(q0,0,1) = (q1,{0,Z},{1,R})
f(q0,0,B) = (q3,{0,Z},{B,Z})
f(q1,0,0) = (q1,{0,R},{0,R})
f(q1,1,0) = (q2,{1,R},{0,R})
f(q2,0,0) = (q2,{0,Z},{0,R})
f(q2,0,1) = (q1,{0,Z},{1,R})
f(q2,0,B) = (q3,{0,Z},{B,Z})
q3 = 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 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 que cambia de nuevo de estado a q2. 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 q3. Si hay X's por su camino hacia la izquierda se los salta hasta que lee un 1, cambiando de estado a q40 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 q0. 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 q1 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 q7.
ENTRADA: ...B01001000100000B...
FINALIZA: Acepta si los grupos de o's separados por 1's están ordenados por orden creciente.
Para la máquina de Turing clasica, 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 que cambia de nuevo de estado a q2. 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 q3. Si hay X's por su camino hacia la izquierda se los salta hasta que lee un 1, cambiando de estado a q40 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 q0. 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 q1 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 q7.
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 |
jueves, 24 de abril de 2008
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
- 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
Rojo= Posicion inical del cabezal 1
Azul= Posición inicial del cabezal 2
Procedimiento: Utilizaremos el estado q0 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 q1. En estado q1, 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 q1, 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 q1 hasta que encontremos (B,B) no haremos nada con el cabezal 1 y en cabezal marcamos un 0 y terminamos en el estado final q2.
ENTRADA: ...B0001001001000100B...
SALIDA: ...B00000B...
Las transiciones del MT multicabezal son:
f(q0,0,0) = (q0,{0,Z},{0,R})
f(q0,0,1) = (q0,{0,Z},{1,R})
f(q0,0,B) = (q1,{0,Z},{B,R})
f(q1,0,B) = (q1,{B,R},{B,Z})
f(q1,1,B) = (q1,{B,R},{0,R})
f(q1,B,B) = (q2,{B,Z},{0,R})
f(q2,B,B) = ESTADO FINAL
ENTRADA: ...B0001001001000100B...
SALIDA: ...B00000B...
Las transiciones del MT multicabezal son:
f(q0,0,0) = (q0,{0,Z},{0,R})
f(q0,0,1) = (q0,{0,Z},{1,R})
f(q0,0,B) = (q1,{0,Z},{B,R})
f(q1,0,B) = (q1,{B,R},{B,Z})
f(q1,1,B) = (q1,{B,R},{0,R})
f(q1,B,B) = (q2,{B,Z},{0,R})
f(q2,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...
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...
Ya veremos como funciona...
lunes, 14 de abril de 2008
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... (0n)
SALIDA: ...B0100100000B... (0i110i210i31... 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.
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(q0,0,0,0) = (q1,{0,L},{0.Z},{0,R})
f(q1,B,0,0) = (q2,{$,L},{0,Z},{0,R})
f(q2,B,0,0) = (q3,{0,Z},{0,Z},{0,R})
f(q3,0,0,0) = (q3,{0,Z},{0,Z},{0,R})
f(q3,0,0,B) = (q4,{0,Z},{0,Z},{$,R})
f(q4,0,0,B) = (q4,{X,R},{X,R},{B,Z})
f(q4,$,0,B) = (q5,{$,L},{0,Z},{B,Z})
f(q5,X,0,B) = (q5,{0,L},{0,Z},{B,Z})
f(q5,B,0,B) = (q4,{B,R},{0,Z},{0,Z})
f(q4,0,$,B) = (q5,{0,L},{0,L},{B,Z})
f(q5,X,X,B) = (q5,{0,L},{0,L},{B,Z})
f(q5,B,X,B) = (q6,{0,R},{0,L},{B,Z})
f(q6,0,X,B) = (q6,{0,Z},{0,L},{B,Z})
f(q6,0,$,B) = (q4,{0,Z},{$,R},{B,Z})
f(q4,$,$,B) = (q7,{$,L},{$,L},{B,Z})
f(q7,X,X,B) = (q7,{Q,L},{0,L},{0,R})
f(q7,B,X,B) = (q8,{0,Z},{0,L},{1,R})
f(q8,0,$,B) = (q4,{0,Z},{$,R},{B,Z})
f(q7,B,$,B) = (q9,{B,R},{B,R},{B,Z})
f(q9,0,0,B) = (q9,{B,R},{B,R},{B,Z})
f(q9,B,$,B) = (q10,{B,Z},{B,Z},{B,Z})
f(q10,B,B,B) = ESTADO FINAL
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... (0n)
SALIDA: ...B0100100000B... (0i110i210i31... 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(q0,0,0,0) = (q1,{0,L},{0.Z},{0,R})
f(q1,B,0,0) = (q2,{$,L},{0,Z},{0,R})
f(q2,B,0,0) = (q3,{0,Z},{0,Z},{0,R})
f(q3,0,0,0) = (q3,{0,Z},{0,Z},{0,R})
f(q3,0,0,B) = (q4,{0,Z},{0,Z},{$,R})
f(q4,0,0,B) = (q4,{X,R},{X,R},{B,Z})
f(q4,$,0,B) = (q5,{$,L},{0,Z},{B,Z})
f(q5,X,0,B) = (q5,{0,L},{0,Z},{B,Z})
f(q5,B,0,B) = (q4,{B,R},{0,Z},{0,Z})
f(q4,0,$,B) = (q5,{0,L},{0,L},{B,Z})
f(q5,X,X,B) = (q5,{0,L},{0,L},{B,Z})
f(q5,B,X,B) = (q6,{0,R},{0,L},{B,Z})
f(q6,0,X,B) = (q6,{0,Z},{0,L},{B,Z})
f(q6,0,$,B) = (q4,{0,Z},{$,R},{B,Z})
f(q4,$,$,B) = (q7,{$,L},{$,L},{B,Z})
f(q7,X,X,B) = (q7,{Q,L},{0,L},{0,R})
f(q7,B,X,B) = (q8,{0,Z},{0,L},{1,R})
f(q8,0,$,B) = (q4,{0,Z},{$,R},{B,Z})
f(q7,B,$,B) = (q9,{B,R},{B,R},{B,Z})
f(q9,0,0,B) = (q9,{B,R},{B,R},{B,Z})
f(q9,B,$,B) = (q10,{B,Z},{B,Z},{B,Z})
f(q10,B,B,B) = ESTADO FINAL
domingo, 13 de abril de 2008
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 ¬¬'
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 ¬¬'
miércoles, 9 de abril de 2008
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...
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...
MT para N2:
Dado un entero n, obtener el cuadrado de ese entero.
Nota: El procedimiento es diferente al propuesto en clase.
ENTRADA: ...B000B...
SALIDA: ...B000000000B...
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 N2:
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 |
domingo, 6 de abril de 2008
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
:P
Suscribirse a:
Entradas (Atom)