Teoría de lenguajes, gramáticas y autómatas para informáticos

Teoría de lenguajes, gramáticas y autómatas para informáticos

La ingeniería informática es uno de los ámbitos en los que mayor importancia y repercusión tiene la teoría matemática de los lenguajes, tanto en el desarrollo de lenguajes de programación como en numerosas tareas de inteligencia artificial: traducción entre idiomas, reconocimiento de objetos, aprendizaje computacional, etc. Por ello, y a diferencia de la mayoría de textos publicados sobre la materia, hemos considerado conveniente presentar los elementos básicos de la teoría de lenguajes a partir de situaciones habituales para las personas que se inician en la informática, intentando que situaciones que se presentan frecuentemente en la tarea de programación motiven la introducción de los conceptos, y que la formalización de éstos se produzca sólo a posteriori.

  • Cover
  • Title page
  • Copyright page
  • Índice General
  • Presentación
    • Estructura del libro
  • 1. Lenguajes y computadores
    • 1.1 Distintos tipos de programas
    • 1.2 Problemas y lenguajes
  • 2. Autómatas finitos
    • 2.1 Alfabetos y lenguajes
    • 2.2 Representaciones de un AFD
    • 2.3 Autómata finito determinista como clasificador
    • 2.4 El autómata finito determinista como traductor
    • 2.5 Deterministas, indeterministas y estocásticos
      • 2.5.1 Autómatas finitos indeterministas
      • 2.5.2 Equivalencia AFI-AFD
      • 2.5.3 Autómatas finitos estocásticos
  • 3. Lenguajes regulares
    • 3.1 Expresiones regulares
      • 3.1.1 Algunas propiedades de las ER
    • 3.2 Equivalencia ER-AF
    • 3.3 Operaciones con conjuntos regulares
  • 4. Construcción de autómatas finitos
    • 4.1 Lema de bombeo
    • 4.2 Algoritmos y decidibilidad
    • 4.3 Minimización de autómatas finitos
      • 4.3.1 Teorema de Myhill y Nerode
      • 4.3.2 Algoritmos de minimización
  • 5. Gramáticas
    • 5.1 Introducción
    • 5.2 Definición y clasificación de las gramáticas
    • 5.3 Gramáticas regulares
      • 5.3.1 Gramática regular asociada a un autómata
      • 5.3.2 Autómata asociado a una gramática regular
    • 5.4 Gramáticas independientes del contexto (GIC)
      • 5.4.1 Derivación y árbol de derivación
      • 5.4.2 Ambigüedad
      • 5.4.3 Recursividad
      • 5.4.4 El análisis sintáctico
      • 5.4.5 Simplificación de una GIC
      • 5.4.6 Formas normalizadas
  • 6. Lenguajes independientes del contexto
    • 6.1 Operaciones con LIC
    • 6.2 Lema de bombeo para LIC
    • 6.3 Algoritmos
  • 7. Autómatas con pila y analizadores sintácticos
    • 7.1 Definiciones
    • 7.2 Autómata de pila para una GIC
    • 7.3 Gramática correspondiente a un AP
    • 7.4 Analizadores sintácticos
  • A. Nociones básicas de teoría de conjuntos
    • A.1 Correspondencias y relaciones
    • A.2 Cardinal. Conjuntos infinitos
      • A.2.1 Demostración del teorema de Cantor
      • A.2.2 Aplicación a la informática
  • Bibliografía

SUBSCRIBE TO OUR NEWSLETTER

By subscribing, you accept our Privacy Policy