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

Hoja de datos de Google

Evaluación

    • Parciales 40%

      • Parcial I 20%

      • Parcial II 20%

    • Talleres 20%

      • Taller I 5%

      • Taller II 5%

      • Taller III 5%

      • Taller IV 5%

    • Quices 10%

    • Proyecto final 30%

      • Propuesta 5%

      • Proyecto 15% (5% de avance, 10% Articulo científico con el proyecto final)

      • Sustentación 10%

Notas

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

Lecturas

    • Penrose, Roger, La Nueva Mente del Emperador, Mondadori, 1991, ISBN 84-397-1786-5. [pdf] [amazon]