Hub LF Materiales

Materiales

Libros de referencia, cronograma semanal y recursos para Lenguajes Formales.

EAFIT Universidad

2026-1 Semestre

ST0270 Codigo

17 Semanas

Libros de referencia

Automata and Computability

Kozen, Dexter C.

Third printing 2012 Springer

Compilers: Principles, Techniques, & Tools

Aho, Alfred V., Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman

2nd ed. 2006 Addison-Wesley

Formal Languages: Origins and Directions

Greibach, S. A.

1981 Annals of History of Computing 3.1

Evaluacion

Parcial 1

Semana 5

20%

Parcial 2

Semana 10

20%

Parcial 3

Semana 16

20%

Proyecto Final

Semana 17

20%

Tarea 1

Semana 4

10%

Tarea 2

Semana 7

10%

Cronograma semanal

Introducción al curso. Introducción a los lenguajes formales, las gramáticas y los modelos de computación.

U1: Introducción a los lenguajes formales Kozen (2012, Lecture 1), Aho et al. (2006, §1.1-1.2), Greibach (1981)

Teoría de los lenguajes formales: Definiciones y operaciones básicas.

U1: Introducción a los lenguajes formales Kozen (2012, Lecture 2)

Lenguajes regulares. Autómatas finitos deterministas.

U2: Lenguajes regulares y autómatas finitos Kozen (2012, Lectures 3 y 4)

Autómatas finitos no deterministas. Propiedades de clausura de los lenguajes regulares.

U2: Lenguajes regulares y autómatas finitos Kozen (2012, Lectures 5-6)

Expresiones regulares. Limitaciones de los autómatas finitos.

U2: Lenguajes regulares y autómatas finitos Kozen (2012, Lectures 8, 11)

Lenguajes libres de contexto. PARCIAL 1.

U3: Lenguajes libres de contexto Kozen (2012, Lectures 19, 20) Parcial 1

Autómatas de pila.

U4: Autómatas de pila y propiedades de los LLC Kozen (2012, Lectures 23, 24)

Propiedades de los lenguajes libres de contexto. Limitaciones.

U4: Autómatas de pila y propiedades de los LLC Kozen (2012, Lecture 21)

Máquinas de Turing. Computabilidad efectiva. Clasificación de Chomsky.

U5: Máquinas de Turing y computabilidad Kozen (2012, Lectures 28, 29)

Análisis descendente recursivo.

U6: Análisis sintáctico descendente y ascendente Aho et al. (2006, §4.4.1)

Conjuntos First y Follow. PARCIAL 2.

U6: Análisis sintáctico descendente y ascendente Aho et al. (2006, §4.4.2) Parcial 2

Análisis predictivo no recursivo: gramáticas LL(1), tabla y algoritmo.

U6: Análisis sintáctico descendente y ascendente Aho et al. (2006, §4.4.3, §4.4.4)

Reducciones. Análisis reducción-desplazamiento.

U6: Análisis sintáctico descendente y ascendente Aho et al. (2006, §4.5.1-4.5.4)

Análisis descendente: Ítems, autómata LR(0).

U6: Análisis sintáctico descendente y ascendente Aho et al. (2006, §4.6.1, §4.6.2)

Análisis descendente: Análisis sintáctico SLR.

U6: Análisis sintáctico descendente y ascendente Aho et al. (2006, §4.6.3, §4.6.4)

Traducción puramente sintáctica: definiciones, órdenes de evaluación.

U7: Traducción puramente sintáctica Aho et al. (2006, §5.1, §5.2)

Traducción puramente sintáctica: aplicaciones, esquemas, implementación. PARCIAL 3.

U7: Traducción puramente sintáctica Aho et al. (2006, §5.3, §5.4, §5.5) Parcial 3