Programa del curso

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

La enseñanza se realizará mediante clases de exposición de los temas (4 horas semanales) y clases prácticas (3 horas semanales de consulta y presentación). El estudiante deberá realizar además trabajos de laboratorio. Se estima en 12 horas semanales promedio el tiempo de dedicación del estudiante.

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) que tendrá 2 entregas. Por otra parte, en cada prueba se incluirán preguntas vinculadas a la tarea del laboratorio, que de no ser contestadas implicará un 0 en la parte correspondiente a dicha entrega. 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.