CC30B Fundamentos de la Ciencia de la Computación
10 UD

  1. Requisitos

    2. CC20A, MA26B

  2. Objetivos

    3. Conocer qué problemas puede resolver un computador a través de diversos modelos simples de computación. Estos modelos son usados en diversas áreas como la construcción de compiladores (análisis léxico y sintáctico), sistemas de entrada y salida de datos discretos, editores de texto, búsqueda de patrones, etc.

  3. Programa

    1. Introducción

      2. Conceptos básicos de alfabeto, cadena y operaciones asociadas. Lenguajes. Representación finita de lenguajes.

    2. Lenguajes regulares y autómatas finitos

      3. Expresiones regulares. Lenguajes regulares. Modelo simple de un computador. Autómata finito. Propiedades. Determinismo y no determinismo. Equivalencia entre ambos modelos. Equivalencia entre autómatas y lenguajes regulares. Lema Pumping. Igualdad entre lenguajes regulares.

    3. Lenguajes libres del contexto y autómatas de pila

      4. Gramáticas libres del contexto. Derivación de palabras. Lenguajes libres del contexto. Autómatas de pila. Propiedades. Determinismo y no determinismo. Lema Pumping. Equivalencia entre autómatas de pila y lenguajes libres del contexto.

    4. Máquinas de Turing y Computabilidad

      5. Modelo general de un computador. Gramáticas sensibles al contexto. Máquina de Turing. Variaciones del modelo. No determinismo. Problemas NP-Completos. Complejidad de problemas. Decidibilidad. Problema de la parada. Modelos alternativos. Tesis de Church.

  4. Bibliografía

    1. H. Lewis y C. Papadimitrou. Elements of the Theory of Computation. Prentice-Hall, 1981.

    2. J. Hopcroft y J. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

    3. D. Kelley, Teoría de Autómatas y Lenguajes Formales, Prentice Hall, 1995.