Teoría de Autómatas
Objetivo:
Conocer los elementos básicos de los lenguajes formales, de los dispositivos formales que los reconocen y conocer también a la Jerarquía de Chomski.
Contenido:
- Introducción a la noción de autómata.
- Fundamentos matemáticos
- Cadenas y lenguajes
- Semigrupo de cadenas
- Propiedades de lenguajes
- Gramáticas formales
- Representación de lenguajes
- Conceptos básicos de gramáticas
- Gramáticas formales
- Tipos de gramáticas
- Arboles de derivación
- Ambigüedad
- Máquinas de estados finitos
- Máquinas de transición y con estados asignados
- Conversión entre ambos tipos de máquinas
- Equivalencia de máquinas de estados finitos
- Reducción de estados
- Lenguajes de estados finitos
- Reconocedores de estados finitos
- Reconocedores determinísticos e indeterminísticos y conversión entre ellos
- Aplicaciones al diseño de máquinas
- Reconocedores de estados finitos y su relación con las gramáticas regulares
- Propiedades de los lenguajes de estados finitos
- Ambigüedad
- Limitaciones de autómatas finitos
- Limitaciones de reconocedores
- Limitaciones de generadores
- Limitaciones de traductores
- Autómatas de cinta
- Reconocedores de cinta y gramáticas formales
- Máquinas secuenciales generalizadas
- Reconocedores de dos modos
- Relación de reconocedores de estados finitos
- Autómatas de pila
- Reconocedores de pila
- Reconocedores de pila para gramáticas libres de contexto
- Construcción de analizadores de sintaxis de pila
- Propiedades de cerrado de los lenguajes libres de contexto
- Reconocedores de pila determinísticos
- Reconocedores de conteo
- Lenguajes libres de contexto
- Introducción
- Transformación de gramáticas
- Formas canónicas de gramáticas
- Estructura de los lenguajes libres de contexto
- Análisis de sintaxis
- Análisis top-down y bottom-up
- Análisis de precedencia
- Análisis gereralizado de izquierda a derecha
- Máquinas de Turing
- Conceptos fundamentales
- Simulación de otros autómatas
- Traductores de Turing
- Reconocedores de Turing
- Funciones computables y predicados
- Algoritmos y computabilidad efectiva
- Máquina universal de Turing
Bibliografía (libros clásicos)
- Aho, Hopcroft, Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
- Denning, JB Dennis, JE Qualitz: Machines, languages and computation, Prentice-Hall, 1978
- Ginzburg: Algebraic theory of automata, Academic Press, 1968
- Harrison: Introduction to formal languages theory, Addison Wesley, 1978
- Salomaa: Formal languages, Academic Press, 1973
- Salomaa: Automata theory, Pergamon Press, 1969.
Notas del Curso:
El libro "Teoría de Autómatas", de Guillermo Morales-Luna, es el texto del curso. Está disponible en varios formatos: PostScript Comprimido, DVI y HTML.
