Patiperros del DCC

Requisitos

CC20A, MA26B

Objetivos

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.

Programa

Cadenas y lenguajes

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

Lenguajes regulares y autómatas finitos

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.

Lenguajes libres del contexto y autómatas de pila

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.

Máquinas de Turing y Computabilidad

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

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.