Materia	Carrera	Plan	Año	Periodo
TEORÍA DE LA COMPUTACIÓN	LIC.CS.COMP.	RD-3-1/2023	2025	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 formales 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 Fundamentos del Diseño de Lenguajes de Programación, 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. Algunos contenidos abordados se constituyen en insumo para la posterior realización de la asignatura Computabilidad y Complejidad.
Desde este lugar la propuesta es la de, en un trabajo conjunto de docentes y estudiantes poder dar respuesta a las 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.

Se presentan a continuación una serie de objetivos tanto de carácter general o transversal como de carácter específico, que se pretende que alcancen los/las estudiantes a lo largo del dictado del curso.
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 de 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 los 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, en función a la Jerarquía de Chomsky.
- Vincular la teoría formal de lenguajes con los lenguajes de programación.
- Diseñar soluciones que resuelvan un problema de la realidad dado en forma de enunciado.
En el transcurso del dictado de esta asignatura se trabajarán de manera transversal los siguientes ejes:
Identificación, formulación y resolución de problemas de informática.
Utilización de técnicas y herramientas de aplicación en la informática
Fundamentos para el desempeño en equipos de trabajo.
Fundamentos para la comunicación efectiva.
Fundamentos para la acción ética y responsable.
Fundamentos para el aprendizaje continuo.

Contenidos mínimos: Introducción a los lenguajes formales. Jerarquía de Chomsky. Fundamentos de autómatas y gramáticas. Lenguajes regulares, autómatas finitos, gramáticas regulares, expresiones regulares. Equivalencias y propiedades. Lenguajes libres del contexto, autómatas a pila y gramáticas libres del contexto. Equivalencias y propiedades. Lenguajes dependientes del contexto, Autómatas linealmente acotados, Gramáticas dependientes del contexto. Lenguajes irrestrictos, Máquina de Turing y gramáticas irrestrictas.


Unidad 1. Nociones Básicas
Introducción a los lenguajes formales. Definición y especificación de lenguajes formales: alfabeto, cadena, lenguaje. Representación de los lenguajes formales. Dispositivos generadores y reconocedores: gramáticas y autómatas. Fundamentos de autómatas y gramáticas. 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 (o Tipo 3). Equivalencia entre lenguajes aceptados por AFD y generados por Gramáticas Regulares. Aplicaciones de AFD, AFND y ER.

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, ejemplos. 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
Lenguajes Libres del Contexto (Tipo 2). Motivación e introducción. Gramáticas Libres del Contexto (GLC). Árbol de derivación o sintáctico. Frontera. Forma sentencial izquierda y derecha. 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. Autómata Push-Down Determinístico. Análisis Sintáctico.

Unidad 5. Propiedades de los Lenguajes Libres del Contexto
Propiedades de clausura de los Lenguajes Libres del Contexto. Formas Normales. Transformaciones sobre las Gramáticas Libres del Contexto. Lema de Pumping para Gramáticas Libres del Contexto y su aplicación.

Unidad 6. Lenguajes Dependientes del Contexto e Irrestrictos
Lenguajes Dependientes del Contexto (Tipo 1). Autómata Linealmente Acotado. Gramáticas Dependientes del Contexto. Lenguajes Recursivos. Lenguajes irrestrictos (Tipo 0). Introducción a las Máquinas de Turing y a las Gramáticas Irrestrictas.

Prácticos de Aula:
Práctico 1: Alfabetos - Lenguajes - Representación de lenguajes
Objetivos: recuperar conceptos estudiados previamente, que sirven de fundamento para el abordaje de los contenidos que se desarrollan en esta actividad curricular.
Metodología: lectura de la bibliografía propuesta, para de manera autónoma, realizar los ejercicios propuestos. Posteriormente en clase a partir de consultas de las/los estudiantes analizar los resultados obtenidos.

Práctico 2: Lenguajes Regulares
Objetivos: comprender las características principales de dichos lenguajes, como así también diseñar diferentes dispositivos para describirlos: Autómatas Finitos Determinísticos y No Determinísticos - Expresiones Regulares - Gramáticas Regulares. Vincular estos conceptos con lenguajes de programación y problemas del mundo real.
Metodología: desarrollo de ejercicios de construcción de Autómatas, Expresiones Regulares y Gramáticas Regulares, asociados a lenguajes y a problemas del mundo real.

Práctico 3: Propiedades de los Lenguajes Regulares - Minimización - Lema de Pumping.
Objetivos: analizar las propiedades de clausura de los lenguajes regulares, construir autómatas mínimos y utilizar una herramienta que permite determinar cuándo un lenguaje no es regular.
Metodología: desarrollo de ejercicios en papel, discusión en clase y trabajo de tipo expositivo por parte de los/las estudiantes. Discusión en clase de las soluciones a las que arriben los/las estudiantes.

Práctico 4: Lenguajes Libres del Contexto
Objetivos: comprender y construir Gramáticas Libres del Contexto, Autómatas a Pila, para diferentes lenguajes, incluyendo construcciones propias de los lenguajes de programación. Trabajar con un analizador sintáctico provisto por la cátedra.
Metodología: desarrollo de ejercicios en papel. Discusión en clase de las soluciones a las que arriben los/las estudiantes.

Práctico 5: Propiedades de los Lenguajes Libres de Contexto - Lema de Pumping - Formas Normales. Objetivos: analizar las propiedades de clausura de los lenguajes libres del contexto y utilizar como
herramienta el Lema de Pumping, para determinar que ciertos lenguajes no son libres del contexto.
Metodología: desarrollo de ejercicios en papel, discusión en clase y trabajo de tipo expositivo por parte de los/las estudiantes. Discusión en clase de las soluciones a las que arriben los/las estudiantes.

Práctico 6: Máquina de Turing - Autómata Linealmente Acotado - Gramáticas Dependientes del Contexto.
Objetivos: comprender y construir Autómatas Linealmente Acotados y Máquinas de Turing, comparar con las máquinas previamente abordadas.
Metodología: desarrollo de ejercicios en papel. Discusión en clase de las soluciones a las que arriben los/las estudiantes.

En la mayoría de los prácticos se utilizan notebook de Python para que los/las estudiantes puedan comprobar la resolución de ciertos ejercicios.

Práctico de Formación Experimental:
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 basadas en expresiones regulares y entregar el código correspondiente que implementa la solución, finalizadas las clases estipuladas para realizar dicho trabajo.

Práctico de Investigación:
Análisis y discusión, en grupos de al menos 4 estudiantes, de un tema propuesto por la cátedra, en este caso sobre Gramáticas de Atributos, una extensión de las Gramáticas Libres del Contexto, con la finalidad de comprender el tema, dar ejemplos y realizar un conjunto de ejercicios, para ello cada grupo tendrá que desarrollar un informe que responda al conjunto de ítems solicitados, y, además, realizar una exposición oral en clase del trabajo desarrollado.

A continuación, se presenta la descripción del abordaje de cada uno de los ejes introducidos previamente en los objetivos, como así también, de las metodologías de evaluación de los mismos:
- Identificación, formulación y resolución de problemas de informática.
Se aborda particularmente desde el práctico 2 en adelante, dado que se plantean problemas actuales de informática que pueden ser modelados e implementados utilizando algunos de los autómatas (AFD, AFND) que se estudian, con Expresiones Regulares, Autómatas Finitos, Gramáticas Libres del Contexto. Pero además se analizan y resuelven problemas propios del campo de la especificación de lenguajes de programación, como por ejemplo búsqueda de patrones en textos.
Se trabaja con evaluación continua o formativa, para se solicitará la entrega de ejercicios correspondientes a los prácticos de aula, o en algunos casos resolver en clase un ejercicio, una vez revisadas las entregas la metodología utilizada puede ser la de que los/las estudiantes realicen una autoevaluación para luego re entregar, o, coevaluación entre pares, o la devolución por parte del equipo de docentes.
La intencionalidad de este tipo de evaluación es la de que el/la estudiante pueda identificar su nivel de apropiación de los contenidos a medida que atraviesa cada unidad temática y a los docentes les brinda información acerca de la situación particular de cada estudiante para realizar un andamiaje adecuado en los casos que así lo requieran.
Además, se realiza una evaluación del tipo sumativa (con sus respectivas recuperaciones).
- Utilización de técnicas y herramientas de aplicación en la informática.
Se aborda la utilización de herramientas de aplicación para realizar búsqueda de patrones en textos usando Expresiones Regulares y/o Autómatas Finitos. Uso de herramientas tipo Jflex, que permite especificar patrones con expresiones regulares, principalmente en el práctico de formación experimental.
Respecto a la evaluación, se verifica que se utilicen de manera eficiente las herramientas, para el desarrollo del práctico de formación experimental, para ello se trabaja con entregas parciales del práctico, hasta obtener la versión definitiva.
- Fundamentos para el desempeño en equipos de trabajo.
La propuesta es que el trabajo de formación experimental se realice conformando equipos de 2 estudiantes, por otro lado, el trabajo de investigación en grupos de al menos 4 estudiantes. Los proyectos grupales permiten que los/las estudiantes interactúen en el grupo y también, cuando se hacen las presentaciones orales la interacción con los demás grupos.
En el informe los estudiantes deben describir ventajas y desventajas de trabajar en equipo.
Este trabajo de investigación, tiene que ser expuesto y debatido en clase, con la participación de todos los integrantes del equipo. Finalizadas las presentaciones se realiza una devolución por parte del cuerpo docente.
- Fundamentos para la comunicación efectiva.
Para el trabajo de formación experimental y el de investigación, se solicita la presentación de un informe escrito en formato académico, en base a una guía propuesta. Pero en toda la secuencia de trabajos que entreguen los estudiantes, también se revisan los aspectos que tienen que ver con la comunicación de manera adecuada.
También se propicia el debate de temas en clase, para incentivar el diálogo y la comunicación oral.
En las correcciones informadas se hace hincapié no sólo en lo disciplinar sino también en lo referido a la presentación de los informes.
Con la presentación del trabajo de formación experimental y el de investigación, se verifica que el/la estudiante vaya adquiriendo la capacidad de expresarse utilizando la terminología adecuada, acorde a los contenidos vistos en la asignatura, como así también que se respete el formato especificado en la guía de informe.
Se evalúa la comunicación oral y la capacidad de transmitir las ideas tanto de los expositores, como de la clase en el momento de realizar preguntas. También se evalúa el tipo de presentación utilizada.
- Fundamentos para la acción ética y responsable.
Se comparte el cronograma con la descripción de las actividades/evaluaciones.
En todas las actividades solicitadas se describen plazos y forma de entrega.
En la redacción de informes se enfatiza sobre la correcta referencia al material bibliográfico.
Se verifica que las actividades sean entregadas respetando las fechas y formatos pactados, que sean producciones propias y que en las entregas grupales hayan participado todos los integrantes.
- Fundamentos para el aprendizaje continuo.
Tanto las actividades teóricas como prácticas comienzan con un repaso de contenidos previos, con la participación de los/las estudiantes, a partir de dar respuestas a preguntas y/o consultas y/o resolución de ejercicios en pizarrón por parte de los/las estudiantes, etc.
La evaluación formativa, el trabajo de investigación y el práctico de formación experimental, permiten desarrollar en el/la estudiante la capacidad de aprender de forma continua.
Se verifica que todos/as los/las estudiantes participen de las distintas actividades propuestas, además de promover la participación.
Se realiza una corrección informada de las actividades para que cada estudiante vaya observando el nivel de apropiación de los contenidos.

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 formación experimental y el práctico de investigación.
2. Aprobar 1 evaluación parcial o alguna de sus 2 (dos) recuperaciones, según lo establecido en la normativa vigente.
3. Contar con un porcentaje mínimo igual o superior al 70% de asistencia a clases teóricas y prácticas.
En todas las instancias, la nota obtenida por el/la estudiante debe ser igual a 7 o superior.

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. Aprobar, 2 tests teóricos, 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 todos los conceptos abordados en el curso.
En todas las instancias, la nota obtenida por el/la estudiante debe ser igual a 7 o superior.
En la nota final de aprobación por promoción se contemplarán todas las instancias evaluativas propuestas (actividades prácticas, evaluación parcial, práctico de formación experimental y el práctico de investigación, coloquio 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] 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] Peter Linz. “An Introduction to Formal Languages and Automata“. Jones & Bartlett Learning. 5° Edición. (2012).
[4] 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).
[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).

El objetivo primario de este curso es introducir al/la estudiante en los aspectos teóricos de Ciencias de la Computación, tomando como eje la Jerarquía de Chomsky, para el estudio de las propiedades de los distintos tipos de lenguajes formales y principalmente lenguajes de programación, a través de diferentes formalizaciones (dispositivos reconocedores y generadores).

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

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

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

 

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 18 y box 4, primer piso bloque II, teléfono 4520300, internos 2118 y 2104, respectivamente.