CURSO : Teoria de Automatas y Lenguajes Formales
SIGLA : IIC2222
CRÉDITOS : 10
REQUISITOS : IIC2252 Matematica Discreta
SEMESTRE : II
1. OBJETIVOS
Proveer al alumno con nociones de los fundamentos de la ciencia de la computacion; en
particular, en lo que respecta a la teoria de la computabilidad. El alumno desarrollara la
capacidad de entender los problemas computacionales, y lograr una comprension acabada
de ciertos topicos de la ciencia de la computacion. Conocera los modelos basicos de
computabilidad y complejidad de problemas. El curso incluye temas que son centrales al
desarrollo teorico del area, y tambien aquellos que tienen importancia para aplicaciones de
ingenieria.
2. CONTENIDO
- Fundamentos matematicos: Alfabetos, palabras y lenguajes. Grafos y arboles.
Induccion matematica. Conjuntos y relaciones.
- Automatas finitos: Automatas finitos deterministicos. Automatas finitos no
deterministicos. Automatas finitos con transiciones en vacio. Expresiones regulares.
Automatas que escriben.
- Propiedades de los conjuntos regulares: Lema de bombeo para conjuntos regulares.
Propiedades de clausura. Algoritmos de decision. Teorema de Myhill-Nerode.
Minimizacion de automatas finitos.
- Gramaticas libres de contexto: Definiciones. Arboles de derivacion. Simplificacion de
gramaticas. Formas normales. Lenguajes inherentemente ambiguos.
- Automatas apiladores: Definiciones. Relacion con los lenguajes libres de contexto.
- Propiedades de los lenguajes libres de contexto: Lema de bombeo para lenguajes libres
de contexto. Propiedades de clausura. Algoritmos de decision.
- Maquinas de Turing: Modelo de la maquina de Turing. Lenguajes y funciones
computables. Tecnicas para la construccion de maquinas de Turing. Extensiones al
modelo de las maquinas de Turing. Hipotesis de Church.
- Problemas indecidibles: Problemas. Propiedades de los lenguajes recursivos y
enumerables recursivamente. La maquina de Turing universal.
3. BIBLIOGRAFIA
Complementaria:
CAMPOS, Alvaro. Teoria de automatas y lenguales formales. Santiago, Chile,
Pontificia Universidad Catolica de Chile. Depto. de Ciencia de la Computacion,
1995. Apuntes de clases.
DAVIS, Martin D. and WEYUKER, Elaine J. Computability, complexity and
languages: fundamentals of theoretical computer science. 2nd ed. Boston,
Academic Press, 1994.
HOPCROFT, John. Introduction to automata theory, languages and computation,
Reading, Mass. Addison Wesley, 1979.
LEWIS, Harry and PAPADIMITRIOU, Cristhos H. Elements of the theory of
computation. Englewood Cliffts, N.J., Prentice Hall, 1981.
MARTIN John C. Introduction to languages and the theory of computation. 2nd. ed.
New York, McGraw Hill, 1997.
SIPSER, Michael. Introduction to the theory of computation. Boston, MA, PWS,
1996.
