Edición de «Preguntas de Final (Teoría de Lenguajes)»

{{Back|Teoría de Lenguajes}}
Esta es una lista que ejemplifica algunas de las preguntas tomadas en finales de esta materia. Esta lista no pretende ser extensiva ni completa, sólo debe ser tomada (como mucho) a modo orientativo. Además de ellas, por ejemplo, también se suelen tomar las demostraciones de varios teoremas.

= Lenguajes Regulares =

* Sea L un lenguaje regular generado por una gramática regular derecha. 
** Indique qué lenguaje generará la gramática obtenida a partir de invertir la parte derecha de las producciones que generaban L.
** Dado un AFD que acepta el lenguaje regular L, indique como construir el AF que acepta Lr.
** Indique como obtendría el AFD correspondiente a un lenguaje regular expresado con una gramática regular izquierda.
* Cómo demuestra que un lenguaje regular L sobre sigma es equivalente a sigma*?
* Defina la relación de k-indistinguibilidad.
* Enuncie y demuestre la propiedad de la k-indistinguibilidad usada como criterio de parada en el algoritmo de minimización. (puede usar para la demostración las otras propiedades de la k-indistinguibilidad)
* Demuestre la equivalencia entre gramática regular a izquierda y gramática regular a derecha.
* Defina y demuestre la equivalencia entre AFND-L y AFND

= Lenguajes Libres de Contexto =

* ¿Cuáles son las condiciones para que un autómata de pila sea determinístico? 
* Diga y justifique si el método que permite pasar de un AP que termina por estado final a un AP que termina por pila vacía , preserva o no el determinismo. 

= Lenguajes Dependientes del contexto =

* Probar que todo LDC es recursivo 

= Propiedades de Lenguajes =

* Demuestre que la intersección de un lenguaje regular y un lenguaje estrictamente libre de contexto es un lenguaje libre de contexto.
* Demuestre que la intersección entre el lenguaje L sobre sigma formado por todas las cadena de la forma ww, donde w pertenece a sigma* y el lenguaje regular dado por la expresión a+b+a+b+ no es un lenguaje libre de contexto.
* Diga si el lenguaje L del item anterior es del tipo 2. Justifique.

== Pumping ==

* ¿Porqué para la demostración del lema de pumping para lenguajes del tipo 2 se considera un  árbol de derivación cuya altura es mayor al cardinal del conjunto de no terminales de la gramática? 
* En el lema de pumping para lenguajes del tipo 3, ¿El "numero de pumping" n debe ser siempre mayor o igual a la cantidad de estados del automata del lenguaje?
* En el lema de pumping para lenguajes del tipo 2, ¿Porqué se considera un árbol de altura |VN| +1, donde VN es el conjunto de no terminales de la gramática?
* Demostrar el lema de Pumping para lenguajes libres de contexto.

= Parsers =

* De un lenguaje estrictamente del tipo 2 que no sea LL(1) pero sí sea LR(0)
* Defina gramática de precedencia simple.

== LR ==

* Sea C el conjunto de símbolos de lookahead del item LR(1) [A->w. , C] ¿Es C un subconjunto de los siguientes(A)? Justifique.
* Sea M el AFD correspondiente a un analizador sintáctico LR(1) y M’ el AFD correspondiente al analizador sintáctico LALR(1) obtenido a partir de M. ¿Pueden aparecer conflictos de reducción-desplazamiento en la tabla del analizador sintáctico LALR(1) si no estaban en el analizador sintáctico LR(1)? Justifique.
* ¿Es siempre posible analizar sintácticamente con un analizador sintáctico LR(1) un lenguaje fuertemente tipado? Justifique
* Para demostrar que el conjunto de prefijos viables de un lenguaje libre de contexto es regular, se construye un AFND-L. 
** Indique cuales son las reglas para su construcción.
** Demuestre que, dado el AFND-L construido según las reglas preguntadas en el item anterior, si <math>\delta(q0,\gamma)</math> contiene a <math>[A\rightarrow \alpha. \beta ]</math> entonces <math>[A\rightarrow \alpha . \beta ]</math> es ítem válido para <math>\gamma</math> para el caso en el que la última transición (en el camino de <math>\gamma</math>) no está etiquetada con <math>\lambda</math>.

* Indique cómo se construye el autómata finito no determinístico lambda para reconocer los prefijos viables de una gramática LR(0). 
* Indique si el pasaje de LR(1) a LALR(1) puede generar a conflictos desplazamiento-reducción que no existían en la tabla LR(1). 
* Defina prefijo viable.
* Dar la 'nueva' definicion que utiliza la catedra de LR(k)

== LL ==

* Defina gramática LL(1)

= Atributos y Compiladores =

* Dé un ejemplo de DDS donde en las reglas semánticas se realice coerción de tipos. ¿De que tipo de coerción se trata?
* De un ejemplo de DDS donde se genera código intermedio diferente para un operador sobrecargado. Use el operador "+" entre enteros y entre reales. Para generar el código use dos macros diferentes sin ser necesario detallar su definición.
* Defina que es un sistema de tipos y que es un lenguaje fuertemente tipado. 
* ¿Qué es un código de tres direcciones? ¿Porqué se usa? Muestre al menos, dos tipos diferentes de proposiciones. 
* ¿Puede, mediante una definición dirigida por la sintaxis con condicionales, analizar el lenguaje an bn usando una gramática regular? Justifique. 
* Es el lenguaje L ={ww} sobre {a,b}libre de contexto? Considere una gramática G regular e indique atributos y reglas semánticas en G talque usada con un analizador sintáctico reconozca sólo las cadena de L. Nota: Considere la disponibilidad de las siguientes funciones para ser usadas en las reglas semánticas: longitud de cadena, extracción de subcadena y comparación de cadenas.

[[Category:Finales]]