Siguiente:
Índice General
Índice General
Teoría de Autómatas y Lenguajes Formales
Version 2
Dr. Arno Formella
Universidad de Vigo
Departamento de Informática
Í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
© 2006, Dr. Arno Formella, Universidad de Vigo, Departamento de Informática
(AFND-)