Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico Matemáticas y Naturales
Departamento: Informatica
Área: Area V: Automatas y Lenguajes
(Programa del año 2010)
(Programa en trámite de aprobación)
(Programa presentado el 01/09/2010 12:38:21)
I - Oferta Académica
Materia Carrera Plan Año Periodo
AUTOMATAS Y LENGUAJES LIC.EN CS.DE LA COMPUTACION 006/05 2010 1° cuatrimestre
II - Equipo Docente
Docente Función Cargo Dedicación
ROGGERO, PATRICIA BEATRIZ Prof. Responsable P.Adj Exc 40 Hs
APOLLONI, JAVIER MARIANO Responsable de Práctico JTP Exc 40 Hs
FUNEZ, DARIO GUSTAVO Auxiliar de Práctico A.1ra Exc 40 Hs
III - Características del Curso
Credito Horario Semanal Tipificación Duración
Teórico/Práctico Teóricas Prácticas de Aula Práct. de lab/ camp/ Resid/ PIP, etc. Total B - Teoria con prácticas de aula y laboratorio Desde Hasta Cantidad de Semanas Cantidad en Horas
Periodo
 Hs. 3 Hs. 3 Hs. 1 Hs. 7 Hs. 1º Cuatrimestre 15/03/2010 25/06/2010 15 105
IV - Fundamentación
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 provee los conceptos necesarios para el posterior estudio de computabilidad y complejidad de problemas.
V - Objetivos / Resultados de Aprendizaje
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 de análisis lexicográfico, en particular con el uso de herramientas como LEX.
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 profundiza en las técnicas Bottom-Up a través del estudio de gramáticas LR y el uso de herramientas tipo YACC.
VI - Contenidos
Bolilla 1.
Repaso General:
Conjuntos, funciones, relaciones y métodos de prueba. Alfabeto. Sentencia. Lenguaje. Representación de los lenguajes. Dispositivos generadores y reconocedores de lenguajes. Gramáticas y Autómatas. 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. 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, Lema de Pumping (bombeo) 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). 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. Autómata push-down determinístico y ambigüedad.

Bolilla 5.
Propiedades de los lenguajes libres del contexto: Formas Normales: Transformaciones sobre las gramáticas libres del contexto. 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. Uso de herramientas generadoras de parsers.

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.

VII - Plan de Trabajos Prácticos
Prácticos de Aula

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

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

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


Prácticos de Laboratorio:
A partir de una gramática particular que la cátedra les proveerá, los alumnos deberán:

1) Generar automáticamente un analizador lexicográfico, a través del uso de una herramienta, como jlex. El alumno debe entregar el código fuente y un informe escrito que detalle los pasos seguidos para la realización del trabajo.


2) Generar automáticamente un parser bottom-up, utilizando una herramienta como cup. El alumno debe entregar el código fuente y un informe escrito.

Estos prácticos se realizarán de manera paulatina, a medida que se den los conceptos teóricos y se realicen los prácticos de aula relacionados con los temas involucrados.
VIII - Regimen de Aprobación
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. Presentación, que incluye entrega de los programas fuentes y un reporte del trabajo realizado, y aprobación de los prácticos de laboratorio propuestos.

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

Nota:
1. Setenta por ciento (70%) es el porcentaje mínimo, de los ejercicios ha resolver, necesario para aprobar el 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.
b. El examen parcial deberá ser aprobado con nota superior al 80%.

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 admiten rendir examen final en condición de Libre.
D. El examen final puede ser oral y/o escrito.
IX - Bibliografía Básica
[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.
[7] Sipser Michael, Introduction to the Theory of Computation. PWS Publishing Company (1997).
X - Bibliografia Complementaria
[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).
XI - Resumen de Objetivos
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.
XII - Resumen del Programa
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.

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.
XIII - Imprevistos
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.
XIV - Otros