Resumen Semanal (26 al 30) FIN

Lunes: -----

Martes: Quedamos con el grupo 12. Pusimos en común los resumenes de temas 6 y 7. Comentamos posibles relaciones entre ambos, como iba a ser la realización del tema 8 y sus posibles relaciones con los dos temas anteriores. Además, corregimos su Tarea 5 que era la que nos correspondia y pusimos en común posibles soluciones e ideas para la última tarea.

Miercoles: Realización de la Tarea 6 y publicación en el blog.

Jueves:  Quedamos con el grupo 12. Nos repartimos la exposición para el viernes en trozos y empezamos a hacernos la idea e intentar perder el miedo escénico, que no es pequeño :p.

Viernes:

Resumen Semanal (19 al 25)

Esta semana nos hemos dedicado a prepararnos la exposición del dia 30. Quedamos para resumir "a mano" el tema 6, para posteriormente, crear el esquema en FreeMind.

Una vez obtuvimos dicho resumen, lo pasamos a "limpio".

Al día siguiente comprobamos si teníamos la información necesaria, si estaba bien organizado, corregimos varios fallos tontos, etc.

Finalmente nos pusimos en contacto con el Grupo 12 para ver como evolucionaba su parte de la exposición y para juntarnos para la siguiente semana y realizar conjuntamente el resumen del tema 8. Respecto a tareas del Blog, no hicimos nada, ya que teníamos todo al día, tanto en realización como en corrección de tareas.

Última Tarea

a) ¿Cómo se podría construir un generador de todos los códigos de Máquinas de Turnig sintácticamente correctos?

Para realizar dicho generador, utilizaremos un generador canónico que, empezando por la cadena vacía, vaya creando cadenas con el alfabeto restringido {0,1,B} , es decir, generará 0,1,00,01,10... etc. Luego, dicha cadena, se tendrá que pasar a un autómata reconocedor de MT's (como el que se dibujó en clase a última hora) para que decida si ese código generado pertenece o no a una MT. 

Por tanto la solución sería la que indica el dibujo:

La cosa es que hay infinitas máquinas de turing, por tanto por muchos códigos de MT que construyamos, siempre nos quedarán códigos por obtener.

b) Por el mismo motivo que hemos expuesto al final del apartado a), nos decantamos por la opción 2) ya que aunque nos salgan infinitos códigos de máquinas, nunca voy a conseguir tenerlas todas.

Resumen Semanal (12 al 18)

Esta semana nos la hemos tomado de descanso. Como ya teniamos todas las tareas de demás grupos corregidas,  la tarea de la demostración la hicimos la semana anterior y de momento no tenemos que corregir ninguna de nuestras MT's, nos tomamos la semanita de descanso que ya tocaba :p.

Resumen Semanal (5 al 11)

Lunes:  - - - - - - - - 

Martes: Realización de la MT Generadora de AnB2nAn.

Miércoles: Preparación de la parte teórica, posibles tipos de demostración.

Jueves:  Corrección de la MT Generadora del grupo 13.

Viernes: Corrección de las MT's del grupo 4.

Sábado:  Repaso a la MT Generadora ya que encontramos un fallo, no hicimos un generador, simplemente un comprobador, por lo que nos tocó modificarla, pero ya está todo arreglado ;).

Domingo:  Realización en "bonito" de la demostración de La intersección de dos L.R. es un L.R.

Demostración : La intersección de dos LR's es un LR

Para demostrar este enunciado, nos hemos basado en teoremas anteriores, sobretodo en el 7.4, La unión de dos lenguajes recursivos es un lenguaje recursivo.

Para la realización de la demostración de este teorema, nos basamos en que para que un lenguaje intersección de dos lenguajes, solo acepta cadenas que pertenezcan a ambos lenguajes. Por tanto, procedemos a la demostración:

Sean L1 y L2 , L.R. ⇒ ∃ M1 , M2 | L1 = L(M1), L2 = L(M2) y M1 y M2 siempre paran:

- si x ∈ L1 , M1 acepta la cadena x y si x ∉ a L1 , M1 rechaza la cadena x.

- si x ∈ L2 , M2 acepta la cadena x y si x ∉ a L2 , M2 rechaza la cadena x.

Sea L = L1 ∩ L2 , ¿∃ M | L = L(M) y M siempre para? Sí, construyendo la máquina que se presenta en la figura:

La construcción es correcta puesto que

- si x ∈ L1 AND x ∈ L2 ⇒ x ∈ L1 ∩ L2 = L (M1 y M2 aceptan ⇒ M acepta)

- si x ∉ L1 OR x ∉ L2 ⇒ x ∉ L1 ∩ L2 = L (M1 ó M2 rechazan ⇒ M rechaza).

Por lo tanto, M siempre para y si x ∈ L, M acepta y si x ∉ L, M rechaza.

PD: Espero que no nos hagas pagar © por tus apuntes Gloria :p.

Resumen Semanal (28 al 4)

Lunes:  - - - - - - - - 

Martes: Realización de la MT Generadora de AnB2nAn.

Miércoles: Repaso a la MT Generadora y comprobación mediante descripciones instantaneas.

Jueves:  - - - - - - - -

Viernes:  - - - - - - - - 

Sábado:  Corrección de la MT de divisores multicabezal del grupo 3.

Domingo:  Corrección de la MT de divisores simple del grupo 3.