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
Guillermo Morales-Luna
2000-06-27