Teoría de Lenguajes
 
      Principal  |   Temario  |   Horarios  |   Prácticos  |   Obligatorio  |   Evaluaciones  |   Plan 87  |   Sitios Relacionados

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
 
  1. Básica
    • Introduction to Automata Theory, Languages and Computation. Hopcroft, Motwani, Ullman. ISBN 0-201-44124-1, Addison-Wesley 2001
  2. 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 :
  1. Exoneración del examen final.
  2. Suficiencia en el curso: el estudiante queda habilitado a rendir el examen.
  3. 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.
 
  Grupo de Procesamiento de Lenguaje Natural   |  Instituto de Computación   |  Fac. de Ingeniería   |  Universidad de la República