Autómatas y Lenguajes Formales

Teoría de la Computación

1 ¿De qué se trata el curso?

Éste es un curso introductorio a la Teoría de la Computación. Se estudian diferentes modelos de cómputo (y problemas que pueden resolver), todos enmarcados en una jerarquía que irá apareciendo naturalmente conforme avancemos con el temario hasta llegar a la máquina automática propuesta por Alan M. Turing, hoy conocida con Máquina de Turing en su honor. Cada nivel de la jerarquía estará descrito por una máquina abstracta, un lenguaje formal y una gramática formal.

Este curso, además de ayudar a las personas estudiantes a obtener una noción formal de qué es un cómputo, permite adquirir herramientas necesarias para desempeñarse satisfactoriamente en cursos como Complejidad Computacional y Compiladores. Utilizaremos el temario oficial del curso como guía.

2 Evaluación del curso 

Opción A

50%

Exámenes 

20%

Tareas

20%

Implementación

10%

Mini-exámenes

+10%

Exposición (opcional)

Desglose de la evaluación de la opción A

Opción B

60%

Tareas-examen a casa 

20%

Implementación

20%

Mini-exámenes

+10%

Exposición (opcional)

Desglose de la evaluación de la opción B

3 Dinámica del curso

Detalles del curso para el semestre 2023-2

Modalidad

Clases presenciales en el Laboratorio de Ciencias de la Computación 3, último piso del Edificio Tlahuizcalpan.

Sesión de asesorías opcionales abiertas en la Sala de Maestros, primer piso del Edificio Tlahuizcalpan (junto al elevador)

Personal académico

Clases con el profesor: Lic. en C. Comp. Enrique Francisco Soto Astorga

Clases con el ayudante: José Manuel Madrigal Ramírez
Sesiones de asesoría opcionales abiertas: Ambos según disponibilidad (se avisará por Classroom y por la mensajería del grupo)

Horario (versión final actualizada el 29 de junio de 2023)

Lunes

Lab. C.C. 3
09:00 - 10:00

Martes

Lab. C.C. 3
09:00 - 10:00

Miércoles

Lab. C.C. 3
09:00 - 10:00

Jueves

Lab. C.C. 3
09:00 - 10:00

Viernes

Lab. C.C. 3
09:00 - 10:00

Sala de Maestros
15:00 - 19:00

4 Temario adaptado del oficial

Par este curso seguiremos el temario oficial y le haremos adaptaciones que consideramos vitales para darle un giro especial al contenido. De cualquier forma, la prioridad del curso será revisar al menos los tópicos incluídos en el temario oficial y, si hay tiempo y no hay paros, revisar lo extraordinario. Estamos considerando tiempos de holgura suficientes para sobrevivir a un paro, así que esperamos llegar al final del curso sin problemas.

I. Introducción

II. Gramáticas tipo-3, lenguajes regulares y máquinas finitas

III. Gramáticas tipo-2, lenguajes libres de contexto y máquinas con pila

IV. Gramáticas tipo-1, lenguajes dependientes de contexto y máquinas acotadas

V. Gramáticas tipo-0: lenguajes recursivamente enumerables y Máquinas de Turing

VI. Computabilidad y decidibilidad

VII. (opcional, tal vez no lleguemos) Temas selectos

5 Bibliografía básica

[1] Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2007). Introduction to Automata Theory, Languages, and Computation 3th Ed. Pearson Education.

[2] Viso-Gurovich, E. (2008) Introducción a la teoría de la computación. Las Prensas de Ciencias.