Temas Subtemas
Preliminares matemáticos Lógica elemental
Teoría de conjuntos
Relaciones y funciones
Inducción matemática
Cardinalidad
Lenguajes formales Alfabetos, palabras y lenguajes
Operaciones con palabras
Operaciones con lenguajes
Lenguajes regulares y autómatas finitos Lenguajes sobre alfabetos
Lenguajes regulares y expresiones regulares
Autómata finito determinista (AFD)
Autómata finito no determinista (AFN)
Equivalencia entre AFNs y AFDs
Autómata finito con epsilon transiciones
Autómatas finitos y expresiones regulares
Aplicaciones prácticas de las expresiones regulares y de los autómatas finitos
Lenguajes independientes del contexto y autómatas de pila Gramáticas regulares
Gramáticas regulares y lenguajes regulares
Gramáticas independientes del contexto
Arboles de derivación y ambigüedad
Simplificación de gramáticas independientes del contexto
Propiedades de los lenguajes independientes del contexto
Algoritmos de análisis sintáctico
Autómatas de pila
Forma normal de Greibach
Máquinas de Turing Definiciones básicas
Máquinas de Turing como aceptadoras de lenguajes
Construcción de máquinas de Turing
Modificaciones de las máquinas de Turing
Máquina de Turing universal
Lenguajes recursivamente enumerables Lenguajes aceptados por máquinas de Turing
Lenguajes regulares e independientes del contexto como lenguajes recursivos
Propiedades de los lenguajes recursivos y recursivamente enumerables
Gramáticas no restringidas y lenguajes recursivamente enumerables
Lenguajes sensibles al contexto y la jerarquía de Chomsky
Resolubilidad El problema de la parada
El problema de correspondencia de Post
Problemas no decidibles en lenguajes independientes del contexto
Computabilidad Fundamentos de la teoría de funciones recursivas
Alcance de las funciones recursivas primitivas
Funciones recursivas parciales
El poder de los lenguajes de programación
Introducción a la teoría de la complejidad computacional Complejidad algorítmica
Modelo general de cómputo y complejidad computacional
Tiempo y espacio en máquinas de Turing
Las distintas clases de complejidad
Los problemas tratables y no tratables
Reducibilidad en tiempo polinómico
Problemas NP-completos