Semana 1Lenguajes regulares
Lenguajes y autómatas finitos
- TeoríaPresentación · Cadenas, lenguajes y problemas de decisión · Autómatas finitos deterministas · Construcción del producto
- LabUn simulador de DFA
Universidad Nacional de Ingeniería
Qué es una computadora como objeto matemático, qué problemas no puede resolver ningún programa y cuáles exigen demasiado tiempo o memoria. Cada construcción se demuestra y se programa en C++.

Este curso continúa Análisis y Diseño de Algoritmos y usa las demostraciones de Matemática Discreta. Antes del primer laboratorio, revisen la guía del entorno y su cuenta de GitHub. Para la primera sesión, lean el capítulo 1 de los apuntes.
Autómatas finitos, expresiones regulares, lema de bombeo y minimización.
Semanas 1–4IIGramáticas, forma normal de Chomsky, CYK y autómatas de pila.
Semanas 5–6IIIMáquinas de Turing, el problema de la parada, reducciones, Rice e incompletitud.
Semanas 7–11IVP y NP, Cook-Levin demostrado, PSPACE, jerarquías y azar.
Semanas 12–16