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

Docente	Función	Cargo	Dedicación
ROGGERO, PATRICIA BEATRIZ	Prof. Responsable	P.Asoc 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
VILLEGAS, MARIA PAULA	Auxiliar de Práctico	A.1ra Semi	20 Hs

Debido al contexto epidemiológico actual, en concordancia a las medidas adoptadas a nivel nacional y provincial por la pandemia del COVID-19, este programa se desarrollará en MODALIDAD MIXTA (MAYORMENTE 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: Jerarquía de Chomsky, Teoría de Lenguajes Formales, 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.

- Proporcionar herramientas conceptuales que les permita a los/las estudiantes comprender los conceptos centrales de la Teoría de Lenguajes Formales, tales como: Autómatas, Gramáticas y su aplicación, en particular en el contexto de los Lenguajes de Programación.
- Analizar e individualizar las características de los distintos tipos de lenguajes.
- Aplicar los conceptos desarrollados en la implementación de un Analizador Lexicográfico.
- Efectuar algunos desarrollos teóricos tendientes a favorecer un acercamiento a los conceptos de análisis sintáctico, junto con las respectivas técnicas de análisis Top-Down y Bottom-Up.
- Promover la revisión crítica de los temas abordados, propiciando la discusión y el trabajo en grupo y colaborativo.

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ómatas Finitos Determinísticos (AFD) y No-Determinísticos (AFND). Equivalencia de aceptación entre AFD y AFND. AFND con transiciones épsilon. Equivalencia de aceptación entre AFD y AFND-épsilon. Expresiones Regulares. Propiedades de las Expresiones Regulares. Equivalencias entre Expresiones Regulares y autómatas finitos. Gramáticas Regulares (Tipo 3). Equivalencia entre lenguajes aceptados por AFD y generados por 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 teórica 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ácticos de Laboratorio:
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.
Implementar un autómata a pila, para un lenguaje particular suministrado por la cátedra.

La propuesta de trabajo, en lo que respecta al régimen de aprobación, está basada en la evaluación continua o formativa, con el objetivo de relacionar la información sobre la evolución del proceso de aprendizaje de los/las estudiantes con las características de la acción didáctica, a medida que se desarrollan y progresan las actividades de enseñanza y aprendizaje.

En este sentido, el estudiante puede regularizar (para luego rendir el examen final) o promocionar. Las condiciones en función a la modalidad de dictado mayormente no presencial y a la metodología propuesta en la que se desarrollará el curso, son las siguientes:

A. Régimen para Estudiantes Regulares
Entregar, en tiempo y forma, y aprobar el 100% de las evaluaciones periódicas propuestas por la cátedra, las cuales consistirán en ejercicios de los prácticos de aula, y/o ejercicios prácticos extras propuestos por los docentes, y/o prácticos de laboratorio, y/o trabajos de investigación, que pueden incluir exposición, de temas o problemas particulares sobre los contenidos de la materia.

Con la finalidad de realizar un trabajo colaborativo de comprensión, se efectuarán devoluciones de las instancias evaluativas como parte del proceso de aprendizaje. Además, todas las evaluaciones pueden tener una instancia de defensa oral posterior a la entrega donde el/la estudiante exponga, explique y responda dudas o inquietudes de sus compañeros y/o docentes acerca del trabajo realizado en sus entregas.

Los/las estudiantes deben contar además con un porcentaje mínimo igual o superior al 60% de participación activa en todas las actividades sincrónicas y asíncronas propuestas por los docentes durante el cursado de la materia.

Nota:
1. Las evaluaciones se aprueban con un porcentaje mínimo de setenta por ciento (70%).
2. Si cualquier punto no fuera cumplimentado implica que el estudiantes pase a condición de libre.

B. Régimen para Estudiantes Promocionales
1. Ídem a lo requerido para estudiantes regulares excepto que se debe alcanzar un porcentaje de asistencia igual o superior al 80%.
2. Además el estudiante tendrá que desarrollar y aprobar un coloquio integrador oral o escrito que incluya el análisis y discusión de conceptos teóricos dados en el curso. Dicho coloquio podrá ser de forma virtual o presencial (en el caso que estén dadas las condiciones para ello).

La nota final de promoción se computará promediando, las notas obtenidas en las evaluaciones requeridas para la regularidad y la nota obtenida en el ítem 2 del punto B. En todas las evaluaciones, la nota obtenida por el alumno debe ser igual a 7 o superior, según lo establece la normativa vigente.

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”. Addison Wesley. 3° Edición. (2007).
[2] Sudkamp, T.A. - “Languages and Machines (An Introduction to the Theory of Computer Science)”. Addison Wesley. 3° Edición. (2005).
[3] Sipser, M. – “Introduction to the Theory of Computation”. PWS Publishing Company. 3° Edición. (2013).
[4] Aho A. - Ullman J. The theory of parsing, translation and compiling. Vol. I. Prentice Hall (1973).
[5] Hopcroft J. - Ullman J. Formal languages and their relation to automata. Addison Wesley (1972).
[6] Apunte realizado por la Cátedra de "Análisis Lexicográfico - JFlex".
[7] Notas de Clase de la Cátedra.

[1] Hopcroft J. y Ullman J.- “Introduction to automata theory, languages and computation”. Addison Wesley (1979).
[2] Denning P.- Dennis J.- Qualitz J. Machine, languages and computation. Prentice-Hall (1978).
[3] Davis - Weyuker. Computability, Complexity, and Languages. Academic Press (1992).
[4] Aho A. - Sethi R. - Ullman J. Compilers: Principles, Techniques and Tools. Addison Wesley (1990).
[5] Ramón Brena Pinero "Lenguajes Formales y Autómatas" (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.

El presente programa puede presentar ajustes dada la situación epidemiológica por COVID19. Toda modificación será acordada y comunicada con el estudiantado e informada a Secretaría Académica.

Aclaración: de acuerdo al art. 2 de la Resolución Rectoral 1404/20, el Calendario Académico de la Universidad Nacional de San Luis establece que el Primer Cuatrimestre sea de 14 semanas. A los efectos de que se impartan todos los contenidos y se respete el crédito horario establecido en el Plan de Estudios de la carrera para esta asignatura, se establece que se de cómo máximo 8 horas por semana distribuidas en teorías, prácticos de aula y laboratorio y consultas, hasta completar las 105 horas correspondientes al Crédito Horario Total de la asignatura.