Ministerio de Educación, Ciencia y Tecnología
Universidad Nacional de San Luis
FACULTAD DE CS. FISICO MAT. Y NAT.

ANEXO II

PROGRAMA DEL CURSO: AUTOMATAS Y LENGUAJES

DEPARTAMENTO DE:   INFORMATICA
AREA: Area V: Automatas y LenguajesAÑO: 2003 (Id: 2007)
Estado: Aprobado

 

I - OFERTA ACADÉMICA

CARRERAS PARA LAS QUE SE OFRECE EL MISMO CURSO

PLAN DE ESTUDIOS
ORD. Nº

CRÉDITO HORARIO

   

SEM.

TOTAL

LIC. EN CIENCIAS DE LA COMPUTACION11/98798

II - EQUIPO DOCENTE

Funciones

Apellido y Nombre

Total hs en
este curso

Cargo y Dedic.

Carácter

Responsable

LEGUIZAMON, MARIO GUILLERMO20  hs.PROFESOR ADJUNTO EXC.Efectivo
Auxiliar de 1ºAPOLLONI, JAVIER MARIANO 10  hs.AYUDANTE DE 1RA. SEMI. Temporal

III - CARACTERÍSTICAS DEL CURSO

CREDITO HORARIO SEMANAL
MODALIDAD
REGIMEN

Teórico/

Práctico

Teóricas

Prácticas de

Aula

Práct. de lab/ camp/

Resid/ PIP, etc.

1c
 Hs.
3 Hs.
4 Hs.
 Hs.
Asignatura
Otro: 
Duración: 14 semanas
Período del 24/03/03 al 27/06/03

IV.- FUNDAMENTACION

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 lenguajes de programación previamente estudiados. Asimismo, involucra el desarrollo de los 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 programa-ción, a través de diferentes formalizaciones que incluyen dispositi-vos reconocedores (autómatas y redes de Petri) y generadores (gramá-ticas). Asimismo 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 genera-ció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 de Precedencia y LR.

 


VI. - CONTENIDOS

Bolilla 1.
Repaso general: Alfabeto. Sentencia. Lenguaje. Representación de los lenguajes. Dispositivos generativos y reconocedores. Gramáticas. Autómatas determinísticos y no determinísticos. Relación general entre autómata y gramática.

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.

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.
Parsing Bottom-up determinístico. Gramáticas de precedencia. Gramáticas de precedencia simple. Relaciones de precedencia. Teorema fundamental. Algoritmo de shift-reduce para gramáticas de precedencia. 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: construcción de items LR(1), redefinición de las operaciones de clausura y goto, construcción de tablas canónicas LR. Parsing LALR: construcción de tablas. Gramáticas Ambigüas: resolución de conflictos. Herramientas de generación de tablas LALR: Yet Another Compiler Compiler (YACC).


Bolilla 5
Conjuntos recursivos y recursivamente enumerables. Gramáticas
irrestrictas. Lenguajes Tipo 0. Máquina de Turing. Máquina de
Turing como reconocedor. Máquina de Turing como computadora de
funciones enteras. Máquina de Turing No Determinística. MT con
k-Cintas. Lenguajes Sensibles al Contexto o Tipo 1. Autómata
Linealmente Acotado. Propiedades de Clausura de los Lenguajes de Tipo
1. Jerarquía de Chomsky.

Bolilla 6
Definición de Redes de Petri, marcado y transición. Reglas de
Ejecución. Redes de Petri como reconocedoras de lenguajes. Etiquetado. Propiedades de clausura de los lenguajes de Redes de Petri.




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.

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: Máquina de Turing - Autómata linealmente acotado.

Práctico 6: Redes de Petri.


Prácticos de Máquina

Práctico 1: Diseño e implementación de un Analizador Lexicográfico para un lenguaje reducido usando LEX. Junto con el programa deberá ser entregado un informe sobre el mismo.

Práctico 2: Generación de un analizador sintáctico usando YACC.


VIII - RÉGIMEN 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 primer práctico de máquina propuesto (fuente y
ejecutable) incluyendo un reporte del trabajo realizado.

2. Presentación de dos prácticos de aula que incluyen una selección de ejercicios propuestos.

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

4. Aprobar un coloquio integrador oral 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 coloquio (punto 4.).


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

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. Realizar un examen escrito de la parte práctica.

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.a - BIBLIOGRAFÍA BÁSICA

Hopcroft J. - Ullman J. ``Introduction to automata theory, languages
and computation\\\'\\\'. Addison Wesley (1979).

Aho A. - Ullman J. ``The theory of parsing, translation and
compiling\\\'\\\'. Vol. I. Prentice Hall.

Hopcroft J. - Ullman J. ``Formal languages and their relation to
automata\\\'\\\'. Addison Wesley.

Peterson, James. ``Petri Net Theory and The Modeling of
Systems\\\'\\\'. Prentice-Hall Inc. (1981).

Sipser Michael, ``Introduction to the Theory of Computation\\\'\\\'. PWS Publishing Company (1997).

Sudkamp, Thomas A. ``Languages and Machines (An Introduction to the Theory of Computer Science)\\\'\\\'. Addison Wesley (1997).

Wood, Derick. ``Theory of computation\\\'\\\'. John Wiley & Sons, Inc.



IX b - BIBLIOGRAFÍA COMPLEMENTARIA


Denning P.- Dennis J.- Qualitz J. \\\"Machine, languages and computation\\\". Prentice-Hall (1978).

Davis - Weyuker. \\\"Computability, Complexity, and Languages\\\". Academic Press.

Aho A. - Sethi R. - Ullman J. \\\"Compilers: Principles, Techniques and Tools\\\". Addison Wesley (1990).



COMPLEMENTO DE DIVULGACION


OBJETIVOS DEL CURSO

El objetivo primario de este curso es introducir al alumno en los aspectos teóricos de Ciencias de la Computación que incluyen: intenta
- 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 de Precedencia y LR.

 

 

PROGRAMA SINTETICO

PROGRAMA SINTETICO:
Bolilla 1. Definiciones básicas: Lenguaje. Representación de los lenguajes. Dispositivos generativos y reconocedores.

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.

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 de precedencia. Gramáticas LR. Algoritmos de análisis sintáctico asociados.

Bolilla 5. Lenguajes recursivos y recursivamente enumerables. Máquina de Turing, diferentes modelos. Gramáticas Irrestrictas. Jerarquía de Chomsky. Lenguajes sensibles al contexto o Tipo 1. Autómata Linealmente Acotado. Propiedades de clausura de lenguajes tipo 1.

Bolilla 6. Redes de Petri. Lenguajes de Redes Petri.

 


IMPREVISTOS