Teoría de Autómatas y Lenguajes Formales


  Horario: Martes & Jueves 10:00-11:30

  Salón 201-202, 2o. piso Edificio del Posgrado

Profesor:
  Dr. Luis Pineda
  lpineda@unam.mx
  Departamento de Ciencias de la Computación
  IIMAS, UNAM
  Tel: 55-56-22-36-18
  Asesoría previa cita

Contenido:
  • Textos
  • Lecturas adicionales
  • Calendario tentativo
  • Política de calificaciones

    • Textos
  • Introduction to Languages and the Theory of Computation (Third edition) John Martin, McGraw Hill, 2003
  • Introduction to Automata Theory, Languages and Computation (Second Edition) John E. Hopcroft, Rajeev Motwani and Jeffery D. Ullman Addison Wesley, 2001
    • Lecturas adicionales:
  • Computability and Logic (Third Edition) George S. Boolos and Richard C. Jeffrey Cambridge University Press, 1989.
    • Calendario tentativo:
     
     
    Clases
    		 Título y Video
    		 Lecturas 1 Lecturas adicionales 2 , 345 Tareas Slides Slides color
    Ago 6 Presentación          
    Ago 8 Preliminares y Languajes 1.5 1.5 BJ1   Sesión 1 Sesión 1
    Ago 13
    		 Lenguajes y operaciones con lenguajes 1.5
    1.5, 3.1.1 & BJ2
    		 Tarea 1 Sesión 2 Sesión 2
    Ago 15
    		 Lenguajes y expresiones regulares
    3.1
    3.1.2 & 3.1.3
    		   Sesión 3 Sesión 3
    Ago 20
    		 Soluciones tarea 1          
    Ago 22
    		 Ejemplos y aplicaciones de lenguajes regulares
    3.1
    3.3
    		   Sesión 4 Sesión 4
    Ago 27
    		 Autómata finito
    3.2, 3.3
    		 2.1 & 2.2   Sesión 5 Sesión 5
    Ago 29
    		 El lenguaje aceptado por un AF
    3.3, 3.4
    2.2.4 & 2.2.5
    		   Sesión 6 Sesión 6
    Sep 3
    		 Operaciones con AF
    3.5
    2.1 & 4.2.1
    		 Tarea 2 Sesión 7 Sesión 7
    Sep 5
    		 AF no deteminísticos
    4.1, 4.2
    2.3
    		   Sesión 8 Sesión 8
    Sep 10
    		 Soluciones tarea 2          
    Sep 12
    		 AFN son AF
    4.1
     2.3.5 & 2.3.6
    		 Tarea 3 Sesión 9 Sesión 9
    Sep 17
    		 AFN con transiciones vacías
    4.2
    2.5
    		   Sesión 10 Sesión 10
    Sep 19
    		 Soluciones tarea 3          
    Sep 24
    		 Teorema de Kleene
    4.3
     3.2
    		   Sesión 11 Sesión 11
    Sep 26
    		 Autómata mínimo
     5.1 & 5.2
    4.4
    		   Sesión 12 Sesión 12
    Oct 1
    		 Lema de bombeo
    5.3
     4.1
    		 Tarea 4 Sesión 13 Sesión 13
    Oct 3
    		 Gramáticas Libres de Contexto (GLC)
    6.1
    5.2, 5.2
    		   Sesión 14 Sesión 14
    Oct 8
    		 Soluciones tarea 4          
    Oct 10
    		 Examen parcial          
    Oct 15
    		 GLC & ER
    6.2, 6.3
    5.3
    		   Sesión 15 Sesión 15
    Oct 17
    		 Ambigüedad
    6.4, 6.5, 6.6
    5.4 & 7.1
    		 Tarea 5 Sesión 16 Sesión 16
    Oct 22
    		 Forma Normal de Chomsky
    6.4, 6.5, 6.6
    5.4 & 7.1
    		   Sesión 17 Sesión 17
    Oct 24
    		 Soluciones tarea 5          
    Oct 29
    		 Autómata de pila (AP)
    7.1, 7.2
    6.1, 6.2
    		   Sesión 18 Sesión 18
    Oct 31
    		  AP Determinístico
    7.3
    6.4
    		   Sesión 19 Sesión 19
    Nov 5
    		 AP para GLC
    7.4
    6.2 & 6.3
    		  Tarea 6 Sesión 20 Sesión 20
    Nov 7
    		 GLC de AP
    7.5
    6.2 & 6.3
    		   Sesión 21 Sesión 21
    Nov 12
    		 Soluciones tarea 6          
    Nov 14
    		 Parseo top-Down
    7.6
    		     Sesión 22 Sesión 22
    Nov 19
    		 Parseo bottom-up
    7.6
    		     Sesión 23 Sesión 23
    Nov 21
    		 Lema de bombeo para LLC
    8.1
    6.2
    		 Tarea 7 Sesión 24 Sesión 24
    Nov 26
    		 Máquina de Turing, Problema del Paro & Tesis de Church 9     Sesión 25 Sesión 25
    Nov 28
    		 Soluciones tarea 7          
    Dic 3
    		 Examen Final          
    1 X.Y: John Martin, Cap. X, Sec. Y.
    2 X.Y: Lecturas de Hopcroft, Motwani and Ullman, a menos que se especifique otra cosa
    3 BJX: Boolos and Jeffrey, Cap. X.
    Política de calificaciones
  • Tareas:  20%
  • Examen parcial: 40%
  • Examen final 40%