MATERIA: Teoría de la Computación

CLAVE: COMP-521

SEMESTRE DE UBICACION: Quinto

AREA: Ciencias de la Computación

OBJETIVOS: Este curso introduce la teoría de la computabilidad, incluyendo resultados importantes del estudio de autómatas y lenguajes formales. El curso empieza con una discusión de autómatas y su - relación con lenguajes regulares, libres del contexto y dependientes del contexto. Se presentan teorías generales de la computabilidad, incluyendo las máquinas de Turing, funciones recursivas y cálculos lambda. Se discuten nociones de decidibilidad e indecidibilidad y se relaciona esto con análisis de complejidad. Finalmente se presentan y analizan enfoques a semántica de programas, llevando esto a una breve introducción al tema de verificación de formal programas

TEMARIO:

  1. Introducción

    • Procesadores de lenguajes

    • Cadenas, alfabetos y lenguajes

    • Modelos matemáticos de traducción

  2. Máquinas con un número finito de estados

    • Definición

    • Aplicaciones e instrumentación. Diseño de autómatas finitos

    • Equivalencia de autómatas finitos

    • Minimización de autómatas finitos

  3. Gramáticas formales y lenguajes formales

    • Introducción

    • Conceptos básicos de gramáticas

    • Gramáticas formales

    • Clasificación de gramáticas: no restringidas, sensitivas al contexto, libres del contexto y regulares

    • Árboles de derivación. Ambigüedad

  4. Autómatas de estados finitos y lenguajes tipo 3

    • Introducción

    • Propiedades de los lenguajes regulares

    • Expresiones regulares. Equivalencia entre autómatas finitos y expresiones regulares. Construcción de autómatas finitos a partir de expresiones regulares

    • Algoritmos de decisión para lenguajes regulares: ambigüedad, vacuidad, finitud e infinitud; equivalencia

  5. Autómatas con stack o pila

    • Definición

    • Formalización

    • Traducción con autómatas de stack

    • Ciclos en los autómatas de stack determinísticos

  6. Lenguajes libres del contexto

    • Presentación

    • Simplificación de gramáticas libres del contexto. Producciones vacías o producciones-e

    • Formas normales: Chomski y Greibach

    • Equivalencia entre autómatas de stack y lenguajes libres del contexto

  7. Propiedades de los lenguajes libres del contexto

    • Caracterización del complemento de los lenguajes libres del contexto: Lemas del bombeo y de Ogden

  8. Máquinas de Turing

    • Motivación, definiciones y notación

    • Técnicas para la construcción de las máquinas de Turing

    • La máquina de Turing como un procedimiento

  9. Semántica de los lenguajes de programación

    • Semántica informal

    • Semántica formal (axiomática, de notacional, operativa)

BIBLIOGRAFIA:

  • Linz, P., An Introduction To Format Languages and Automata, D.C. Heath and Company,1990

  • Ullman, J.D.; Hopkroft, J.E., Introduction to Automata Theory, Languages and Computations, Addison-Wesley Publishing Company, 1979

BIBLIOGRAFIA COMPLEMENTARIA:

  • Gough, K.J., Syntax Analysis and Software Tools, Addison-Wesley Publishing Company, 1988

  • Gries, David, editor, Programming in the 1990’s, An introduction to the Calculation of Programs, Springer Verlag, 1990

  • Dijkstra, E.W., editor., Formal Development of Programs and Proofs, Addison-Wesley Publishing Company, 1990

  • Manna, Z.; Waldinger, R., The Logical Bases for Computing Programming, Addison-Wesley Publishing Company, 1993

  • Kfoury, A.J.; Moll, R. N.; Arbib, M.A., A Programing Approach to Computability, Springer-Verlag, 1982