Materia	Carrera	Plan	Año	Periodo
AUTOMATAS Y LENGUAJES	LIC.EN CS.DE LA COMPUTACION		2008	1° cuatrimestre

Docente	Función	Cargo	Dedicación
ROGGERO, PATRICIA BEATRIZ	Prof. Responsable	P.Adj Exc	40 Hs
FUNEZ, DARIO GUSTAVO	Auxiliar de Práctico	A.1ra Exc	40 Hs

El presente curso está destinado a alumnos avanzados de la Lic. en Ciencias de la Computación. Se estudian conceptos formales relacionados con la teoría de lenguajes y los lenguajes de programación, los cuales incluyen autómatas y gramáticas. Además de la aplicación de estos conceptos a los aspectos básicos del diseño de compiladores, el análisis lexicográfico y el análisis sintáctico.
El alumno debe aprender y comprender la forma en que funciona cada autómata, y la correspondencia entre autómata, gramática y lenguajes.
Por otro lado el curso es fundamental para el estudio de computabilidad y complejidad de problemas.

El objetivo fundamental de este curso es introducir al alumno en los aspectos teóricos de las Ciencias de la Computación que incluyen:
Mostrar los aspectos básicos de la teoría de lenguajes formales, autómatas y gramáticas. Estudio de análisis lexicográfico y el uso de herramientas de generación automática de los mismos. También se procura introducir al alumno en el estudio de conceptos de análisis sintáctico, junto con las respectivas técnicas de análisis (Top-Down y Bottom-Up). En cuanto a las técnicas de análisis sintáctico se profundizará en las técnicas Bottom-Up a través del estudio de gramáticas LR.

Bolilla 1.
Repaso General:
Conjuntos, funciones, relaciones y métodos de prueba. Alfabeto. Sentencia. Lenguaje. Representación de los lenguajes. Dispositivos generadores y reconocedores. Gramáticas. Autómatas determinísticos y no determinísticos. Relación general entre autómata y gramática. Jerarquía de Chomsky.

Bolilla 2.
Lenguajes Regulares (Tipo 3). Autómata Finito Determinístico y No-Determinístico (Repaso). Equivalencia de aceptación de un AFD y un AFND. AFND con transiciones épsilon. Equivalencia de aceptación de un AFND y un AFND-épsilon. Expresiones regulares y Gramáticas regulares (Tipo 3)(Repaso). Equivalencia entre: lenguajes regulares, lenguajes aceptados por autómatas finitos determinísticos y no-determinísticos y gramáticas regulares. Autómata finito con acciones semánticas. Analizador lexicográfico o Scanner. LEX: Un generador automático de Analizadores Lexicográficos. Redes de Petri, marcado y transición. Redes de Petri como reconocedoras de lenguajes

Bolilla 3.
Propiedades de los lenguajes regulares: Propiedades de clausura, Lema de Pumping y su aplicación, Minimización de autómata finito determinístico.

Bolilla 4.
Gramáticas y lenguajes libres del contexto (Tipo 2). Motivación e introducción. Árbol de derivación. Frontera. Forma sentencial izquierda y derecha. Ambigüedad. Autómatas a Pila (Push Down). Autómata Push-Down determinístico. Lenguaje aceptado por Pila Vacía y Estado Final. Equivalencia de aceptación por Pila Vacía y Estado Final.

Bolilla 5.
Propiedades de los lenguajes libres del contexto: Formas Normales: Transformaciones sobre gramáticas. Lema de Pumping para gramáticas libres del contexto y su aplicación. Propiedades de clausura de los lenguajes libres del contexto.

Bolilla 6.
Análisis sintáctico. Técnica de Análisis Top-Down y Bottom-up. Implementación de Analizadores Sintácticos utilizando Autómatas Push-Down. Parsing Bottom-up determinístico. Parser LR. Planteo general del problema. Algoritmos de Parsing LR. Parsing SLR: items LR(0), operaciones de clausura y goto, construcción del conjunto de items, tabla de parsing SLR. Parsing LR canónico. Parsing LALR.

Bolilla 7.
Introducción a las Máquinas de Turing y a las Gramáticas Irresterictas. Lenguajes Sensibles del Contexto o Tipo 1. Autómata Linealmente Acotado. Gramáticas Sensibles del Contexto.

Prácticos de Aula

Práctico 1: Repaso (Funciones, relaciones, métodos de prueba, lenguajes, etc.)

Práctico 2: Autómatas Finitos - Lenguajes Regulares - Gramáticas Regulares.

Práctico 3: Propiedades de los Lenguajes Regulares.

Práctico 4: Gramáticas Libres del Contexto - Autómatas Push-Down.

Práctico 5: Propiedades de los Lenguajes Libres de Contexto.

Práctico 6: Análisis Sintáctico - Gramáticas LR.

Práctico 7: Autómata linealmente acotado - Gramáticas Sensibles del Contexto.


Práctico de Máquina
Diseño e implementación de un Analizador Lexicográfico para una gramática reducida del lenguaje JAVA. Junto con el programa se debe entregar un informe sobre el mismo.

El alumno podrá optar por cursar la materia bajo régimen
promocional o regular:

A. Régimen para Alumnos Promocionales

1. Presentación y aprobación del práctico de máquina propuesto (fuente) incluyendo un reporte del trabajo realizado.

2. Aprobar 1 examen parcial teórico/práctico o su respectiva recuperación, o, para quienes corresponda, la recuperación por trabajo,

3. Aprobar, con un mínimo de 80%, un examen integrador oral y/o escrito al final del cuatrimestre.

La nota final se computará promediando las notas obtenidas en
cada uno de los puntos mencionados previamente.

Setenta por ciento (70%) es el porcentaje mínimo, de los ejercicios ha resolver, necesario para aprobar el parcial.

Si todos los puntos anteriores hubieran sido cumplimentados, excepto el punto (3), el alumno quedará automáticamente en condición de alumno regular, debiendo rendir el examen final.

Si cualquier otro punto no fue cumplimentado implicará que el
alumno pase a condición de libre.


B. Régimen para Alumnos Regulares

Idem al punto A. excepto que no deberá rendir el examen integrador (punto 3.).

Setenta por ciento (70%) es el porcentaje mínimo, de los ejercicios a resolver, necesario para aprobar el parcial.

En ambos casos, régimen promocional o regular, al menos el 50% de cada uno de los ejercicios involucrados en el parcial deberán ser completados para considerar su aprobación.


C. Régimen para Alumnos Libres

Para rendir en condición de libre, el alumno deberá contactarse con la cátedra como mínimo 10 días antes de la fecha de examen, además deberá cumplimentar los siguientes requisitos:

1. Presentar el práctico de máquina (fuente), el cual debe ser aprobado.
Sobre éste, la cátedra puede tomar un coloquio si lo cree conveniente.

2. Realizar un examen escrito de la parte práctica, el cual es eliminatorio.

3. Habiendo aprobado el examen anterior, pasará a un examen oral o escrito, el cual tendrá las mismas características de un examen final para alumnos regulares.

[1] Hopcroft J. - Ullman J. - Motwani R. Introduction to automata theory, languages and computation. Addison Wesley (2001).
[2] Hopcroft J. - Ullman J. Introduction to automata theory, languages and computation. Addison Wesley (1979).
[3] Aho A. - Ullman J. The theory of parsing, translation and compiling. Vol. I. Prentice Hall.
[4] Hopcroft J. - Ullman J. Formal languages and their relation to automata. Addison Wesley.
[5] Peterson, James. Petri Net Theory and The Modeling of Systems. Prentice-Hall Inc. (1981).
[6] Sipser Michael, Introduction to the Theory of Computation. PWS Publishing Company (1997).
[7] Sudkamp, Thomas A. Languages and Machines (An Introduction to the Theory of Computer Science). Addison Wesley (1997).
[8] Wood, Derick. Theory of computation. John Wiley & Sons, Inc.

[1] Denning P.- Dennis J.- Qualitz J. Machine, languages and computation. Prentice-Hall (1978).
[2] Davis - Weyuker. Computability, Complexity, and Languages. Academic Press.
[3] Aho A. - Sethi R. - Ullman J. Compilers: Principles, Techniques and Tools. Addison Wesley (1990).

El objetivo primario de este curso es introducir al alumno en los aspectos teóricos de Ciencias de la Computación que incluyen:
- El establecimiento de jerarquías y estudio de las propiedades de los distintos tipos de lenguajes, principalmente lenguajes de programación, a través de diferentes formalizaciones (dispositivos reconocedores y generadores).
- El estudio de análisis sintáctico y técnicas de análisis (Análisis Top-Down y Bottop-up).
- Profundización de la técnica de análisis sintáctico Bottom-up a través del estudio de gramáticas LR.

PROGRAMA SINTETICO:
Bolilla 1. Definiciones básicas: Lenguaje. Representación de los lenguajes. Dispositivos generadores y reconocedores. Jerarquía de Chomsky.

Bolilla 2. Lenguajes Regulares (Tipo 3): Autómata Finitos, expresiones regulares y gramáticas regulares. Analizador lexicográfico o Scanner. Redes de Petri.

Bolilla 3. Propiedades de los lenguajes regulares.

Bolilla 4. Gramáticas y lenguajes libres del contexto (Tipo 2). Autómatas a Pila (Push Down). Autómata Push-Down determinístico.

Bolilla 5. Propiedades de los lenguajes libres de contexto.

Bolilla 6. Analizador sintáctico Top-Down y Bottom-up. Gramáticas LR. Algoritmos de análisis sintáctico asociados.

Bolilla 7. Máquina de Turing. Gramáticas Irrestrictas. Lenguajes Sensibles del Sontexto o Tipo 1. Autómata Linealmente Acotado. Gramáticas Sensibles del Contexto.