Ciencias de la Computación (plan 2013) 2024-2

Cuarto Semestre, Autómatas y Lenguajes Formales

Autómatas y Lenguajes Formales

Francisco Hernández Quiroz
Departamento de Matemáticas (cub. 025)
Facultad de Ciencias
E-mail: fhq@ciencias.unam.mx
Página web:
https://lya.fciencias.unam.mx/fhq/

Enlace a Google Classroom:

https://classroom.google.com/c/NjU2OTc3ODIzNzUy?cjc=spcny6j

Temario

1. Lenguajes regulares y autómatas finitos I

2. Lenguajes regulares y autómatas finitos II. Lenguajes independientes del contexto y
autómatas de pila

3. Lenguajes recursivamente enumerables y máquinas de Turing. Decidibilidad

4. Otros modelos computacionales

Aspectos “técnicos”

Requisitos

• Conceptos básicos de teoría de conjuntos.
• Inducción matemática.

Método de trabajo y evaluación

El curso será presencial pero la asistencia a las clases no es obligatoria y los alumnos con problemas de movilidad o con capacidad autodidacta sólo tendrán que asistir a los exámenes.

Habrá cuatro tareas y cuatro exámenes y dos reposiciones de exámenes parciales o un final. Los exámenes contarán el 80% de la calificación
y las tareas el 20% restante. El libro de texto principal es [5], con material adicional de [2, 1]. Los otros textos en la bibliografía son de consulta.

Bibliografía

[1] S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, 2004.

[2] Maxime Crochemore, Christophe Hancart y Thierry Lecroq, Algorithms on Strings, Cambridge University Press, 2001.

[3] Martin Davis, Computability, Complexity and Languages: Fundamentals of Theoretical Computer Science, Academic Press, 1983.

[4] J.E. Hopcroft y J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979.

[5] Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer, 1997.

[6] Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.

[7] Song Y Yan, Formal Languages and Machine Computation, World Scientific, 1998.