Programa general

• Preliminares: lenguajes formales.

• Autómatas finitos y lenguajes regulares

• Autómatas de pila y lenguajes libres de contexto

• Decidibilidad y computabilidad: Máquinas de Turing

• Análisis sintáctico

• Traducción puramente sintáctica

Programa del curso

programa-si2002 

programa-st0270 

Plan semanal

syllabus-20261 

Libros guía

• Aho, Alfred V., and Alfred V. Aho, eds. Compilers: Principles, Techniques, & Tools. 2nd ed. Boston: Pearson/Addison Wesley, 2007.

• Kozen, Dexter C. Automata and Computability. New York, NY: Springer New York, 1997. https://doi.org/10.1007/978-1-4612-1844-9.

  • Disponible en https://ebookcentral-proquest-com.ezproxy.eafit.edu.co/lib/eafit/detail.action?docID=3076071. Requiere credenciales de EAFIT.

Diapositivas de clase

• Sergio Ramírez Rico

• Andrés Sicard Ramírez

Material de estudio

Parciales semestres anteriores

Referencias adicionales

• Peter Linz [1990] (2016). An Introduction to Formal Languages and Automata. 6.a ed. Jones & Bartlett Learning.

• Michael Sipser [1996] (2012). Introduction to the Theory of Computation. 3.a ed. International Edition. Cengage Learning.

Ejercicios

• Teoría de los lenguajes formales

  • Kozen 2012: 

    • Demostrar propiedades de la concatenación, página 9

    • Demostrar propiedades de las operaciones de conjuntos, páginas 11 a 13.

• Lenguajes regulares y autómatas finitos

  • Kozen 2012:

    • Homework 1: 1, 2, 3.

    • Homework 2: 1, 2.

    • Homework 3: 1, 2.

    • Homework 4: 1a, 1d.

  • Linz 2016:

    • Section 2.1: 5, 7.

    • Section 2.2: 8, 11.

    • Section 2.3: 3, 5.

• Lenguajes libres de contexto y autómatas de pila

  • Kozen, D. (2012): 

    • Homework 5: 1, 2, 3, 4.

    • Homework 6: 1, 2.

    • Homework 7: 2, 

    • Miscellaneous Exercises: 69, 70, 71, 72, 73(a), 76, 77, 91.

  • Linz 2016:

    • Section 5.1: 7, 8, 9, 10, 13.

    • Section 6.2: 3, 5.

    • Section 7.1: 3, 4, 11.

    • Section 7.2: 3, 6, 9.

• Máquinas de Turing

  • Kozen, D. (2012):

    • Homework 8: 1.

    • Miscellaneous Exercises: 96, 97.

  • Sipser (2012):

    • Ejercicios: 3.1, 3.8.

Actividades evaluativas

• Tres parciales, 20% cada uno. Semanas 5, 10 y 16.

• Dos tareas prácticas, 10% cada una. Semanas 4 y 7.

• Proyecto del curso, 20%. Semana 17.

Profesores

• Adolfo Andrés Castro Sánchez

• César Augusto Guerra Villa

• Oscar Andrés Rodríguez Cifuentes

• Sergio Steven Ramírez Rico

Atención a estudiantes

Pendiente

Conducto regular

1. Profesor del curso

2. Coordinador de la materia: Sergio Steven Ramírez Rico (ssramirezr@eafit.edu.co)

3. Jefe del programa de Ingeniería de Sistemas: Andrés Sicard Ramírez (pregrado.is@eafit.edu.co)