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 2006)
(Programa en trámite de aprobación)
(Programa presentado el 08/03/2006 17:33:43)
I - Oferta Académica
Materia Carrera Plan Año Periodo
AUTOMATAS Y LENGUAJES LIC. CS. COMP. 006/05 4 1c
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 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. 4 Hs.  Hs. 7 Hs. 1 Cuatrimestre 13/03/2006 16/06/2006 14 98
IV - Fundamentación
El presente curso esta destinado a alumnos avanzados de la Lic. en Ciencias de la Computación. Está orientado hacia el estudio de los conceptos formales relacionados con la teoría de lenguajes y los lenguajes de programación previamente estudiados. Asimismo, incluye el desarrollo de conceptos necesarios para su aplicación en la asignatura Compiladores, del segundo cuatrimestre, tales como análisis lexicográfico y sintáctico.
V - 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 que incluyen dispositivos reconocedores (autómatas y Redes de Petri) y generadores (gramá-ticas). También se procura introducir al alumno en el estudio del concepto de análisis sintáctico, las respectivas técnicas de análisis (Análisis Top-Down y Bottop-up) y el uso de herramientas de generación automática de analizadores lexicográficos y sintácticos. 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.
VI - Contenidos
Bolilla 1.
Repaso general: 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. Propiedades de clausura de los lenguajes regulares. Expresiones y Gramáticas regulares (Repaso). Lema de Pumping y sus aplicaciones. Equivalencia entre: lenguajes regulares, lenguajes aceptados por autómatas finitos determinísticos y no-determinísticos y gramáticas regulares. Minimización. 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.
Gramáticas y lenguajes libres del contexto (Tipo 2). Motivación e introducción. Arbol de derivación. Frontera. Forma sentencial izquierda y derecha. Ambigüedad. Transformaciones sobre gramáticas. Lema de Pumping para gramáticas libres del contexto. Propiedades de clausura de los lenguajes libres del contexto. 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 4
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. Herramientas de generación de tablas LALR: Yet Another Compiler Compiler (YACC).

Bolilla 5
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, etc.)

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

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

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

Práctico 5: 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 un lenguaje C++ reducido usando LEX. Junto con el programa deberá ser entregado un informe sobre el mismo.

Práctico de Investigación
Análisis e investigación del tema Redes de Petri y Redes de Petri como reconocedoras de lenguajes. Presentación de un informe del análisis efectuado, junto con algunos ejercicios propuestos y resueltos (mínimo 2).
VIII - Regimen de Aprobación
El alumno podrá optar por cursar la materia bajo régimen
promocional o regular:

A. Régimen para Alumnos Promocionales

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

2. Presentación del trabajo de investigación y desarrollo personal propuesto por la cátedra (Redes de Petri).

3. Aprobar 1 examen parcial teórico/práctico o su respectiva recuperación.

4. 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 (4), 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 4.).

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 y ejecutable).
Sobre éste, la cátedra puede tomar un coloquio si lo cree conveniente.

2. Presentar el práctico de investigación (Redes de Petri).

3. Realizar un examen escrito de la parte práctica.

4. 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.
IX - Bibliografía Básica
[1] Hopcroft J. - Ullman J. "Introduction to automata theory, languages and computation". Addison Wesley (1979).
[2] Aho A. - Ullman J. "The theory of parsing, translation and
[3] compiling". Vol. I. Prentice Hall.
[4] Hopcroft J. - Ullman J. "Formal languages and their relation to
[5] automata". Addison Wesley.
[6] Peterson, James. "Petri Net Theory and The Modeling of
[7] Systems". Prentice-Hall Inc. (1981).
[8] Sipser Michael, "Introduction to the Theory of Computation". PWS Publishing Company (1997).
[9] Sudkamp, Thomas A. "Languages and Machines (An Introduction to the Theory of Computer Science)". Addison Wesley (1997).
[10] Wood, Derick. "Theory of computation". John Wiley & Sons, Inc.
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.
[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, expresiones regulares y gramáticas regulares. Propiedades de clausura. Lema de Pumping. Minimización. Analizador lexicográfico o Scanner. Redes de Petri.

Bolilla 3. Gramáticas y lenguajes libres del contexto (Tipo 2). Lema de Pumping para gramáticas libres del contexto. Propiedades de clausura Autómatas a Pila (Push Down). Autómata Push-Down determinístico.

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

Bolilla 5. 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