CI-1322 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II Semestre 2002

$[\/]$

CI-1322 Autómatas y compiladores

Examen #2 [solución]

Duración: dos horas. Lea bien el examen antes de hacerlo. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva tres de las cuatro preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] (a+b) <: (c*D**F) <:= H ** i ** j

En esta expresión se usa el operador ternario para denotar rangos, que evalúa cada término y retorna "true" si la expresión del centro está entre las de los extremos.

1.a) [6 pts] De un ejemplo de cada una de los posibles rangos que se pueden expresar con el operador ternario de rangos.

1.b) [11 pts] Extienda la gramática de expresiones para que incluya los operadores ternarios de rangos. Al formar expresiones también permita que se use el operador de exponenciación "**", pero asegúrese de que tenga mayor precedencia que los operadores multiplicativos y de que sea asociativo a la derecha. Su gramática debe ser recursiva izquierda.

1.c) [5 pts] Transforme su gramática es una gramática que no sea recursiva izquierda.

1.d) [11 pts] Haga una derivación de una hilera "w" en la que aplique por lo menos 10 producciones de "G" y en la que se usen operadores ternarios, de exponenciación multiplicativos y aditivos.

2) [33 pts] Un palíndromo es una hilera que se lee igual hacia adelante que hacia atrás. Por ejemplo, "radar" y "aba" son palíndromos.

2.a) [7 pts] Escriba una gramática G que genere todos los palíndromos para el alfabeto Σ = {a,b,c}.

2.b) [7 pts] Calcule los conjuntos Primero() y Siguiente() para G. Diga si la gramática G es LL(1).

2.c) [11 pts] Haga la tabla SLR(1) para G. Interprete lo que ha obtenido.

2.d) [8 pts] Escoja una hilera "w" que esté en el lenguaje L(G) y que tenga al menos 10 símbolos. Procese su hilera "w" con la tabla de análisis sintáctico SLR(1) que ha calculado y diga cuál es la derivación más derecha que ha obtenido.

3) [33 pts] L₁ = { aⁿ bⁿ c^K | n ≥ 1 & K ≥ 1 } L₂ = { a^K bⁿ cⁿ | n ≥ 1 & K ≥ 1 }

3.a) [7 pts] Escriba una gramática G₁ para L₁ que no sea recursiva izquierda.

3.b) [11 pts] Haga las tablas LL(1) para la gramática G₁. Interprete lo que ha obtenido.

3.c) [4 pts] Escriba la gramática G₂ para L₂ que no sea recursiva izquierda.

3.d) [11 pts] Haga las tablas SLR(1) para la gramática G₂. Interprete lo que ha obtenido.

3.e) [0 pts] Calcule L₁ ∩ L₂. Explique qué puede concluir del valor calculado.

4) [33 pts] L = { aⁿ bⁿ c^m d^m | n ≥ 1 & m ≥ 1 } U { aⁿ b^m c^m dⁿ | n ≥ 1 & m ≥ 1 }

4.a) [11 pts] Describa en palabras cuáles son las hileras que pertenecen a L. Escriba una gramática G que genere L, o sea, que L(G) = L.

4.b) [11 pts] Hay lenguajes libres de contexto que son inherentemente ambiguos, pues cualquier gramática que los genere es ambigua. Muestre que su gramática G es ambigua.

4.c) [11 pts] Calcule los conjuntos Primero() y Siguiente() para su gramática G. Sin hacer el trabajo de calcular las tablas LL(1) para su gramática G, demuestre que G no es una gramática LL(1).

Soluciones

$[/\]$