Recuerden subir los archivos a Cuba-Wiki y no linkearlos de servidores externos, siempre siguiendo la convención de nombres descripta acá.

Segundo Parcial 1C 2012 (Teoría de Lenguajes)

De Cuba-Wiki

Ejercicio 1

Dada la gramática extendida: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G1 = <\{a,b,c,d,e\},\{S,A,B,C,D\},P,S>} con P:

  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S \rightarrow B}
  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B \rightarrow BbDda\ |\ a}
  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle D \rightarrow (e(ce)*\ |\ B)^+}

a) Dar una gramática LL(1) que reconozca el mismo lenguaje que G1.

b) Dar la implementación del parser recursivo iterativo ELL(1) para los no terminales B y D de la gramática original.

Ejercicio 2

Dada la gramática Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G = <\{x,a,b\},\{S',S,A\},P1,S'>} , con P1:

  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S' \rightarrow S $}
  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S \rightarrow A\ |\ xb}
  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow aAb\ |\ x}

Decidir si G es SLR. Para eso, construir la tabla. De haber conflictos, solucionarlos modificando la tabla, pero no la gramática.

Ejercicio 3

Dado un generador de notas de canciones (en cifrado estadounidense), se solicita agregarle una funcionalidad que permita detectar la presencia de versos de distintas cancione conocidas y rechazar algunas melodías que no satisfacen ciertas características.

Dados dos versos de cada una de las famosas canciones Funky Town y Low Rider:

FunkyTown(FT): ccacg - gcfec
LowRider(LR): bbbbbcdg - bcbg

y la gramática G2, se pide dar una gramática de atributos que sintetice:

a) la cantidad de versos de cada canción (FT y LR) contenidos en una canción dada.

b) la cantidad de versos que no son de ninguna de estas canciones (FT,LR).


Además, se solicita que las canciones generadas sean de tal forma que no puedan aparecer versos contiguos de FT y de LR (dados versos de distinta canción, entre ellos tiene que haber al menos un verso que no pertenezca a ninguna de ellas).

con P3:

  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle M \rightarrow T - M\ |\ \lambda}
  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T \rightarrow AcBC}
  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow bbbbb\ |\ b\ |\ c\ |\ g}
  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B \rightarrow d\ |\ b\ |\ ac\ |\ fe}
  • Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle C \rightarrow g\ |\ c}


Ejemplos:

  • ccacg-gcfec-bbbbbcdg-bcbg- no es una canción generable, dado que no hay un verso de otra canción que separe cgfec-bbbbbcdg.
  • gcfec-ccbc-bcbg-bbbbbcdg-ccbc-gcbc- es una canción posible. Devuelve 2 versos de LR, 1 verso de FT y 3 versos que no son de ninguna de ellas.


Notas:

  • Dos versos iguales cuentan como 2, no como 1.
  • Se puede asumir que se cuenta con una función de igualdad de strings.