Programa de la materia

Unidad 1 

Introducción a los lenguajes formales

Alfabetos, cadenas y lenguajes formales: definiciones básicas. Operaciones con cadenas. Operaciones con lenguajes. Propiedades de lenguajes.

 

Unidad 2 

Autómatas finitos y lenguajes regulares

Autómata finito: definiciones básicas; ejemplos. Autómata finito determinístico: reconocimiento y traducción. Autómata finito no determinístico. Equivalencia entre autómata finito determinístico y no determinístico. Minimización de autómatas finitos. Aplicaciones de autómatas finitos. Lenguajes regulares. Gramáticas regulares. Relación entre gramáticas regulares y autómatas finitos. Expresiones regulares: definiciones y aplicaciones prácticas.  Leyes algebraicas de expresiones regulares. Relación entre lenguajes regulares, autómatas finitos, gramáticas regulares y expresiones regulares. Propiedades de clausura de los lenguajes regulares.  

 

 Unidad 3

Autómatas de pila y lenguajes libres del contexto

Autómata de pila: definiciones básicas; ejemplos. Autómata de pila determinístico: reconocimiento y traducción. Autómata de pila no determinístico. Lenguajes libres del contexto. Propiedades de los lenguajes libres del contexto. Gramáticas libres del contexto. Árbol de derivación. Ambigüedad. BNF (Backus Naur Form). BNF extendido y diagramas sintácticos.

 

Unidad 4

Máquinas de Turing

Máquina de Turing: definiciones básicas; ejemplos. Máquina de Turing determinística: reconocimiento, traducción y cálculo de funciones. Máquina de Turing multicinta. Máquina de Turing no determinística. Autómata linealmente acotado. Autómata linealmente acotado y lenguajes sensibles al contexto. Gramáticas sensibles al contexto. Máquina de Turing y lenguajes estructurados por frases.

 

Unidad 5

Jerarquía de Chomsky

Jerarquía de Chomsky: autómatas, gramáticas y lenguajes. Relación entre clases de lenguajes. Ejemplos.

 

Unidad 6

Nociones básicas de computabilidad

Relación entre problemas y lenguajes. Procedimiento y algoritmo. Lenguajes recursivos y recursivo enumerables, problemas de decisión: definiciones básicas y ejemplos. El problema del Halting. 


BIBLIOGRAFIA
  • Brookshear, J. Glenn. “Teoría de la Computación. Lenguajes Formales, Autómatas y Complejidad”. Addison-Wesley Iberoamericana. 1993.
  • Brookshear, J. Glenn. “Introducción a las Ciencias de la Computación”. Addison-Wesley Iberoamericana. 1995.
  • Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey. "Introducción a la Teoría de Autómatas, Lenguajes y Computación". Editorial Pearson Educación, Segunda edición 2008.
  •  Kelley, D. “Teoría de autómatas y lenguajes formales”. Prentice Hall. 1995.
  •  Lewis, H.; Papadimitriou, C.  “Elements of Theory of Computation”. Second Edition. Prentice Hall. 1998.
  •  Martin, John. “Lenguajes Formales y Teoría de la Computación”. 3ra. Edición. Mc Graw Hill. 2003.
  •  Mauco, María Virginia; Barbuzza, Rosana. “Teoría de Autómatas y Lenguajes Formales” Apuntes para Ciencias de la Computación I. Facultad de Ciencias Exactas, Universidad Nacional del Centro de la Pcia. de Buenos Aires. Disponible en http://ciencias-de-la-computacion-i.alumnos.exa.unicen.edu.ar/