Materia	Carrera	Plan	Año	Periodo
AUTOMATAS Y LENGUAJES	LIC.CS.COMP.	32/12	2016	1° cuatrimestre
AUTOMATAS Y LENGUAJES	LIC.CS.COMP.	006/05	2016	1° cuatrimestre

Docente	Función	Cargo	Dedicación
ROGGERO, PATRICIA BEATRIZ	Prof. Responsable	P.Adj Exc	40 Hs
APOLLONI, JAVIER MARIANO	Prof. Co-Responsable	P.Adj Exc	40 Hs
FUNEZ, DARIO GUSTAVO	Responsable de Práctico	A.1ra Exc	40 Hs
VILLEGAS, MARIA PAULA	Auxiliar de Práctico	A.1ra Simp	10 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, 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ómatas, gramáticas y lenguajes.
Por otro lado el curso provee los conceptos necesarios para el posterior estudio de computabilidad y complejidad de problemas.

Al finalizar el curso se espera que el alumno sea capaz de comprender los conceptos centrales de la teoría de lenguajes formales, autómatas y gramáticas, además de la forma en que funciona cada autómata y la correspondencia entre autómata, gramática y lenguajes, particularmente lenguajes de programación, como así también el estudio e implementación de un analizador lexicográfico.
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).

Bolilla 1.
Repaso General:
Alfabeto. Sentencia. Lenguaje. Representación de los lenguajes. Dispositivos generadores y reconocedores de lenguajes. Gramáticas y Autómatas, descripción general. 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. Propiedades de las Expresiones Regulares. Equivalencias entre expresiones regulares y autómatas finitos. Gramáticas regulares (Tipo 3)(Repaso). Equivalencia entre: lenguajes regulares, lenguajes aceptados por autómatas finitos determinísticos y gramáticas regulares. Autómata finito con acciones semánticas. Analizador lexicográfico o Scanner, uso de herramientas generadoras.

Bolilla 3.
Propiedades de los lenguajes regulares: Propiedades de clausura, demostración y usos de dichas propiedades, Lema de Pumping (bombeo), demostración y su aplicación, ejemplos. Minimización de autómatas finitos determinísticos: testeo de estados equivalentes, transitividad de estados equivalentes, estados mutuamente equivalentes, algoritmo de minimización.

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). Configuraciones. Lenguaje aceptado por Pila Vacía y Estado Final. Equivalencia de aceptación por Pila Vacía y Estado Final. Equivalencia entre gramáticas libres del contexto y autómatas push-down. Autómata push-down determinístico. 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.

Bolilla 5.
Propiedades de los lenguajes libres del contexto: Formas Normales. Transformaciones sobre las gramáticas libres del contexto: eliminación de símbolos inútiles, eliminación de producciones nulas, eliminación de producciones simples, eliminación de recursión a izquierda, Forma Normal de Chomsky. Lema de Pumping para gramáticas libres del contexto y su aplicación. Propiedades de clausura de los lenguajes libres del contexto.

Bolilla 6.
Lenguajes Irrestrictos. Introducción a las Máquinas de Turing y a las Gramáticas Irrestrictas. Lenguajes Sensitivos del Contexto o Tipo 1. Autómata Linealmente Acotado. Gramáticas Sensitivas del Contexto. Lenguajes Recursivos.

Prácticos de Aula

Práctico 1: Alfabetos - Lenguajes - Representación de lenguajes

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

Práctico 3: Propiedades de los Lenguajes Regulares.

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

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

Práctico 6: Máquina de Turing - Autómata linealmente acotado - Gramáticas Sensibles del Contexto.

Práctico de Laboratorio 1:
La cátedra proveerá una gramática asociada a un lenguaje de
programación y los alumnos deberán utilizarla para:

* Realizar un análisis exhaustivo con la finalidad de determinar cuáles son los tokens que dicha gramática puede generar.
* Implementar el analizador lexicográfico correspondiente.
* Entregar el código fuente, correctamente probado y funcionando, además de un informe escrito que detalle los pasos seguidos para la realización del trabajo.

Práctico de Laboratorio 2:
Implementación de algoritmos de transformación de las gramáticas libres del contexto. Con la finalidad de obtener gramáticas correctas, para ser ingresadas como entrada, al algoritmo para obtener gramáticas en Forma Normal de Chomsky.

* Entregar el código fuente, correctamente probado y funcionando.

El alumno puede regularizar (luego rendir el examen final) o promocionar, las condiciones son:

A. Régimen para Alumnos Regulares

1. Tener un mínimo de 60% de asistencia a las clases prácticas.

2. Entrega del 70% de los ejercicios de prácticos de aula solicitados.

3. Aprobación de los prácticos de laboratorio propuestos.

4. Aprobar 2 exámenes parciales prácticos o alguna de sus respectivas recuperaciones. Tal como lo establece la reglamentación vigente, Ord 32/14 CS, que modifica el Régimen de Regularización de Materias establecido según Ord. 13/03 CS, se otorgan dos (2) recuperaciones por cada parcial.

Nota:
1. Setenta por ciento (70%) es el porcentaje mínimo, de los ejercicios ha resolver, necesario para aprobar cada parcial. Además al menos el 50% de cada uno de los ejercicios involucrados en el parcial deberán ser completados para considerar su aprobación.
2. Si cualquier punto no fuera cumplimentado implicará que el alumno pase a condición de libre.

B. Régimen para Alumnos Promocionales

1. Idem a lo requerido para alumnos regulares, salvo que:
a. El alumno deberá asistir a un 80% de las clases teóricas y prácticas.
2. Aprobar, con un mínimo de 7 (siete), 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.

C. El curso no admite rendir el examen final en condición de Libre.
D. El examen final puede ser oral y/o escrito.

[1] Hopcroft J. - Ullman J. - Motwani R. Introduction to automata theory, languages and computation. 3º Edición. Addison Wesley (2006).
[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 (1973).
[4] Hopcroft J. - Ullman J. Formal languages and their relation to automata. Addison Wesley (1972).
[5] Sudkamp, Thomas A. Languages and Machines (An Introduction to the Theory of Computer Science). 3º Edición. Addison Wesley (2005).
[6] Wood, Derick. Theory of computation. John Wiley & Sons, Inc. (2003).
[7] Ramón Brena Pinero "Lenguajes Formales y Autómatas" (1997).
[8] Apuntes de la Cátedra de "Análisis Lexicográfico y Herramienta JFlex" (2014).

[1] Denning P.- Dennis J.- Qualitz J. Machine, languages and computation. Prentice-Hall (1978).
[2] Davis - Weyuker. Computability, Complexity, and Languages. Academic Press (1992).
[3] Aho A. - Sethi R. - Ullman J. Compilers: Principles, Techniques and Tools. Addison Wesley (1990).
[4] Sipser Michael, Introduction to the Theory of Computation. PWS Publishing Company (1997).

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).

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 Determinísticos y No Determinísticos, Expresiones Regulares y Gramáticas Regulares. Analizador lexicográfico o Scanner.

Bolilla 3. Propiedades de los lenguajes regulares. Minimización.

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

Bolilla 5. Propiedades de los lenguajes libres de contexto. Formas Normales.

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

Eventualmente si por motivos de fuerza mayor, no se cuenta con la totalidad de las semanas de clase previstas, el profesor responsable determinará que temas serán propuestos para que los alumnos estudien por su cuenta.