Stanford MOOC Automata W4

Automata Theory At Coursera

Ultima semana del curso Automata. Ahora sí que se puso pesado el asunto.

El primer tema fue la conversión entre CFG (context-free grammars) y PDA (Pushdown automaton), en ambos sentidos. Pesada por lo “talachudo” que es el asunto.

El segundo tema fue la revisión del equivalente del pumping lemma para las CFG. Esto se revisó tanto en su declaración como en su aplicación.

Poniéndose un poco más pesado el asunto, el tercer tema fue el de las propiedades de decisión de las CFG:

  • Si una cadena en particular pertenece al lenguaje.
  • Si el lenguaje es vacío.
  • Si el lenguaje es infinito.

y sus propiedades de cerradura:

  • Si un lenguaje en particular es cerrado bajo unión, concatenación, la cerradura de Kleene, reversiones, homomorfismos u homomorfismos inversos,…
  • pero no bajo intersección o diferencia.

Los últimos dos temas finalmente rayan en el corazón de las matemáticas y computación. El primero de éstos fue sobre indecidibilidad. Esto puede llevar a muchos a evocar de inmediato a Gödel pero no, en este caso, ni siquiera se mencionó. Lo primero que se vio al respecto fue sobre las nociones de conjuntos contables y no contables, llevando a explicar los diferentes infinitos existentes. En el segundo se dio una introducción de la máquina de Turing (presentando las nociones de solución a un problema por el alcanzar un estado final, algoritmo y la detención del mecanismo) y las nociones de lenguajes recursivos y recursivamente enumerables.

El curso concluye en la semana en la que este post es publicado. Restan dos ejercicios de programación cuya fecha de vencimiento es para finales de mes. Sólo cuentan por un 5% de calificación cada uno, pensados para que sean realizados por aquellos que quieren terminar este curso con una nota de distinción. Aún no decido si los hago o no.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s