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 2008)
(Programa en trámite de aprobación)
(Programa presentado el 17/06/2008 08:20:14)
I - Oferta Académica
Materia Carrera Plan Año Periodo
AUTOMATAS Y LENGUAJES LIC.EN CS.DE LA COMPUTACION 2008 1° cuatrimestre
II - Equipo Docente
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
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
0 Hs. 3 Hs. 3 Hs. 1 Hs. 7 Hs. 1º Cuatrimestre 10/03/2008 20/06/2008 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 es fundamental para el estudio de computabilidad y complejidad de problemas.
V - Objetivos
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.
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. 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.

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

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 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.
IX - Bibliografía Básica
[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.
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. 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.
XIII - Imprevistos