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
|
|
- 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.
- 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.
- 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
-
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 y recomendados
|
|
Para cursar esta asignatura se requiere conocer Cálculo Proposicional y de Predicados, nociones básicas de funciones, relaciones y estructuras algebraicas y tener conocimientos y experiencia en Lenguajes de Programación.
Se recomienda que para cursar esta asignatura se tengan aprobados los exámenes de Matemática Discreta I y de Lógica y 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 mismo el año próximo.
Al comienzo del curso se informará los puntajes de las pruebas individuales y el trabajo de laboratorio.
Ninguna de las instancias de evaluación tendrá una incidencia superior al 60% del total del puntaje del curso.
|
|