Teoría de Autómatas y Languajes Formales
Horario: Miércoles 8:00-11:00
Excepto los miércoles 12 de octubre y 2
de noviembre, cuando las clases se llevarán a cabo los viernes
14 de oct. y 4 de nov. respectivamente
Por el canal del IIMAS en : http://canal.iimas.unam.mx
Profesor:
Dr.
Luis Pineda
luis@leibniz.iimas.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 , 3 |
Tareas |
Soluciones |
Slides |
Slides a color |
| Ago 17 |
Presentación |
|
|
|
|
|
|
| Ago 17 |
Preliminares y
Languajes |
1.5 |
1.5 BJ1 |
|
|
Sesión
1 |
Sesión
1 |
|
Ago 24
|
Lenguajes
y operaciones con lenguajes |
1.5 |
1.5, 3.1.1 & BJ2
|
Tarea 1
|
Solución 1
|
Sesión
2 |
Sesión
2 |
|
Ago 31 (UJAT)
|
Lenguajes
y expresiones regulares |
3.1
|
3.1.2 & 3.1.3
|
Tarea 2
|
Solución 2
|
Sesión
3 |
Sesión
3 |
|
Ago 31 (UJAT)
|
Ejemplos
y aplicaciones de lenguajes regulares |
3.1
|
3.3
|
|
|
Sesión
4 |
Sesión
4 |
|
Sep 7
|
Autómata
finito |
3.2, 3.3
|
2.1 & 2.2 |
|
|
Sesión
5 |
Sesión
5 |
|
Sep 7
|
El
lenguaje aceptado por un AF |
3.3, 3.4
|
2.2.4 & 2.2.5
|
|
|
Sesión
6 |
Sesión
6 |
|
Sep 21
|
Operaciones con AF |
3.5
|
2.1 & 4.2.1
|
Tarea 3
|
Solución 3
|
Sesión
7 |
Sesión
7 |
|
Sep 21
|
AF no deteminísticos |
4.1, 4.2
|
2.3
|
|
|
Sesión
8 |
Sesión
8 |
|
Sep 28
|
AFN son AF |
4.1
|
2.3.5 & 2.3.6
|
Tarea 4
|
Solución 4
|
Sesión
9 |
Sesión
9 |
|
Sep 28
|
AFN con transiciones vacías |
4.2
|
2.5
|
|
|
Sesión
10 |
Sesión
10 |
|
Oct 5
|
Teorema de Kleene |
4.3
|
3.2
|
|
|
Sesión
11 |
Sesión
11 |
|
Oct 14 (UJAT)
|
Autómata mínimo |
5.1 & 5.2
|
4.4
|
Tarea 5
|
Solución 5
| Sesión
12 |
Sesión
12 |
|
Oct 19
|
Lema de bombeo |
5.3
|
4.1
|
Tarea 6
|
Solución 6
|
Sesión
13 |
Sesión
13 |
|
Oct 26
|
Examen parcial |
|
|
Examen
|
|
|
|
|
Nov 4 (UJAT)
|
Gramáticas Libres de Contexto (GLC) |
6.1
|
5.2, 5.2
|
|
|
Sesión
14 |
Sesión
14 |
|
Nov 4 (UJAT)
|
GLC & ER |
6.2, 6.3
|
5.3
|
|
|
Sesión
15 |
Sesión
15 |
|
Nov 9
|
Ambigüedad |
6.4, 6.5, 6.6
|
5.4 & 7.1
|
Tarea 7
|
Solución 7
|
Sesión
16 |
Sesión
16 |
|
Nov 9
|
Forma Normal de Chomsky |
6.4, 6.5, 6.6
|
5.4 & 7.1
|
|
|
Sesión
17 |
Sesión
17 |
|
Nov 16
|
Autómata de pila (AP) |
7.1, 7.2
|
6.1, 6.2
|
|
|
Sesión
18 |
Sesión
18 |
|
Nov 16
|
AP Determinístico |
7.3
|
6.4
|
|
|
Sesión
19 |
Sesión
19 |
|
Nov 23
|
AP para GLC |
7.4
|
6.2 & 6.3
|
Tarea 8
|
Solución 8
|
Sesión
20 |
Sesión
20 |
|
Nov 23
|
GLC de AP |
7.5
|
6.2 & 6.3
|
|
|
Sesión 21 |
Sesión 21 |
|
Nov 30
|
Lema de bombeo para LLC |
8.1
|
6.2
|
Tarea 9
|
Solución 9
|
Sesión 22 |
Sesión 22 |
|
Nov 30
|
Parseo top-Down |
7.6
|
|
|
|
Sesión 23 |
Sesión 23 |
|
Dic 7
|
Parseo bottom-up |
7.6
|
|
|
|
Sesión 24 |
Sesión 24 |
|
Dec 7
|
Máquina de Turing, Problema del Paro & Tesis de Church |
9 |
|
|
|
Sesión 25 |
Sesión 25 |
|
Enero 11, 10:00 Hrs
|
Examen Final |
|
|
Examen |
|
|
|
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%