Información General

• Profesor: Olivia Gutú

• Localización: Cubículo 2, edificio 3K-4

• Horario: Lunes y jueves de 11:00 a 13:00 hrs., viernes de 12:00 a 13:00 hrs.

• Aula: 3K4-A203.

• Asesorías: Estaré disponible todos los días de 13:00 a 14:00 hrs.

• Textos:

  • Teoría de autómatas y lenguajes formales, Olivia Gutú. Notas de clase que puedes descargar aquí. Un texto previo Un primer curso en teoría de autómatas y lenguajes formales (Pearson, 2014) la puedes sacar de la biblioteca.

  • Introduction to automata theory, languajes and computation, 3.ª ed. Hopcroft, J. E.; Motwani, R. y Ullman, J., Pearson/Addison Wesley (2007). Este es un libro clásico de soporte y consulta.

Contenido de la materia

• Alfabetos, cadenas y lenguajes
  • Alfabetos y cadenas
  • Lenguajes
• Autómatas finitos deterministas
  • Definición de autómata finito determinista
  • Lenguaje de un autómata finito determinista
  • Minimización del número de estados (opcional)
• Autómatas finitos no-deterministas
  • Definición de autómata finito no-determinista
  • Autómatas con transiciones instantáneas
  • Caracterización de los autómatas finitos
• Lenguajes regulares
  • Definción de expresión y lenguaje regular
  • De autómatas finitos a expresiones regulares
  • De expresiones regulares a autómatas finitos
  • Lema de bombeo para lenguajes regulares
• Autómatas a pila
  • Definición de autómata a pila
  • Descripciones instantáneas
  • Aceptación por estado final y por pila vacía
  • Autómatas a pila deterministas
• Gramáticas libres de contexto
  • Definición de gramática
  • Lenguaje aceptado por una gramática
  • Árboles de derivación y ambigüedad
• Lenguajes libres de contexto
  • De gramáticas a autómatas a pila
  • De autómatas a pila a gramáticas
  • Lema de bombeo para lenguajes libres de contexto
  • Propiedades de los lenguajes libres de contexto
  • Algoritmo CYK
• Máquinas de Turing
  • Definición y movimientos de una máquina de Turing
  • La máquina de Turing como algoritmo
  • La máquina de Turing como cadena binaria
  • Problemas decidibles y un poco de filosofía

Calificación

La calificación del curso se realiza de la siguiente manera:

1. Exámenes semanales/quincenales (60%)
2. Examen final (20%)
3. Participación (incluye exposiciones) (20%)