Teoría de Lenguajes y Automatas
Objetivos
Conocer la notación de los lenguajes formales y regulares.
Análizar y diseñar expresiones regulares y autómatas para su uso real.
Implementar los conceptos de la teoría del lenguaje en un lenguaje de computador.
Conocer herramientas en entornos y problemas reales para buscar o analizar textos.
Metodología
Se realizarán clases magistrales para la explicación de los conceptos fundamentales de la teoria de lenguajes formales y regulares, expresiones regulares y automatas.
Se harán ejercicios en clase explicando los conceptos y el fundamento teorico de los temas del curso que están en el programa.
Se evaluará el progreso continuo del estudiante por medio de quices y tareas, desarrollo de talleres y dos evaluaciones parciales del contenido del curso.
Se realizará un seminario de "cacharreo" para aplicar herramientas de software en autómatas y expresiones regulares (YACC, LEX y Python).
Se implementará lo visto en el curso por medio de un proyecto final relacionado al contenido para poner en practica los conceptos.
Contenido
Evolución histórica de la Teoría de la Computación
Fundamentos Matemáticos
Capítulo 1. LENGUAJES Y GRAMATICAS FORMALES
Alfabetos y palabras
Lenguajes formales
Gramáticas formales
Nociones básicas sobre traductores
Capítulo 2. EXPRESIONES REGULARES
Definición de expresión regular
Lenguaje descrito por una expresión regular
Propiedades de las expresiones regulares
Derivada de una expresión regular
Ecuaciones de expresiones regulares
Expresiones regulares y gramáticas regulares
Capítulo 3. AUTOMATAS FINITOS
Arquitectura de un autómata finito (AF )
Autómatas finitos deterministas
Autómatas finitos no deterministas
Autómatas finitos con λ-transiciones
Lenguaje aceptado por un AF
Equivalencia entre autómatas finitos
Autómatas finitos, expresiones regulares y gramáticas regulares
Minimización de un AFD
Aplicaciones: análisis léxico
Capítulo 4. GRAMATICAS LIBRES DEL CONTEXTO
Definiciones básicas
Transformaciones en gram´ticas libres del contexto
Formas Normales
Capítulo 5. INTRODUCCION AL ANALISIS SINTACTICO
Objetivo del analizador sintáctico
Problema de la ambigüedad en el análisis sintáctico
Análisis sintáctico ascendente y descendente
Método de análisis CYK
Análisis sintáctico determinista
Programación
Exposiciones
Analizador ADN [ppt]
Analizador Léxico [pdf]
Analizador Sintáctico [pptx]
Autómata en un laberinto [pps]
Bibliografía
Hopcroft, John E. y Jeffrey D. Ullman, Introducción a la teoría de autómatas, lenguajes y computación, CECSA, México, 1996.
J. G. Brookshear, Teoría de la Computación: Lenguajes Formales, Autómatas y Complejidad, Addison-Wesley Iberoamericana, 1993.
D. Kelley. Teoría de Autómatas y Lenguajes Formales. Prentice-Hall, 1995.
P. Isasi, P. Martínez y D. Borrajo. Lenguajes, Gramáticas y Autómatas. Un Enfoque Práctico. Addison-Wesley, Madrid, 1997.
M. Alfonseca, J. Sancho y M. Martínez. Teoría de Lenguajes, Gramáticas y Autómatas. Ediciones Universidad y Cultura, Madrid, 1990.
Recursos
Curso teoria de la computación. Rodrigo Di Castro. UNVirtual. http://www.virtual.unal.edu.co/cursos/ciencias/2001018/index.html [material]
[Murcia] TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES. Departamento de Ingeniería de la Información y las Comunicaciones. Universidad de Murcia. [pdf]
Lecturas