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: Automatas y LenguajesAÑO: 2001 (Id: 904)
Estado: En tramite de Aprobación

 

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/9812180

II - EQUIPO DOCENTE

Funciones

Apellido y Nombre

Total hs en
este curso

Cargo y Dedic.

Carácter

Responsable

LEGUIZAMON, MARIO GUILLERMO  hs.PROFESOR ADJUNTO EXC.Efectivo
Jefe Trab. Prác.ROGGERO, PATRICIA BEATRIZ  hs.JEFE DE TRABAJOS PRAC. EXC.Efectivo
Auxiliar de 1ºDNL   hs.AYUDANTE DE 1RA. EXC. Efectivo

DNL: Docente no listado

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
12 Hs.
6 Hs.
6 Hs.
 Hs.
Asignatura
Otro: 
Duración: 15 semanas
Período del 12/03/01 al 22/06/01

IV.- FUNDAMENTACION

El presente curso está destinado a alumnos avanzados de la Lic. en Ciencias de la Computación. Está orientado hacia el estudio formal de los conceptos previamente estudiados relacionados con lenguajes de programación y análisis de algoritmos. Asimismo, involucra el desarrollo los conceptos necesarios para su aplicación en la asignatura Compiladores, del segundo Cuatrimestre.


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 lo concerniente a lenguajes de programación, a través de diferentes formalizaciones (dispositivos reconocedores y generadores).
 El estudio de análisis sintáctico y las distintas técnicas de análisis y su implementación.
 La introducción a los conceptos fundamentales de Teoría de Computabilidad
 La posibilidad de determinar qué puede y no puede ser computado y analizar la complejidad computacional para aquellos problemas resolubles basándose en algún modelo formal de computación y en el concepto de reducción de un lenguaje a otro.

 


VI. - CONTENIDOS

Bolilla 1.

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.

Autómata Finito Determinístico (AFD). Lenguajes Regulares (Tipo 3). Autómata Finito No-Determinístico (AFND). Equivalencia de aceptación de un AFD y un AFND. AFND con transiciones épsilon(AFND-). Equivalencia de aceptación de un AFND y un AFND-. Propiedades de clau-sura de los lenguajes regulares. Expresiones Regulares. Relación con lenguajes regulares. Obtención de una Expresión regular a partir de un AFD. Lema de Pumping y sus aplicaciones. Minimización. Gramá-ticas regulares. Equivalencia de la familia de lenguajes generados por gramáticas regulares con lenguajes aceptados por Autómatas Finitos. Autómata finito con acciones semánticas. Analizador lexico-grá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. Cómo pasar de la gramática al autómata. Analizador sintáctico Top-Down y Bottom-up. Reducción. Cómo pasar del autóma-ta a la gramática. 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. Gramáticas de operadores. Gramáticas de precedencia entre operadores. Gramá-tica esqueleto. Algoritmo de shift-reduce para gramáticas de prece-dencia entre operadores. Funciones de precedencia.

Bolilla 4.

Conjuntos Enumerables. El método de la diagonal de Cantor. Número cardinal. Conjuntos finitos e infinitos. Teoremas relacionados. Algoritmo y Computabilidad. Conjuntos recursivos y recursivamente enumerables. Gramáticas irrestrictas. Lenguajes Tipo 0. Funciones y lenguajes computables. Funciones no computables. Tesis de Church. 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. Sistema de Post. Sistema de Post como generalización del concepto de gramática. Funciones recursivas primitivas, -recursivas. Equivalencia de los Modelos Formales. Máquina de Turing como enumerador. Caracterización de conjuntos recursivos y recursivamente enumerables. Máquina de Turing Univer-sal.

Bolilla 5.

Jerarquía de Chomsky. Lenguajes sensibles al contexto o Ti-po 1. Autó-mata Linealmente Acotado. Propiedades de clau-sura de los lenguajes tipo 1.


Bolilla 6.

Problemas resolu-bles y no resolubles. Concepto de Reducción de un pro-blema a otro. Propiedades de los lenguajes recursivos y recursivamente enumerables. Lenguajes no-recursivamente enumerables. Problema de Halting. Pro-blema de correspondencia de Post. Irresolubilidad del problema de correspondencia de Post. Problemas resolubles y no resolubles para lenguajes de tipo 0, 1, 2 y 3. Aplicación del problema de correspondencia de Post para gramáticas libres del contexto.


Bolilla 7:

Introducción al concepto de complejidad computacional. Complejidad temporal. Medida de complejidad - Notación “-grande”. Problemas de decisión tratables e intratables. Clases P y NP. NP-completitud. Problema de Satisfabilidad – Teorema de Cook. Problemas NP-completos (aplicación del concepto de reducción).


VII. - PLAN DE TRABAJOS PRÁCTICOS


1. Prácticos de Aula

P1 : Repaso (Funciones, relaciones, etc.)
P2 : Aplicaciones de AFs, AFD, AFND, AFND-, Expresiones Regulares,
Minimización, Gramáticas Regulares.
P3 : LEX
P4 : Gramáticas Libres del Contexto
P5 : Autómatas Push-Down.
P6 : Gramáticas de Precedencia.
P7 : Conjuntos enumerables y no enumerables – Cardinalidad
P8 : Máquina de Turing - Funciones Recursivas - Sistema de Post.
P9 : Autómata Linealmente Acotado.
P10: Problemas Resolubles y No Resolubles
P11: Complejidad Computacional

2 Práctico de Máquina:

Diseño e implementación de un Analizador Lexicográfico para un subconjunto del lenguaje Pascal usando LEX. Junto con el programa deberá ser entregado un informe sobre el mismo.


VIII - RÉGIMEN DE APROBACIÓN

El alumno podrá optar por cursar la materia bajo régimen promocional o regular:

1. Régimen para Alumnos Promocionales

a. Aprobar 2 exámenes parciales teórico/prácticos o sus respecti-
vas recuperaciones.
b. Exponer en clase un tema asignado por la cátedra.
c. Presentar un reporte que refleje el entendimiento de un
artículo asignado por la cátedra.
d. Presentación del práctico de máquina propuesto (fuente y
ejecutable) incluyendo un reporte del trabajo realizado.

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 cada parcial.

Si todos los puntos anteriores hubieran sido cumplimentados, excepto el punto (c), 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.

2. Régimen para Alumnos Regulares

a. Aprobar 2 exámenes parciales prácticos o sus respectivas recu-
peraciones
b. Exponer en clase un tema asignado por la cátedra.
c. Presentar el práctico de máquina propuesto (fuente y
ejecutable) incluyendo un reporte del trabajo realizado

En ambos casos, régimen promocional o regular, al menos el 50% de cada uno de los ejercicios involucrados en los parciales deberán ser completados para considerar la aprobación de cada parcial.


3. Régimen para Alumnos Libres

Para rendir en condición de libre, el alumno deberá:

 Presentar el práctico de máquina (fuente y ejecutable). Sobre éste,
la cátedra puede tomar un coloquio si lo cree conveniente.
 Realizar un examen escrito de la parte práctica.
 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


1. Aho - Ullman. "The theory of parsing, translation and compiling".
Vol. I. Prentice Hall.

2. Hopcroft - Ullman. "Introduction to automata theory, languages
and computation". Addison Wesley. (1977)

3. Denning - Dennis - Qualitz. "Machine, languages and computa-
tion". Prentice-Hall. (1978)

4. Davis - Weyuker. "Computability, Complexity, and Languages".
Academic Press. (1994)

5. Papadimitriou, C. & Lewis, H. “Elements of the Theory of
Computation”. Prentice Hall. (1998)

6. Sipser, Michael. “Introduction to the Theory of Computation. PWS
Publisihing Company. (1997)

7. Wood, Derick. "Theory of computation". John Wiley & Sons, Inc.



IX b - BIBLIOGRAFÍA COMPLEMENTARIA

1. Sudkamp, Thomas A. “Languages and Machines (An Introduction to the
Theory of Computer Science)”. Addison Wesley. (1996)

2. Hopcroft - Ullman. "Formal languages and their relation to
automata". Addison Wesley.

3. Papadimitriou - Steiglitz. “Combinatorial Optimization (Algorithms
and Complexity)”. Prentice Hall. (1982)



COMPLEMENTO DE DIVULGACION


OBJETIVOS DEL CURSO

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:
- 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, técnicas de análisis sintáctico
e implementación.
- La determinación de qué puede y no puede ser computado y el
análisis de la complejidad computacional para aquellos problemas
resolubles (recursos insumidos) basándose en algún modelo formal de
computación y en el concepto de reducción de un lenguaje a otro.

 

 

PROGRAMA SINTETICO

PROGRAMA SINTETICO:
Bolilla 1. Definiciones básicas: Lenguaje. Repre-sentación de los lenguajes. Dispositivos generativos y recono-cedores.

Bolilla 2. Lenguajes Regulares (Tipo 3): Autómata Finitos, expresiones regulares y gramáticas reuglares. Equivalencia de los distintos modelos. Propiedades de clausura. Lema de Pumping. Minimi-zación. Anali-zador lexico-gráfico o Scanner..

Bolilla 3. Gramáticas y lenguajes libres del contexto (Tipo 2). Ambigüedad. Transforma-ciones sobre gramá-ticas. Lema de Pumping para gramáticas libres del contexto. Propiedades de clausura Autómatas a Pila (Push Down). Autómata Push-Down determinístico. Analiza-dor sintáctico Top-Down y Bottom-up. Gramáticas de precedencia. Gramáticas de precedencia simple. Relaciones de precedencia. Algoritmo de shift-reduce para gramáticas de precedencia. Gramáticas de operadores. Gramáticas de precedencia entre operadores. Algoritmo de shift-reduce para gramáticas de precedencia entre operadores.

Bolilla 4. Conjuntos Enumerables. El método de la diagonal de Cantor. Número cardinal. Conjuntos finitos e infinitos. Algoritmo y Computa-bilidad. Conjuntos recursivos y recursivamente enumerables. Gramáticas irrestrictas. Lenguajes Tipo 0. Funciones y lenguajes computables. Funciones no computables. Tesis de Church. Máquina de Turing. Máquina de Turing como reconocedor y como computadora de funciones enteras. Máquina de Turing No Determinística. MT con k-Cintas. Sistema de Post. Funciones recursivas. Equivalencia de los Modelos Formales. Máquina de Turing como enume-ra-dor. Máquina de Turing Universal.

Bolilla 5. Jerarquía de Chomsky. Lenguajes sensibles al contexto o Ti-po 1. Autó-mata Linealmente Acotado. Propiedades de clausura de los lenguajes tipo 1.

Bolilla 6. Problemas resolu-bles y no resolubles. Concepto de Reducción de un pro-blema a otro. Propiedades de lenguajes recursivos y recursivamente enumerable. Problema de Halting. Problema de corres-pondencia de Post. Problemas resolubles y no resolubles para Aplicación del roblema de correspondencia de Post .

Bolilla 7: Complejidad temporal. Notación “-grande”. Problemas de decisión tratables e intratables. Clases P y NP. NP-completitud. Teorema de Cook. Aplicación del concepto de reducción.

 


IMPREVISTOS