Materia	Carrera	Plan	Año	Periodo
AUTOMATAS Y LENGUAJES	LIC.CS.COMP.	18/11	2020	1° cuatrimestre
AUTOMATAS Y LENGUAJES	LIC.CS.COMP.	32/12	2020	1° cuatrimestre
AUTOMATAS Y LENGUAJES	LIC.CS.COMP.	006/05	2020	1° cuatrimestre

Docente	Función	Cargo	Dedicación
ROGGERO, PATRICIA BEATRIZ	Prof. Responsable	P.Adj Exc	40 Hs
APOLLONI, JAVIER MARIANO	Prof. Co-Responsable	P.Adj Exc	40 Hs
FUNEZ, DARIO GUSTAVO	Responsable de Práctico	JTP Exc	40 Hs

A partir de las resoluciones del Consejo Superior N° 30/20, N° 32/20 y N° 35/20 y 39/20 y de la Resolución de CD 18/20, en las cuales se aprueba la suspensión de actividades académicas en todo el ámbito de la Universidad Nacional de San Luis, en concordancia a las medidas adoptadas a nivel nacional por la pandemia del COVID-19, este programa se desarrollará en MODALIDAD NO PRESENCIAL, utilizando para tal fin diferentes herramientas virtuales, para el dictado de clases teóricas, clases de práctica, consultas y evaluaciones.

Se estudiarán aspectos formales de la Teoría de la Computación tales como: Teoría de Lenguajes Formales, Jerarquía de Chomsky, como así también cuáles son los modelos que permiten describir lenguajes formales, Modelos Reconocedores o Autómatas, Expresiones Regulares y Modelos Generadores o Gramáticas, siguiendo un enfoque integral, con el fin de analizar las características fundamentales de los Lenguajes de Programación.
Se abordarán los elementos teóricos y prácticos necesarios para que los estudiantes puedan incorporar y comprender las características de cada tipo de lenguaje, la forma en que funciona cada Autómata, y la correspondencia entre Autómatas, Gramáticas y Lenguajes.
También se estudiará la aplicación de estos conceptos al Análisis Lexicográfico y el Análisis Sintáctico.
Por otro lado el curso proveerá la introducción a los conceptos necesarios para el posterior estudio de Computabilidad y Complejidad de problemas.
Se propiciará en el alumno una aproximación significativa al aprendizaje favoreciendo la integración de los contenidos de una manera constructivista (pero además considerando el contexto social actual), teniendo como hilo conductor la Jerarquía de Chomsky.

Al finalizar el curso se espera que el estudiante 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 e implementación de un Analizador Lexicográfico. Todo esto a partir de poder visualizar e individualizar las características de los distintos lenguajes que se estudian, teniendo como hilo eje la Jerarquía de Chomsky.
También se pretende que el estudiante incorpore en el proceso de enseñanza aprendizaje los conceptos de análisis sintáctico, junto con las respectivas técnicas de análisis Top-Down y Bottom-Up.

Bolilla 1. Nociones Básicas (Repaso)
Símbolo. Alfabeto. Sentencia. Lenguaje. Representación de los lenguajes. Dispositivos generadores y reconocedores de lenguajes. Gramáticas y Autómatas, descripción general. Relación general entre Autómata y Gramática. Jerarquía de Chomsky.

Bolilla 2. Lenguajes Regulares
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 AFD y un AFND-épsilon. Expresiones regulares. Propiedades de las 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, demostración y usos de dichas propiedades, Lema de Pumping (bombeo), demostración y su aplicación, ejemplos. Minimización de autómatas finitos determinísticos: testeo de estados equivalentes, transitividad de estados equivalentes, estados mutuamente equivalentes, algoritmo de minimización.

Bolilla 4. Lenguajes Libres del Contexto
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). Configuraciones. 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. 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.

Bolilla 5. Propiedades de los lenguajes libres del contexto
Formas Normales. Transformaciones sobre las gramáticas libres del contexto: eliminación de símbolos inútiles, eliminación de producciones nulas, eliminación de producciones simples, eliminación de recursión a izquierda, Forma Normal de Chomsky. Lema de Pumping para gramáticas libres del contexto y su aplicación. Propiedades de clausura de los lenguajes libres del contexto.

Bolilla 6. Lenguajes Dependientes del Contexto e Irrestrictos
Introducción a las Máquinas de Turing y a las Gramáticas Irrestrictas. Lenguajes Sensitivos del Contexto o Tipo 1. Autómata Linealmente Acotado. Gramáticas Sensitivas del Contexto. Lenguajes Recursivos.

Prácticos de Aula

Práctico 1: Alfabetos - Lenguajes - Representación de lenguajes

Práctico 2: Autómatas Finitos Determinísticos y No Determinísticos - Expresiones Regulares - Gramáticas Regulares.

Práctico 3: Propiedades de los Lenguajes Regulares - Minimización -
Lema de Pumping.

Práctico 4: Gramáticas Libres del Contexto - Autómatas Push-Down - Análisis Sintáctico.

Práctico 5: Propiedades de los Lenguajes Libres de Contexto - Lema de Pumping - Formas Normales.

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

Práctico de Laboratorio 1:
Análisis Lexicográfico: diseñar un programa de computadora para resolver un ejercicio propuesto por la cátedra referente al tema, utilizando herramientas de diseño de analizadores lexicográficos y entregar el ejercicio resuelto.

El estudiante puede regularizar (luego rendir el examen final) o promocionar, las condiciones son, en función a la modalidad de dictado no presencial en la que se desarrollará el curso:

A. Régimen para Estudiantes Regulares

1. Entregar y aprobar el 80% de las evaluaciones periódicas, las cuales consistirán de la entrega de ejercicios de prácticos de aula, y/o entrega de ejercicios extras propuestos por los docentes, y/o desarrollo de trabajos de investigación de algún tema particular de los contenidos y exposición del mismo, y/o análisis de algún problema particular y posterior explicación (oral o escrita) del análisis realizado.

2. Aprobación del práctico de laboratorio propuesto.

Nota:
1. Setenta por ciento (70%) es el porcentaje mínimo, para aprobar las evaluaciones.
2. Si cualquier punto no fuera cumplimentado implicará que el estudiante pase a condición de libre.

B. Régimen para Estudiantes Promocionales

1. Idem a lo requerido para estudiantes regulares.

2. Además el estudiante tendrá que desarrollar un trabajo (monográfico o de investigación o una propuesta de aplicación o resolución de preguntas y/o problemas) que incluya el análisis y discusión de conceptos relevantes desarrollados en el curso, pudiendo requerir un coloquio adicional, a decisión de la cátedra, el cual será tomado una vez que se retorne al cursado presencial.
La nota final se computará promediando, las notas obtenidas en las evaluaciones requeridas para la regularidad y la nota obtenida en el ítem 2, la cual debe ser igual a 7 o superior, según lo establece el Régimen Académico.

C. El curso no admite rendir el examen final en condición de Libre.
D. El examen final puede ser oral y/o escrito.

[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. (2003).
[7] Ramón Brena Pinero "Lenguajes Formales y Autómatas" (1997).
[8] Apuntes de la Cátedra de "Análisis Lexicográfico y Herramienta JFlex" (2014).

[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).
[4] Sipser Michael, Introduction to the Theory of Computation. PWS Publishing Company (1997).

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

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. Minimización.

Bolilla 4. Gramáticas y lenguajes libres del contexto (Tipo 2). Autómatas a Pila (Push Down). Autómata Push-Down determinístico. Analizador sintáctico Top-Down y Bottom-up

Bolilla 5. Propiedades de los lenguajes libres de contexto. Formas Normales.

Bolilla 6. Máquina de Turing. Gramáticas Irrestrictas. Lenguajes Sensibles del Sontexto o Tipo 1. Autómata Linealmente Acotado. Gramáticas Sensibles del Contexto.

Debido al contexto de aislamiento social preventivo y obligatorio, es que el dictado del curso se realizará en MODALIDAD NO PRESENCIAL. Es por ello que los contenidos serán desarrollados en un mayor número de semanas, con menos carga semanal, atendiendo a la situación especial que atraviesa la sociedad, pero además a la particular de los estudiantes.
Aclaración: debido a que el sistema no permite el uso de decimales, para especificar las horas semanales, es que la cantidad de horas totales que da la cuenta (108), no se corresponden con el crédito horario de la asignatura (105).