Edición de «Teoría de Lenguajes»

{{Plan 1993|Lenguajes Formales, Autómatas y Computabilidad}}
'''Teoría de Lenguajes''' es una materia que tiene como objetivo presentar las nociones de lenguaje formal y de sintaxis y semántica de lenguajes, imprescindibles para la construcción de compiladores. Pertenece al [http://www.dc.uba.ar Departamento de Computación] y según el plan de la carrera, debería cursarse en Cuarto Año. Es correlativa de [[Lógica y Computabilidad]].
Se cursa los Lunes y Jueves.

==Programa==

'''Primera Parte'''

Introducción. Lenguajes y gramáticas. [[Clasificación de Chomsky]]. [[Lenguajes regulares]], Autómatas. Expresiones regulares. [[Equivalencia de construcciones regulares|Equivalencias entre expresiones regulares, gramáticas regulares y autómatas]]. [[Lema de pumping#Lenguajes regulares|Lema de pumping]]. [[Minimización de autómatas]]. [[Lenguajes regulares#Problemas decidibles|Decidibilidad de problemas básicos]] y [[Lenguajes regulares#Propiedades|propiedades de clausura]]. Analizadores lexicográficos. Lenguajes independientes de contexto. [[Arboles de derivación]]. [[Lema de pumping#Lenguajes independientes de contexto|Lema de pumping para lenguajes independientes de contexto]], Gramáticas reducidas. Autómatas de pila. Lenguajes determinísticos, Equivalencias entre autómatas de pila y gramáticas libres de contexto. 

'''Segunda Parte'''

Lenguajes tipo 1 y tipo 0. Máquinas asociadas. Parsers ascendentes y descendentes. Método LL(1). Parser descendente recursivo y por tablas. Transformación de gramáticas. Propiedades de las gramáticas LL(1). Métodos ascendentes. Métodos de precedencia. Métodos LR. LR(0). Propiedades. Métodos LR(0), SLR(1), LR(1) y LALR(1). Gramáticas de atributos. Definiciones guiadas por la sintaxis. Esquemas de traducción. Aplicación al análisis semántico y la generación de código. Semántica de los lenguajes de programación. Semántica operacional natural. Semántica operacional de computación.

==Prácticas==

'''Primer Parcial'''
*[[Práctica 0: Preliminares (Teoría de Lenguajes)|Práctica 0: Preliminares]]
*[[Práctica 1: Gramáticas Regulares y Autómatas Finitos (Teoría de Lenguajes)|Práctica 1: Gramáticas Regulares y Autómatas Finitos]]
*[[Práctica 2: Expresiones regulares (Teoría de Lenguajes)|Práctica 2: Expresiones regulares]]
*[[Práctica 3: Autómatas finitos -Continuación- (Teoría de Lenguajes)|Práctica 3: Autómatas finitos -Continuación-]]
*[[Práctica 4: Lenguajes regulares y lema de pumping (Teoría de Lenguajes)|Práctica 4: Lenguajes regulares y lema de pumping]]
*[[Práctica 5: Traductores finitos (Teoría de Lenguajes)|Práctica 5: Traductores finitos]]
*[[Práctica 6: Gramáticas libres de contexto y autómatas de pila (Teoría de Lenguajes)|Práctica 6: Gramáticas libres de contexto y autómatas de pila]]

'''Segundo Parcial'''
*[[Práctica 7: Maquinas de Turing y ALL (Teoría de Lenguajes)|Práctica 7: Maquinas de Turing y ALL]]
*[[Práctica 8: Escritura y simplificacion de GLC (Teoría de Lenguajes)|Práctica 8: Escritura y simplificacion de GLC]]
*[[Práctica 9: Parsers descendentes (Teoría de Lenguajes)|Práctica 9: Parsers descendentes]]
*[[Práctica 10: Gramaticas y parsers de precedencia (Teoría de Lenguajes)|Práctica 10: Gramaticas y parsers de precedencia]]
*[[Práctica 11: Gramaticas y parsers LR (Teoría de Lenguajes)|Práctica 11: Gramaticas y parsers LR]]
*[[Práctica 12: Gramaticas de atributos y TDS (Teoría de Lenguajes)|Práctica 12: Gramaticas de atributos y TDS]]

===2022===
*[https://drive.google.com/file/d/1Xd3fcwWIA93taaJkS_xUbsWLn7spHySO/view Mayoría de las guías prácticas resueltas, 1C 2022]

==Apuntes==

'''Ejercicios Resueltos'''
*[[Medio:Ejercicio_Pumping.pdf|Ej. de Pumping para regulares]]: contiene una explicación detallada de un ejercicio de la guía de Lema de Pumping para lenguajes regulares.

'''Apuntes de Clase'''
*[[Medio:Tleng_apunte_clase_anotado.tar.gz|Apuntes de clase]]: los apuntes que entrega Julio en la clase, con (bastantes) correcciones y algunas anotaciones extra.

'''Primer Parcial'''
*[http://www.exa.unicen.edu.ar/catedras/ccomp1/apuntes.htm Apuntes Varios]

'''Segundo Parcial'''
*[[Definiciones y teoremas (Teoría de Lenguajes)|Definiciones y teoremas]] 

'''Final'''
*[[Ejemplos de Lenguajes (Teoría de Lenguajes)|Ejemplos]]: Ejemplos de lenguajes y gramáticas vistos en la materia.
*[[Medio:TLeng_Resumen_Final_2022.pdf|Apunte/Resumen de Teoría de Lenguajes]], preparado por un alumno para rendir el final, y escrito en base a las clases teóricas (y complementado con las clases prácticas y un poquito de la bibliografía) del primer cuatrimestre de 2022. Contiene todos los temas que se vieron en la cursada, incluyendo teoremas con (generalmente) sus demostraciones.
*[[Medio:TLeng_Apunte_2015_Jsackmann.epub|Apunte de Teoría de Lenguajes]], por Julián Sackmann: contiene la parte de Julio y unos mínimos comentarios sobre parsing no determinístico. Preparado en 2015. Está en formato EPUB, para leer fácilmente desde eReaders.
*[[Medio:TLeng_Apunte_Latashen.pdf|Notas de estudio de Raul Latashen]] ([http://es.scribd.com/doc/49810902/Notas-de-Teoria-de-Lenguajes?secret_password=8x7y734fvrtjy9mgv0e Fuente original])
*[http://es.scribd.com/doc/49811568/Apunte-de-Teoria-de-Lenguajes?secret_password=11sxk5o1z1mrrw6erjs2 Apunte para el final de Soledad Ramusio]
*[[Demostraciones (Teoría de Lenguajes)|Demostraciones]]: Lista de las demostraciones vistas en la materia.
** [[Demostraciones Lenguajes Regulares (Teoría de Lenguajes)|Lenguajes Regulares]]
*[[Preguntas de Final (Teoría de Lenguajes)|Preguntas]]: Lista de ''algunas'' preguntas de final tomados en los últimos años.
*Preguntas 2022: Lista provista por Verónica Becher. Los finales fueron a libro abierto y tuvieron ejercicios ''de ese estilo'' (ninguno exactamente como esos).
**[[Medio:TLeng_preguntas-final_1c22.pdf|Julio 2022]]
**[[Medio:TLeng_preguntas-final_2c22.pdf|Noviembre 2022]]: [https://drive.google.com/file/d/1__a0oT5qbrc7aUTY1cVliVOEC-vxZiR_/view?usp=sharing Respuestas]

== Finales ==
Ver en [[Demostraciones (Teoría de Lenguajes)]] la nota sobre demostración de lema de pumping para LLC, lo toman siempre.

*[[Final del 20/12/23 (Teoría de Lenguajes)|Final del 20/12/23]]
*[[Final del 13/06/23 (Teoría de Lenguajes)|Final del 13/06/23]] [[Resolución Final del 13/06/23 (Teoría de Lenguajes)|Resolución]]
*[[Finales Virtuales Tleng| Finales virtuales]]
*[[Final del 25/09/20 (Teoría de Lenguajes)|Final del 25/09/20]]
*[[Final del 28/02/20 (Teoría de Lenguajes)|Final del 28/02/20]] 
*[[Final del 21/02/20 (Teoría de Lenguajes)|Final del 21/02/20]] 
*[[Final del 13/12/19 (Teoría de Lenguajes)|Final del 13/12/19]]
*[[Final del 13/11/19 (Teoría de Lenguajes)|Final del 13/11/19]]
*[[Final del 27/12/18 (Teoría de Lenguajes)|Final del 27/12/18]]
*[[Final del 08/08/18 (Teoría de Lenguajes)|Final del 08/08/18]]
*[[Final del 13/11/17 (Teoría de Lenguajes)|Final del 13/11/17]]
*[[Final del 19/05/17 (Teoría de Lenguajes)|Final del 19/05/17]]
*[[Final del 20/12/16 (Teoría de Lenguajes)|Final del 20/12/16]]
*[[Final del 26/07/16 (Teoría de Lenguajes)|Final del 26/07/16]]
*[[Final del 09/12/15 (Teoría de Lenguajes)|Final del 09/12/15]]
*[[Final del 19/02/15 (Teoría de Lenguajes)|Final del 19/02/15]]
*[[Final del 22/12/14 (Teoría de Lenguajes)|Final del 22/12/14]]
*[[Final del 12/09/14 (Teoría de Lenguajes)|Final del 12/09/14]]
*[[Final del 17/09/10 (Teoría de Lenguajes)|Final del 17/09/10]]
*[[Final del 11/08/08 (Teoría de Lenguajes)|Final del 11/08/08]]

==Parciales==

'''Primeros Parciales'''
* 2C 2023: [[Medio:tleng-23-2c-1p.pdf | Primer parcial]] | [[Medio:tleng-23-2c-1r.pdf | Primer recuperatorio]]
* 1C 2023: [[Medio:tleng-23-1c-1p.pdf | Primer parcial]] ([[Medio:TLeng_1parcial_08-05-2023.pdf|Resuelto]]) | [[Medio:tleng-23-1c-1r.pdf | Primer recuperatorio]]
* 2C 2022: [[Medio:tleng-22-2c-1p.pdf | Primer parcial]] | [[Medio:tleng-22-2c-1r.pdf | Primer recuperatorio]]
* [[Medio:TLeng_1parcial_02-05-22.pdf | Primer parcial 1C 2022]]
* [[Medio:TLeng_1parcial_29-4-21.pdf | Primer parcial 1C 2021]]
* [[Medio:tleng_2020_c2_rec1.pdf | Primer Recuperatorio 2C 2020]]
* [[Medio:TLeng_1parcial_23-9-19_resuelto.pdf | Primer Parcial 2C 2019 (Resuelto)]]
* [[Medio:1R1C2019-TLeng.pdf | Primer Recuperatorio 1C 2019 (Resuelto)]]
* [[Medio:1P1C2019-TLeng.pdf | Primer Parcial 1C 2019 (Resuelto)]]
* [https://drive.google.com/open?id=14RYiu__h3BN1z89EniGSeJbEXp8LDpqr Primer Recuperatorio 2C 2018]
* [[Medio:1P1C2018-TLeng.pdf ‎| Primer Parcial 1C 2018]]
*Primer Parcial 1C 2017:  [[Media:TLeng_1P_1C_2017.pdf|resolución (pdf)]],
*Primer Parcial 1C 2016:  [[Medio:TLeng 1parcial 30-04-16 ej1.png ‎|ej1]], [[Medio:TLeng 1parcial 30-04-16 ej2.png ‎|ej2]], [[Medio:TLeng 1parcial 30-04-16 ej3.png ‎|ej3]],
*[[Primer Parcial 1C 2012 (Teoría de Lenguajes)|Primer Parcial 1C 2012]]
*[[Primer Recuperatorio 2C 2006 (Teoría de Lenguajes)|Primer Parcial Recuperatorio 2C 2006]]

'''Segundos Parciales'''
* 2C 2023: [[Medio:tleng-23-2c-2p.pdf | Segundo parcial]] | [[Medio:tleng-23-2c-2r.pdf | Segundo recuperatorio]]
* 1C 2023: [[Medio:tleng-23-1c-2p.pdf | Segundo parcial]] | [[Medio:tleng-23-1c-2r.pdf | Segundo recuperatorio]]
* 2C 2022: [[Medio:tleng-22-2c-2p.pdf | Segundo parcial]] ([[Medio:TLeng_2parcial_2022.pdf|Resuelto]]) | [[Medio:tleng-22-2c-2r.pdf | Segundo recuperatorio]]
* 
* [[Medio:TLeng_2parcial_11-11-2021.pdf|Segundo Parcial 2C 2021 (Resuelto)]]
* [[Medio:TLeng_2recu_03-08-2020.pdf | Segundo Recuperatorio 1C 2020 (Resuelto)]]
* [[Medio:TLeng_2parcial_16-07-2020.pdf | Segundo Parcial 1C 2020 (Resuelto)]]
* Segundo Parcial 2C 2019 ([[Medio:TLeng_2parcial_2C_2019.pdf |Enunciado]]) ([[Medio:TLeng_2parcial_2C_2019_resolucion.pdf |Resolución]])
* [[Medio:2R1C2019-TLeng.pdf | Segundo Recuperatorio 1C 2019 (Resuelto)]]
* [[Media: Tleng_segundo_parcial_2019_2c.pdf | Segundo Parcial 1C 2019 (resuelto)]] 
* [https://drive.google.com/open?id=1fSiOPtR9SA_elpN8TOD08e-Pt0gD8MSo 2 Recu 2C 2018]
* [[Medio:2P2C2018-TLeng.pdf ‎| Segundo Parcial 1C 2018]]
*Segundo Parcial Recuperatorio 1C 2016: [[Medio:TLeng 2recu 04-07-16 ej1.png ‎|ej1]], [[Medio:TLeng 2recu 04-07-16 ej2.png ‎|ej2]], [[Medio:TLeng 2recu 04-07-16 ej3.png ‎|ej3]]
*Segundo Parcial 1C 2016: [[Medio:TLeng 2parcial 18-06-16 ej3.png ‎|ej3]]
*[[Segundo Parcial 1C 2012 (Teoría de Lenguajes)|Segundo Parcial 2C 2012]]
*[[Segundo Parcial 2C 2006 (Teoría de Lenguajes)|Segundo Parcial 2C 2006]]
*[[Segundo Recuperatorio 2C 2006 (Teoría de Lenguajes)|Segundo Parcial Recuperatorio 2C 2006]]
*[[Segundo Parcial 1C 2006 (Teoría de Lenguajes)|Segundo Parcial 1C 2006]]
*[[Segundo Recuperatorio 1C 2006 (Teoría de Lenguajes)|Segundo Parcial Recuperatorio 1C 2006]]

== Enlaces externos ==

*[http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/ Curso de compiladores de Stanford]
*[http://oscarbonilla.com/courses/compilers/ Slides de un curso de compiladores de Oscar Bonilla]
*[https://mdaines.github.io/grammophone/ Grammophone] Genera autómatas y tablas LR(0), SLR, LALR, LR(1) y chequea algunas propiedades.

[[Category:Materias]]
[[Category:Computación]]
[[Category:Programación]]