Teoría de Autómatas

1. Fundamentos de Lenguajes Formales

  • 1.1. Conceptos Básicos
  • 1.1.1. Alfabetos y símbolos
  • 1.1.2. Cadenas y palabras
  • 1.1.3. Lenguajes y conjuntos
  • 1.2. Operaciones con Lenguajes
  • 1.2.1. Unión, intersección y diferencia
  • 1.2.2. Concatenación
  • 1.2.3. Cierre de Kleene y cierre positivo
  • 1.3. Expresiones Regulares
  • 1.4. Propiedades de los Lenguajes Formales

2. Fundamentos Matemáticos

  • 2.1. Teoría de Conjuntos
  • 2.2. Relaciones y Funciones
  • 2.3. Técnicas de Demostración
  • 2.3.1. Demostración directa
  • 2.3.2. Demostración por contradicción
  • 2.3.3. Inducción matemática

3. Gramáticas y Lenguajes

  • 3.1. Jerarquía de Chomsky
  • 3.2. Gramática Regular
  • 3.2.1. Gramáticas lineales por la derecha
  • 3.2.2. Gramáticas lineales por la izquierda
  • 3.2.3. Equivalencia con autómatas finitos
  • 3.3. Gramática Independiente del Contexto
  • 3.3.1. Definición formal
  • 3.3.2. Derivaciones y árboles sintácticos
  • 3.3.3. Formas normales
    • 3.3.3.1. Forma normal de Chomsky
    • 3.3.3.2. Forma normal de Greibach
  • 3.4. Lema de Bombeo para Lenguajes Libres de Contexto

4. Autómatas de Pila

  • 4.1. Autómata de Pila Determinista (APD)
  • 4.1.1. Definición formal
  • 4.1.2. Configuraciones y computaciones
  • 4.1.3. Lenguajes aceptados por APDs
  • 4.2. Autómata de Pila No Determinista (APND)
  • 4.2.1. Definición formal
  • 4.2.2. Relación con gramáticas libres de contexto
  • 4.3. Diferencias entre APD y APND

5. Análisis Sintáctico

  • 5.1. Análisis Descendente
  • 5.1.1. Gramáticas LL(k)
    • 5.1.1.1. Conjuntos First y Follow
    • 5.1.1.2. Construcción de tabla de análisis
    • 5.1.1.3. Eliminación de recursividad izquierda
  • 5.1.2. Análisis LL(1)
    • 5.1.2.1. Condiciones LL(1)
    • 5.1.2.2. Implementación de analizador LL(1)
  • 5.2. Análisis Ascendente
  • 5.2.1. Gramáticas LR(k)
  • 5.2.2. Técnicas de análisis LR
    • 5.2.2.1. LR(0)
    • 5.2.2.2. SLR
    • 5.2.2.3. LALR
    • 5.2.2.4. LR(1) canónico

6. Máquinas de Turing

  • 6.1. Definición Formal
  • 6.2. Variantes de Máquinas de Turing
  • 6.2.1. Máquinas de Turing multicinta
  • 6.2.2. Máquinas de Turing no deterministas
  • 6.3. Decidibilidad
  • 6.3.1. Problemas decidibles
  • 6.3.2. Problemas indecidibles
  • 6.4. Tesis de Church-Turing

7. Complejidad Computacional

  • 7.1. Clases de Complejidad
  • 7.1.1. Clase P
  • 7.1.2. Clase NP
  • 7.1.3. NP-Completo
  • 7.2. Reducciones
  • 7.3. Problemas NP-Completos Clásicos