Ciencias de la Computación (plan 2013) 2022-1

Cuarto Semestre, Autómatas y Lenguajes Formales

La presentación del curso será el lunes 30 de agosto a la hora de clase (la liga a meet se publicará aquí dpj-wzyo-ddp) .

https://sites.google.com/ciencias.unam.mx/aylf221/AyLF

DINÁMICA DEL CURSO (classroom zxohdle)

Sesiones síncronas (2 de clase y 1 de ayudatía).

Notas y boletines de ejercicios para trabajarse, idealmente en hora de clase, de forma individual.

Solución de dudas por correo electrónico o classroom.

Evaluaciones por medio de classroom.

TEMARIO

1. Introducción: Cadenas y lenguajes; Definiciones inductivas; Inducción estructural.

2. Lenguajes regulares: Expresiones regulares; Autómatas finitos (AFD, AFN, AFNε); Teorema de Kleene (Derivadas de expresiones regulares y ecuaciones de lenguajes); Teorema de Myhill-Nerode (Minimización de autómatas)

3. Lenguajes libres de contexto: Gramáticas y formas normales; Autómatas de Pila; Ambigüedad; Algoritmos y procedimientos de decisión.

4. Máquinas de Turing: Definición y diseño de máquinas de Turing; Lenguajes recursivos y recursivamente enumerables.

EVALUACIÓN

Toda entrega tardía sólo puede hacerse dentro de las 24hrs siguientes a la fecha determinada y se evaluará sobre el 80 % de la calificación.

• 5 exámenes individuales cuyas fechas de aplicación estarán fijas

• Ejercicios semanales individuales

• Actividades adicionales