Materia	Carrera	Plan	Año	Periodo
AUTOMATAS Y LENGUAJES	LIC.CS.COMP.	32/12	2023	1° cuatrimestre

Docente	Función	Cargo	Dedicación
ROGGERO, PATRICIA BEATRIZ	Prof. Responsable	P.Asoc Exc	40 Hs
APOLLONI, JAVIER MARIANO	Prof. Colaborador	P.Adj Exc	40 Hs
FUNEZ, DARIO GUSTAVO	Responsable de Práctico	JTP Exc	40 Hs
GATICA, CLAUDIA RUTH	Auxiliar de Práctico	A.1ra Semi	20 Hs

Los conceptos involucrados en el estudio de la teoría de la computación o ciencias de la computación, forman parte del conocimiento general de un Licenciado en Ciencias de la Computación, con el perfil requerido por el plan de estudios vigente, entendiendo Ciencias de la Computación como el cuerpo de conocimiento que se ocupa del estudio de los fundamentos teóricos de la información y la computación y de su implementación y aplicación en sistemas computacionales.
Es por lo dicho que, resulta necesario abordar los 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 y teniendo como hilo conductor dicha Jerarquía de Chomsky.
Además resulta necesario brindar al futuro/a Licenciado/a una visión global y formal de la teoría de lenguajes, profundizando algunos de los conceptos abordados en la asignatura Análisis Comparativo de Lenguajes, e introduciendo nuevos contenidos teóricos y prácticos necesarios para que los/las 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, para llegar a la aplicación de estos conceptos al Análisis Lexicográfico y el Análisis Sintáctico, fases claves en el desarrollo de un compilador típico.
Los contenidos abordados se constituyen en insumo para la posterior realización de las asignaturas Computabilidad y Complejidad y Diseño y Construcción de Compiladores.
Desde este lugar la propuesta es la de, en un trabajo conjunto de docentes y estudiantes poder dar respuesta a los siguientes preguntas: ¿por qué estudiar la teoría de lenguajes formales?, ¿cuál es la relación de estos conceptos con lenguajes de programación?, ¿cuál es la utilidad de los diferentes dispositivos descriptores de lenguajes formales y cómo se utilizan en el contexto de los lenguajes de programación? En pos a dar respuesta a estos interrogantes, teniendo como meta trabajar para lograr una buena enseñanza, todo enmarcado en un clima de camaradería entre docentes y estudiantes, propiciando el debate, el trabajo colaborativo, la tarea en grupos, la autonomía, la participación, el contexto particular del aula y la educación para un mundo mejor, y para que los/las estudiantes empiecen a verse/sentirse como futuros profesionales, las clases serán llevadas a cabo de manera coherente para trabajar en estos aspectos descriptos.

Objetivos Educativos:
- Analizar críticamente los contenidos abordados, propiciando actividades de análisis de los marcos teóricos con la realidad del campo laboral.
- Vincular la teoría y la práctica con la intención encontrar alternativas que promuevan la buena enseñanza.
- Integrar el trabajo grupal, colaborativo y la autonomía, en toda la secuencia didáctica propuesta.
- Comprender las conceptos centrales de la teoría de la computación.
Objetivos de Aprendizaje:
- 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.
- Desarrollar los contenidos teóricos necesarios para abordar la introducción al 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.

Contenidos Mínimos: Introducción a los lenguajes formales. Jerarquía de Chomsky. Lenguajes regulares, Autómatas finitos y Gramáticas regulares. Expresiones regulares. Equivalencias, minimización, propiedades de clausura, lema de pumping. Analizador lexicográfico, construcción automática de analizadores lexicográficos. Lenguajes libres del contexto, Autómatas a pila y Gramáticas libres del contexto. Equivalencias, propiedades de clausura, lema de pumping. Análisis sintáctico (parsing). Técnicas. Implementación teórica y práctica de las técnicas de parsing. Construcción automática de analizadores sintácticos. Autómatas linealmente acotados y lenguajes sensibles del contexto, recursividad. Máquina de Turing y gramáticas irrestrictas.


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

Unidad 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 (ER). Propiedades de las ER. Equivalencias entre ER y AFND-épsilon. 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, construcción automática de analizadores lexicográficos.

Unidad 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. Minimización de Autómatas Finitos Determinísticos: testeo de estados equivalentes, transitividad de estados equivalentes, estados mutuamente equivalentes, algoritmo de minimización.

Unidad 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 y práctica de las técnicas de parsing utilizando Autómatas Push-Down. Construcción automática de analizadores sintácticos.

Unidad 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 unitarias, 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.

Unidad 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, recursividad.

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 código correspondiente que implementa la solución, junto con un informe escrito que describa el trabajo realizado, el cual tendrá un conjunto de pautas mínimas. Además cada grupo realizará una exposición oral de su trabajo.
Práctico de Investigación:
Análisis y discusión de un artículo científico en grupos de 2 a 4 estudiantes, sobre el tema expresiones regulares, cuyos objetivos son: comprender el trabajo, para luego explicarlo y debatirlo en la clase, además cada grupo deberá entregar un informe sobre el análisis desarrollado. Por otro lado el trabajo incluirá integrar el uso de una herramienta de IA, del estilo del chatbot GPT-3.

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.
Al comenzar el dictado de la materia se proveerá a los/las estudiantes el cronograma de las distintas instancias que conforman el proceso de evaluación continua.

El/la estudiante puede regularizar (para luego rendir el examen final) o promocionar, las condiciones que se establecen son las siguientes:

A. Régimen para Estudiantes Regulares
1. Entregar, en tiempo y forma, y aprobar el 100% de las actividades prácticas requeridas por la cátedra, las cuales consistirán en: la resolución de ejercicios del tipo de los prácticos de aula y/o la entrega de ejercicios particulares de los prácticos de aula, el práctico de laboratorio y el trabajo de investigación.
2. Aprobar 1 evaluación parcial o alguna de sus 2 (dos) recuperaciones, según lo establecido en la normativa vigente. Dicha evaluación parcial se aprueba con una nota mínima de 7 (siete).
3. Contar con un porcentaje mínimo igual o superior al 70% de asistencia a clases teóricas y prácticas.

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, las actividades 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.

B. Régimen para Estudiantes Promocionales
1. Ídem a lo requerido para estudiantes regulares, salvo el ítem 3., dado que se requiere un 80 % de asistencia a las clases teóricas y prácticas.
2. Responder preguntas teóricas, en las instancias de las actividades prácticas requeridas y en la evaluación parcial, con el objetivo de que el/la estudiante pueda corroborar el nivel de apropiación de los contenidos teóricos, favoreciendo de esta manera la formación continua.
3. Habiendo cumplimentado los ítems 1. y 2., el/la estudiante tendrá que desarrollar y aprobar un coloquio de carácter integrador oral o escrito que incluya el análisis y desarrollo de conceptos teóricos dictados en el curso.
En la nota final de aprobación se contemplarán las distintas instancias propuestas (actividades prácticas y la evaluación parcial). En todas las instancias, la nota obtenida por el alumno debe ser igual a 7 o superior, incluido el coloquio de carácter integrador.

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

[1] [1] Hopcroft J. y Ullman J.- “Introduction to automata theory, languages and computation”. Addison Wesley (1979).
[2] [2] Denning P.- Dennis J.- Qualitz J. Machine, languages and computation. Prentice-Hall (1978).
[3] [3] Davis - Weyuker. Computability, Complexity, and Languages. Academic Press (1992).
[4] [4] Aho A. - Sethi R. - Ullman J. Compilers: Principles, Techniques and Tools. Addison Wesley (1990).
[5] [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 SINTÉTICO:
Unidad 1. Definiciones básicas: Lenguaje. Representación de los lenguajes. Dispositivos generadores y reconocedores. Jerarquía de Chomsky.

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

Unidad 3. Propiedades de los lenguajes regulares. Minimización. Lema de Pumping.

Unidad 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

Unidad 5. Propiedades de los lenguajes libres de contexto. Formas Normales. Lema de Pumping.

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

 

Las vías de comunicación con los estudiantes son las siguientes:
- http://www.dirinfo.unsl.edu.ar/academico/carreras/licenciatura-en-ciencias-de-la-computacion
- Correos electrónicos de los docentes:
Patricia Roggero: proggero@email.unsl.edu.ar
Darío Funez: dgfunez@email.unsl.edu.ar
Claudia Gatica: crgatica@unsl.edu.ar
- Oficinas: box 4 y box 18, primer piso bloque II, teléfono 4520300, internos 2104 y 2118.