Intersección de dos LRE

Las clases Lre de los lenguajes recursivamente enumerables son cerradas respecto a la intersección. Para demostrarlo deberemos considerar que: Si M1 y M2 son máquinas que siempre se paran y aceptan dos lenguajes recursivos, esta máquina aceptará su intersección. Si alguna cadena del lenguaje intersección hace parar M1 o M2, entonces la nueva máquina M también parará por lo que se acepta la interseccíon en ambos casos.


Aprovechamos la entrada para hacer el resumen semanal. Tras la semana del puente en la que expusimos y estuvimos haciendo mil tareas de talf durante el lunes,marte y miercoles nos tomamos unas minivacaciones y hemos vuelto a quedar hoy viernes a las 9 de la mañana para dejar lista esta tarea. Hemos hecho una busqueda en la biblioteca por que no sabiamos como demostrar nada... y hemos encontrado unos libros mu majetes de donde hemos sacado información bastante aclaratoria xDD.
Habiamos quedado también para puntuar todas las tareas pendientes,pero tras la ardua tarea de búsqueda de información hemos pensado que la puntuación la dejamos pa la semana que viene xDDDD

Generador a(n)b(2n)a(n)

Bueno, esta vez me he tocado a mi poner esta entrada y voy apurando sobre la fecha limite de entrega. Bien por nosotros!!!

Entremos en materia. Esta MT, hemos decidido que sera un modelo multicinta, la cual constara de 2 cintas. La primera cinta servira para llebar un conteo de las n (nosotro utilizamos el 0) y la segunda se ira mostrando las cadenas generadas.
En este caso la verdad que no nos importa la posición de los cabezales, ya que en q0 nos encontraremos con las dos cintas completamente en blanco.

Reconocer cadenas que los grupos de 0´s son crecientes

Bueno pos esta vez pero que no sea de precedente subo yo unos de los ejercicios propuestos. Comcretamente subo la MT y su modificacion usando multicabezal para poder saber si una cadena del estilo 0010001000010000 los ceros van de forma creciente.

Bueno primero la MT con un solo cabezal y una sol cinta:


Ahora la MT modificada usando dos cabezales:


PD: si os extrañais por lo de q27 no le hagais mucho caso es una marca personal del grupo. Fue despues de la MT de los divisores que terminamos hasta las... orejas y decidimos llamar a estads finales qXX donde XX es un numero alto xD simplemente.

un saludo gente

Conteo Grupo de Ceros

MAQUINA DE TURING CLASICA
Cadena de Entrada: ...B00100100B...
Cadena de Salida: ...B000B...

El cabezal empieza a la izquierda de todo, leyendo un blanco. Empieza a recorrer la cadena poniendo a blanco los ceros que lee, hasta llegar a un 1. Al leer un 1, se va a la derecha hasta encontrar un blanco, se salta dicho blanco y escribe un cero, entonces vuelve hasta el 1, lo pone a blanco y empieza de nuevo con los ceros. En el ultimo paso encuentra un Blanco no un 1, por tanto pone ese blanco a 0 y de ese modo la cadena queda así ...B000B...




MAQUINA DE TURING MULTICABEZAL
Cadena de Entrada: ...B00100100B...
Cadena de Salida: ...B000B...

Empiezan los dos cabezales en el primer blanco, se desplaza el segundo cabezal hasta el final. Una vez alli,empieza a moverse el primer cabezal,cada vez que encuentre un 1, el segundo cabezal pondra un 0 y asi hasta el final.

F(Q0,B,B)= (Q1, {B,Z},{B,R})

F(Q1,B,0)= (Q1, {B,Z},{0,R})

F(Q1,B,1)= (Q1, {B,Z},{1,R})

F(Q1,B,B)= (Q2, {B,R}{B,R})

F(Q2,0,B)=(Q2, {B,R},{B,Z})

F(Q2,1,B)= (Q2, {B,R},{0,R})

F(Q2,B,B)= (Q4, {B,R}{0,R})

Q4 ESTADO FINAL

MT Divisores Multicabezal

Partimos de la misma idea que con la MT simple, salvo que con esta vez no buscaremos la mitad del numero a obener los divisores, ya que eso nos aumentaria considerablemente el numero de simbolos en el alfabeto de la cinta.

Para esta MT partimos con los cabezales puestos en posicion:
Bq0$000q0$q0B

F(q_0, $, $, B)=(q1,{$,L},{$,L},{B,Z})
F(q0, B, 0, B)=(q7,{B,Z},{0,Z},{B,Z})
F(q0, 0, 0, B)=(q0,{0,R},{0,Z},{B,Z})
F(q0, $, 0, B)=(q3,{$,L},{0,Z},{B,Z})
F(q0, 0, $, B)=(q0,{0,R},{$,Z},{B,Z})
F(q1, B, 0, B)=(q1,{0,L},{0,L},{B,Z})
F(q1, B, $, B)=(q2,{B,R},{$,R},{B,Z})
F(q1, 0, 0, B)=(q3,{0,Z},{0,Z},{B,Z})
F(q2, $, $, B)=(q3,{$,L},{$,L},{B,Z})
F(q2, 0, 0, B)=(q2,{0,R},{0,R},{B,Z})
F(q2, $, 0, B)=(q2,{$,Z},{0,R},{B,Z})
F(q3, B, 0, B)=(q0,{B,R},{0,Z},{B,Z})
F(q3, B, $, B)=(q4,{B,R},{$,R},{B,Z})
F(q3, 0, 0, B)=(q3,{0,L},{0,L},{B,Z})
F(q3, 0, $, B)=(q5,{0,L},{$,Z},{B,Z})
F(q4, $, $, B)=(q5,{$,L},{$,Z},{1,R})
F(q4, 0, 0, B)=(q4,{0,R},{0,R},{0,R})
F(q4, $, 0, B)=(q4,{$,Z},{0,R},{B,Z})
F(q5, B, 0, B)=(q6,{B,R},{$,R},{B,Z})
F(q5, 0, $, B)=(q5,{0,L},{$,Z},{B,Z})
F(q6, 0, 0, B)=(q6,{0,Z},{0,R},{B,Z})
F(q6, 0, $, B)=(q0,{B,R},{$,Z},{B,Z})
F(q7)=Estado Final

Dentro de poco publicaremos ese tocho de arriba como tabla tambien.

MT Divisores

Objetivo: Dado un número, hallar sus divisores

Entrada: ...$0000$...

Salida: ...$0000$00...

La idea básica es leer el número(empezando con el cabezal a la izquierda del todo, por tanto lo primero que encontrará será un $), encontrar la mitad (marcarla como blancos). Con esto conseguimos el máximo divisor, por tanto lo copiamos al principio de la cadena y vamos comparando si es o no divisor. En caso de serlo, copiamos el número(el de mas a la izquierda '00'$00BB$B...) a la derecha, y ponemos un 1 para separalo del siguiente divisor(..00$00BB$001...) y le borramos un 0 desde la izquierda al candidato (..0$00BB$001...). En caso de que no sea divisor borramos el cero de la más a la izquierda y empezamos de nuevo(..0$00BB$...)

Este ejercicio lo hemos hecho a lo largo de la semana, quedando por las mañanas el viernes 11, y lunes,martes y miercoles de esta semana.
Problemas... un monton xDD, desde borrar todo y tener que empezar desde el principio... hasta si marcar o no un $, pero esto ya lo pondra david en una entrada lol.

MT División

Objetivo: Dados dos enteros n y m, obtener resto$cociente.

Entrada: ...B00000001000B...

Salida: ...B0$00B