| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{Plan 1993|Lenguajes Formales, Autómatas y Computabilidad}}
| | '''Teoria 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 Computacion] y segun el plan de la carrera, deberia cursarse en Cuarto Año. Es correlativa de Logica 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, Miercoles y Jueves. |
| Se cursa los Lunes y Jueves. | |
|
| |
|
| ==Programa== | | ==Programa== |
| | *Introducción. |
| | *Lenguajes y gramaticas |
| | *Clasificación de Chomsky |
| | *Lenguajes regulares. Autómatas. |
| | *Expresiones regulares. |
| | *Equivalencias entre expresiones regulares, gramáticas regulares y autómatas. |
| | *Lema de pumping. |
| | *Minimización de autómatas. |
| | *Decidibilidad de problemas básicos y propiedades de clausura |
| | *Analizadores lexicográficos. |
| | *Lenguajes independientes de contexto. |
| | *Arboles de derivación. |
| | *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. |
| | *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. |
|
| |
|
| '''Primera Parte'''
| | ==Practicas== |
| | <br>Primer Parcial |
| | *[[Practica 0 - Preliminares]] |
| | *[[Practica 1 - Gramaticas Regulares y Automatas Finitos]] |
| | *[[Practica 2 - Expresiones regulares]] |
| | *[[Practica 3 - Automatas finitos - Continuacion]] |
| | *[[Practica 4 - Lenguajes regulares y lema de pumping]] |
| | *[[Practica 5 - Traductores finitos]] |
| | *[[Practica 6 - Gramaticas libres de contexto y automatas de pila]] |
|
| |
|
| 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.
| | ==Trabajos Prácticos Viejos== |
| | | [[:Media:TLeng-2006-01-TP-0001.pdf|2006 - 1er Cuatrimestre TP]] |
| '''Segunda Parte'''
| | <br> |
| | |
| 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.
| |
| *[[Medio:T._Leng._Guía_8.pdf|Soluciones Guía 8]]: Mini apunte y soluciones a ejercicios de la Guía 8
| |
| | |
| '''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 == | | == Enlaces externos == |
| | | <br>[http://www.dc.uba.ar/people/materias/tl/ Pagina Oficial de la Materia] |
| *[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:Materias]] |
| [[Category:Computación]] | | [[Category:Computación]] |
| [[Category:Programación]]
| |
