Índice General

• Curso
• Sobre este documento
  • Versiones y lista de correcciones
  
  
• Introducción
• Conceptos básicos
  • Alfabetos
  • Palabras
  • Lenguajes
  • Producciones y Derivaciones
  • Relaciones de equivalencia
  • Relación de equivalencia de lenguajes
  
  
• Gramáticas generativas
  • Ejemplos
  • Abreviación de Backus
  • Árbol de derivación
  • Jerarquia de Chomsky
  • Equivalencia y ambigüedad
  
  
• Autómatas finitos
  • Autómatas finitos deterministas (AFD)
  • Autómatas finitos no-deterministas (AFND)
  • Equivalencia entre AFD y AFND
  • Autómatas finitos no-deterministas con transiciones (AFND-)
  • Equivalencia entre AFND y AFND-
  • Existencia de autómatas finitos mínimos
  • Ejemplos de uso del teorema de Myhill y Nerode
  • Algoritmo de minimización
  
  
• Expresiones regulares
  • Síntaxis y semántica
  • Equivalencia entre autómatas finitos y expresiones regulares
  • Abreviaciones para el uso de expresiones regulares
  • Símbolos y meta-símbolos
  
  
• Lenguajes regulares
  • Equivalencia entre gramáticas lineales por la derecha y autómatas finitos
  • Equivalencia entre gramáticas lineales por la derecha y lineales por la izquierda
  • Lema de bombeo
  
  
• Propiedades, algoritmos de decisión, y aplicaciones para lenguajes regulares
  • Propiedades de lenguajes regulares
  • Algoritmos de decisión de lenguages regulares
  • Aplicaciones para lenguajes regulares
  
  
• Lenguajes libres de contexto
  • Forma Normal de Chomsky
  • Forma Normal de Greibach
  • Lema de bombeo para lenguajes libres de contexto
  
  
• Autómatas finitos con pila (AFP)
  • Motivación
  • Autómatas finitos con pila no-deterministas (AFPND)
  • Equivalencia entre AFPNDs aceptando con pila vacía y aceptando en estado final
  • Equivalencia entre AFPNDs y gramáticas libres de contexto
  • Autómatas finitos con pila deterministas (AFPD)
  
  
• Propiedades, algoritmos de decisión, y aplicaciones para lenguajes libres de contexto
  • Propiedades de lenguajes libre de contexto
  • Algoritmos de decisión de lenguages libres de contexto
  • Aplicaciones para lenguajes libres de contexto
  
  
• Máquinas de Turing (MT)
• Resumen
• Bibliografía
  • Bibliografía básica
  • Bibliografía usada para la preparación