Materia

Para la carrera Ingeniería en Computación, Programación

Créditos

12

Objetivos de la asignatura

Dar una introducción básica a los fundamentos teóricos de los lenguajes formales. Presentar distintas aplicaciones de los modelos de lenguajes analizados.

Metodología de enseñanza

Clases de exposición de los temas (4 horas semanales) donde el estudiante aprende los fundamentos y formalismos teóricos de los lenguajes de programación y se complementan con clases prácticas (3 horas semanales divididas en 1:30 de presentación de los ejercicios de prácticos por parte de los docentes y 1:30 de consulta).

La evaluación está formada por 2 parciales – individuales – y una tarea de laboratorio – en grupo – y con carácter obligatoria su entrega.

Se estima en 180 horas el tiempo total de dedicación del estudiante entre todas las actividades. Entre estas actividades se incluye el Laboratorio, que se realizará en base a los temas tratados durante el curso, para el cual se estima una dedicación de 8 de las 180 horas totales.


Temario

  1. Lenguajes Regulares: Expresiones regulares. Autómatas Finitos Deterministas, No Deterministas, transiciones epsilon. Equivalencia de modelos. Autómata mínimo. Propiedades. El Pumping Lemma y sus consecuencias. Autómatas finitos con salida. Aplicaciones.

  2. Lenguajes Independientes del Contexto. Gramáticas independientes del contexto y gramáticas regulares. Simplificación. Autómatas de pila, equivalencias. Formas normales. Propiedades. El Pumping Lemma y el Lema de Ogden. Análisis sintáctico.

  3. Lenguajes recursivamente enumerables. Gramáticas irrestrictas. Máquinas de Turing. Jerarquía de Chomsky.


Bibliografía
Básica
  • Introduction to Automata Theory, Languages and Computation. Hopcroft, Motwani, Ullman. ISBN 0-201-44124-1, Addison-Wesley 2001
    https://www.fing.edu.uy/owncloud/index.php/s/1N7XHl3BdrerMwl

Complementaria
  • Elements of the Theory of Computation. Lewis H., Papadimitriou C. ISBN 0-13-27-3417-6 Prentice-Hall 1981
  • Compilers. Principles, Techniques and Tools. Aho A., Sethi R., Ullman J. ISBN 0-201-10088-6 Addison-Wesley 1986
Conocimientos previos exigidos

Para cursar esta asignatura se requiere los exámenes de Cálculo Diferencial e Integral en una Variable (o Cálculo I); Geometría y Álgebra Lineal I;  Lógica y Matemática Discreta I. Además, el curso de Programación III. 

Modalidad de evaluación

La asignatura se evaluará por medio de dos pruebas individuales y un trabajo de laboratorio (en grupo de 2 a 4 personas) de carácter obligatorio.

De los resultados obtenidos por la suma de las pruebas y el laboratorio, surgirán tres posibilidades:

  • Exoneración del examen final.
  • Suficiencia en el curso: el estudiante queda habilitado a rendir el examen.
  • Insuficiencia en el curso: el estudiante reprueba el curso y debe reinscribirse en el año próximo.

Ninguna de las instancias de evaluación tendrá una incidencia superior al 60% del total del puntaje del curso.


Última modificación: viernes, 21 de febrero de 2025, 10:34