Materia	Carrera	Plan	Año	Periodo
AUTOMATAS Y LENGUAJES	LIC.CS.COMP.	18/11	2022	1° cuatrimestre
AUTOMATAS Y LENGUAJES	LIC.CS.COMP.	32/12	2022	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

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.

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 (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, 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 código correspondiente que implementa la solución, junto con un informe escrito que describa el trabajo realizado.

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

El/la estudiante puede regularizar (para luego rendir el examen final) o promocionar. En función a la modalidad de dictado que será de manera presencial, en la medida que las condiciones epidemiológicas lo permitan, y a la metodología propuesta en la que se desarrollará el curso, las condiciones que se establecen 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 contenidos de la materia.
- Aprobar 1 examen parcial o alguna de sus 2 (dos) recuperaciones, según lo establecido en la normativa vigente.

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 70% de asistencia a las clases prácticas 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, pero en cada evaluación práctica tendrá que responder también, de manera correcta, ciertas preguntas de tipo teóricas, con el objetivo de favorecer la evaluación continua.
2. Habiendo cumplimentado el ítem 1., el/la estudiante tendrá que desarrollar y aprobar un coloquio integrador oral o escrito que incluya el análisis y desarrollo de conceptos teóricos dictados en el curso.

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.

De acuerdo al Calendario Académico de la Universidad Nacional de San Luis para el año 2022, se 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 den 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.


Correo de contacto: proggero@email.unsl.edu.ar