| Semana |
Lunes 4-5 @ MEM-108 |
Martes 6-8 @ MEM-105 |
Miércoles 4-5 @ MEM-106 |
| I |
06/01: Introducción al curso. |
07/01: Conceptos básicos de lenguajes.
Introducción a autómatas finitos. |
08/01: Autómata finito determinístico (AFD).
Lenguajes regulares (LR).
Clausura de LRs por union, intersección, diferencia, complementación, y homomorfismo inverso. |
| II |
13/01: Autómata finito no-determinístico (AFND).
Equivalencia entre AFDs y AFNDs.
Clausura de LRs por concatenación y estella de Kleene. |
14/01: Especificación del proyecto. |
15/01: Expresiones regulares (ER).
Equivalencia entre AFDs, AFNDs y ERs.
Clausura de LRs por inversión, y homomorfismo. |
| III |
20/01: Diseño de autómatas.
Ejemplos y ejercicios. |
21/01: Discusión del proyecto. |
22/01: Teorema de Myhill-Nerode.
Minimización de AFDs: algoritmo O(n2s) de Moore.
Usos del Teorema de Myhill-Nerode. |
| IV |
27/01: Limitaciones de los lenguajes regulares.
Lema de bombeo.
Problemas de decisión: vacío e infinitud.
Clausura de lenguajes regulares por cociente.
Conjuntos diferenciadores. |
28/01: Primera entrega del proyecto (5%). |
29/02: Autómatas con salida.
Máquinas de Moore y Mealy. |
| V |
03/02: Repaso. Ejercicios. |
04/02: Discusión del proyecto. |
05/02: Examen suspendido por falta de servicios. |
| VI |
10/02: Lenguajes libre de contexto.
Gramáticas libre de contexto (GLC).
Propiedades de clausura.
Ambiguedad.
Ejemplos. |
11/02: Discusión del proyecto. |
12/02: Examen 1 (20%). |
| VII |
17/02: Problemas de decisión para GLCs.
Formas normales.
Autómatas de pila (AP). |
18/02: Segunda entrega del proyecto (10%). |
19/02: Equivalencia entre GLCs y APs.
Ejemplos y ejercicios. |
| VIII |
24/02: Carnaval. |
25/02: Carnaval. |
26/02: Limitaciones de los lenguajes libre de contexto.
Lema de bombeo para lenguajes libre de contexto.
Lema de Ogden. |
| IX |
02/03: Problemas de decisión para lenguajes libre de contexto: lenguaje vacío, finito, pertenencia.
Algoritmo CYK.
Máquinas de Turing.
Variantes. |
03/03: (Suspendido) Quiz (10%).
Discusión del proyecto. |
04/03: Repaso y ejercicios resueltos para lenguajes libre de contexto. |
| X |
09/03: Examen 2 (20%). |
10/03: Discusión del proyecto. |
11/03: Máquinas de Turing (MT).
Variantes.
Ejemplos y ejercicios. |
| XI |
16/03: Decidibilidad.
Problema de aceptación para MTs (ATM).
Diagonalización. |
17/03: Discusión del proyecto. |
18/03: Reducciones.
Problema de parada para MTs (HaltTM).
Indecidibilidad via reducciones.
Problema de Correspondencia de Post (PCP). |
| XII |
23/03: Teorema de Rice. |
24/03: Entrega final del proyecto (15%). |
25/03: Examen 3 (20%). |