Diferencia entre revisiones de «Teoría de Lenguajes»

De Cuba-Wiki
Sin resumen de edición
 
(No se muestran 127 ediciones intermedias de 53 usuarios)
Línea 1: Línea 1:
'''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.
{{Plan 1993|Lenguajes Formales, Autómatas y Computabilidad}}
Se cursa los Lunes, Miercoles y Jueves.
'''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==
==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'''


==Trabajos Prácticos Viejos==
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.
[[:Media:TLeng-2006-01-TP-0001.pdf|2006 - 1er Cuatrimestre TP]]
 
<br>
'''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.
*[[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'''
* [[Medio:TLeng_1parcial_02-10-2023.pdf | Primer parcial 2C 2023]]
* [[Medio:TLeng_1parcial_08-05-2023.pdf | Primer parcial 1C 2023 (Resuelto)]]
* [[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'''
* [[Medio:TLeng_2parcial_2022.pdf|Segundo Parcial 2C 2022 (Resuelto)]]
* [[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]
 
<br><font color=white> [Practicas] </font>
*[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]]

Revisión actual - 15:32 4 feb 2024

Esta página es sobre la materia del plan de estudios 1993. Para ver la materia del plan 2023, consultar 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 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[editar]

Primera Parte

Introducción. Lenguajes y gramáticas. 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.

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[editar]

Primer Parcial

Segundo Parcial

2022[editar]

Apuntes[editar]

Ejercicios Resueltos

Apuntes de Clase

  • Apuntes de clase: los apuntes que entrega Julio en la clase, con (bastantes) correcciones y algunas anotaciones extra.

Primer Parcial

Segundo Parcial

Final

Finales[editar]

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

Parciales[editar]

Primeros Parciales

Segundos Parciales

Enlaces externos[editar]

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Teoría_de_Lenguajes&oldid=15991»