Temario: TEORÍA COMPUTACIONAL

UNIDAD I   Conceptos fundamentales
1.1 Alfabetos
1.2 Cadenas
1.2.1 Definición
1.2.2 Prefijo
1.2.3 Sufijo
1.2.4 Subcadena
1.3 Lenguajes
1.3.1 Definición de lenguaje
1.3.2 Unión de lenguaje
1.3.3 Concatenación de lenguajes
1.3.4 Cerradura de Kleene de un lenguaje

UNIDAD II   Lenguajes regulares
2.1 Expresiones regulares
2.2 Autómatas finitos
2.2.1 Autómata finito determinista
2.2.2 Autómata finito no determinista
2.2.3 Equivalencia entre AFN Y AFD
2.2.4 Transiciones épsilon
2.3 Propiedades de los lenguajes regulares
2.3.1 Lema de sondeo
2.3.2 Teorema de Myhill-Nerode

UNIDAD III   Gramáticas libres de contexto
3.1 Gramáticas libres de contexto
3.1.1 Definición
3.1.2 Forma de Backus-Naur
3.1.3 Ejemplos
3.1.4 Derivaciones
3.1.5 Árboles de sintaxis
3.1.6 Ambigüedad
3.2 Métodos de transformación de gramáticas
3.2.1 Producciones inútiles
3.2.2 Producciones vacías
3.3 Formas normales
3.3.1 Forma normal de Chomsky
3.3.2 Forma normal de Greibach
3.4 Lenguajes inherentemente ambiguos
3.5 Autómatas de pila
3.5.1 Descripción informal
3.5.2 Definiciones
3.5.3 Lema de sondeo para lenguajes libres de contexto
3.5.4 Implementación de autómatas de pila

Unidad IV   Máquinas de Turing
4.1 Modelo de máquina de Turing
4.2 Variantes de la máquina de Turing
4.3 Tesis de Church-Turing
4.4 Máquinas de Turing universales