Preguntas de Final (Teoría de Lenguajes)

Plantilla:Back 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.
• Demostrar las propiedades de los lenguajes libre de contextos: unión, concatenación, clausuras, intersección.

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 $\delta (q0,\gamma )$ contiene a $[A\rightarrow \alpha .\beta ]$ entonces $[A\rightarrow \alpha .\beta ]$ es ítem válido para $\gamma$ para el caso en el que la última transición (en el camino de $\gamma$) no está etiquetada con $\lambda$.

• 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.