Siguiente: Introducción a la teoría Un nivel arriba: PRINCIPIOS DE AUTOMATAS FINITOS Anterior: PRINCIPIOS DE AUTOMATAS FINITOS

Contents

• Contents
• Introducción a la teoría de autómatas
  • Gramáticas formales
    • Una gramática sencilla del castellano
    • Otras gramáticas formales
  • Reglas de transformación
    • MAI : Modos Mecánico, Anti e Inteligente (Zen)
    • KENNINGS: Poesía antigua islandesa
    • Algoritmos de Markov
  • Una formalización de gramáticas
  • Jerarquía de Chomsky
  • Autómatas
    • Autómatas regulares
    • Autómatas de pila
    • Autómatas lineales
    • Autómatas de pila no-deterministas
    • Máquinas de Turing
    • Jerarquía de Chomsky en autómatas
• Fundamentos matemáticos
  • Cadenas y lenguajes
  • Monoide de cadenas
    • La operación de concatenación
    • Relaciones de orden
    • Homomorfismos
    • Relaciones de equivalencia congruentes
  • Propiedades de lenguajes
    • Particiones en base a un lenguaje
    • Propiedades de cerradura
  • Ejercicios
• Gramáticas formales
  • Conceptos básicos de gramáticas
  • Ejemplos de gramáticas
    • Proposiciones bien formadas
    • Tercetas de igual longitud
    • Parejas de igual longitud
    • Palabras dobles
    • Elevación al cuadrado
  • Equivalencia de gramáticas
  • Tipos de gramáticas
  • Ejercicios
  • Programas
• Autómatas finitos y expresiones regulares
  • Máquinas secuenciales
    • Máquinas de Mealy
    • Máquinas de Moore
    • Equivalencia e indistinguibilidad
  • Autómatas finitos
    • Conceptos básicos
    • Homomorfismos
    • Monoide de un semiautómata
    • Acceso en un semiautómata
    • Cocientes de autómatas
  • Autómatas no-deterministas
    • Nociones básicas
    • Monoides de autómas no-deterministas
    • Indeterminismo y determinismo
  • Gráficas de transición
    • Nociones básicas
    • Supresión de transiciones vacías
  • Autómatas bidireccionales
  • Producto de autómatas
  • Propiedades de cerradura
  • Ejercicios
• Expresiones regulares
  • Presentación conjuntista
  • Presentación formal
    • Sintaxis de las expresiones regulares
    • Interpretación estándar
    • De expresiones regulares a autómatas
  • Estructura algebraica de las expresiones regulares
    • Orden
    • Puntos fijos de ecuaciones lineales
    • Matrices de expresiones regulares
  • El teorema de Kleene
  • Expresiones regulares y sistemas de planeación
    • Introducción
    • El mundo de los bloques
    • PB visto como un AF
  • Minimización de autómatas
  • Lema de bombeo
  • Propiedades de lenguajes regulares
    • Propiedades de cerradura bajo homomorfismos
  • Ejercicios
  • Programas
• Autómatas de pila
  • Principios básicos
  • Reconocimiento de lenguajes
  • Autómatas de pila y lenguajes libres de contexto
  • Autómatas de pila deterministas
  • Autómatas de pila con escritura
• Lenguajes libres de contexto
  • Arboles de derivación
    • Gráficas y árboles
    • Arboles y gramáticas
  • Transformaciones equivalentes de gramáticas
    • Supresión de símbolos inútiles
    • Supresión de producciones vacías
    • Supresión de producciones unitarias
  • Formas normales
    • Forma normal de Chomsky
    • Forma normal de Greibach
  • Lenguajes libres de contexto y autómatas de pila
  • Series de potencias e inversión de Lagrange
    • Series en diccionarios
    • Series sobre los racionales
    • Conteo de árboles de derivación
  • Programas
• Bibliography