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

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. Gramáticas regulares. Algoritmo para obtener una gramática regular a partir de un autómata finito. 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

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. Gramáticas libres del contexto. Árbol de derivación. Ambigüedad. Relación entre lenguajes libres del contexto, autómatas de pila y gramáticas libres del contexto. BNF (Backus Naur Form). BNF extendido y diagramas sintácticos. Propiedades de clausura de los lenguajes libres del contexto.

 

Unidad 4

Lenguajes sensibles al contexto y estructurados por frases

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. Gramáticas sensibles al contexto. Relación entre lenguajes sensibles al contexto, autómata linealmente acotado y 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.

 

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.



Bibliografía

Título/Artículo

Autor/es

Editorial/Publicación

Año de edición

Teoría de la Computación. Lenguajes Formales, Autómatas y Complejidad

Brookshear, J. Glenn.

 

Addison-Wesley Iberoamericana

1993

Introducción a las Ciencias de la  Computación

Brookshear, J. Glenn.

 

Addison-Wesley Iberoamericana

1995

Teoría de autómatas y lenguajes formales

Kelley, Dean

Prentice Hall

1995

Elements of Theory of Computation

Lewis, Harry; Papadimitriou, Christos

Prentice Hall

1998

Lenguajes Formales y Teoría de la Computación

Martin, John

Mc Graw Hill

2004

Introducción a la Teoría de Autómatas, Lenguajes y Computación

Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey

Pearson Educación - Addison-Wesley

2008

Introduction to Automata Theory, Languages, and Computation

Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey

Pearson Education

2014