Preguntas de Final (Teoría de Lenguajes)
![]() |
Volver a la página de la materia |
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.
Sumario
Lenguajes Regulares[editar]
- 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[editar]
- ¿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[editar]
- Probar que todo LDC es recursivo
Propiedades de Lenguajes[editar]
- 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.
- Demostrar las propiedades de los lenguajes libre de contextos: unión, concatenación, clausuras, intersección.
Pumping[editar]
- ¿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[editar]
- De un lenguaje estrictamente del tipo 2 que no sea LL(1) pero sí sea LR(0)
- Defina gramática de precedencia simple.
LR[editar]
- 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 contiene a entonces es ítem válido para para el caso en el que la última transición (en el camino de ) no está etiquetada con .
- 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[editar]
- Defina gramática LL(1)
Atributos y Compiladores[editar]
- 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.