Práctica 8: Escritura y simplificacion de GLC (Teoría de Lenguajes)

Ejercicio 01

Dada la gramática G = <Vn, Vt, P, S>

Donde:

Vn = {S, B}

Vt = {a, b}

P = { S -> aBBa, B -> b | bB }

a) Definir el lenguaje generado.

b) Para la cadena abbba encontrar:

• Una derivación más a la izquierda
• Una derivación más a la derecha
• El árbol de derivación

c) ¿Es ambigua la gramática? Justifique su respuesta.

• a) L={a.b^m.b^n.a | m,n>=1}
• b)
  • IZQ: S->aBBA->abBBA->abbBa->abbba
  • DER: S->aBBa->aBba->abBba->abbba
• c) Es ambigua (hay 2 arboles de derivacion)

Ejercicio 02

L = L1 U L2

L1 = {a^n.b^n.c^m / n >= 1, m >= 1}

L2 = {a^n.b^m.c^m / n >= 1, m >= 1}

¿Es posible definir una GLC para L? Explique.

S-> XC | AY
X-> ab | aXb
C-> c | cC
A-> a | aA
Y-> bc | bYc

Este lenguaje, que es equivalente a {a^i.b^j.c^k | i=j o j=k, i,j,k>=1}, es inherentemente ambiguo (todas sus GLC son ambiguas). Se tendría un árbol de derivación, cuando i=j y otro cuando j=k. En consecuencia, si una cadena tiene i=j=k, tendrá dos derivaciones siempre.

Ejercicio 03

Dada la gramática G = <Vn, Vt, P, E> Donde:

Vn = {E} Vt = {id, +, *, (, )} P = {E -> E + E | E * E | (E) | id}

a) Pruebe que la gramática es ambigua. b) Encuentre una gramática equivalente no ambigua tal que el árbol de derivación de la cadena refleje la precedencia de los operadores.

a) Mostrar que E + E * E tiene dos derivaciones posibles

b) E -> E+T | T
   T -> T*F | F
   F -> id | (E) | num

Ejercicio 04

Para las siguientes gramáticas:

S -> CAb | B
A -> Ca | &lambda
B -> Eb | b | &lambda
E -> Ea | a

S -> A | B | Ca
A -> bA | aAb | &lambda
B -> CB | CS | &lambda
C -> bC | bA | d

a) Determinar si la cadena nula pertenece o no al lenguaje

b) Eliminar reglas borradoras

c) Eliminar reglas de renombramiento

d) Eliminar símbolos inútiles

• i)

S −> Eb|b|λ
E −> Ea|a

• ii)

S -> A|B|C|Ca|λ
A -> bA|aAb|b|ab
B -> CB|CS
C -> bC|bA|d

i)

a) Sí: S -> B ->&lambda

b) Si regla borradora es lo mismo que regla anulable:

S -> Cb | B | CAb | &lambda
A -> Ca
B -> Eb | b
E -> Ea | a

c)

S -> Cb | Eb | b | CAb | &lambda
A -> Ca
E -> Ea | a 

d) Los símbolos inútiles son:

  * Los símbolos inactivos
  * los símbolos inalcanzables

En este caso, el único símbolo inútil (inactivo) es C. Quitando aquellas producciones dónde está C, nos queda:

S -> Eb | b | &lambda
E -> Ea | a 

ii)

a) Sí: S -> A -> &lambda y S -> B -> &lambda

b)

S' -> S | &lambda
S -> A | B | Ca
A -> bA | aAb | b | ab
B -> CB | CS | C
C -> bC | bA | d

c)

S -> bA | aAb | b | ab | CB | CS | Ca
A -> bA | aAb | b | ab
B -> CB | CS | bC | bA | d
C -> bC | bA | d

d) No sé a qué se refiere

En general: para eliminar reglas borradoras (lo que yo supongo que significan reglas anulables): Asegurarse de que solamente el símbolo inicial produzca lambda, y que el símbolo inicial no esté a la derecha de ninguna producción. Si S tiene que producir lambda y estar a la derecha, definir S' nuevo símbolo inicial de la forma S' -> S | &lambda

Para eliminar renombres: Un renombre es una producción de la forma A -> B, con A y B pertenecientes a VN. Si tenemos A -> B, reemplazar ese B por cada lado derecho de las producciones que tengan a B en el lado izquierdo.

Ejercicio 05

Dar una gramática no ambigua para las listas de prolog

S-> [E] | []
E-> id | id,E | [] | [E] | [],E | [E],E

No posee reglas borradoras (la gramática no genera la cadena vacía).

No posee renombramientos puesto que no hay producciones del tipo A-> B con A,B no terminales.

No posee símbolos inútiles.

Ejercicio 06

Dar una gramática no ambigua para fórmulas químicas.

Ejemplos:

O₂

H₂O

Fe₂(Fe(CN)₃)₃

S->I|I(S) num
I->elem num | elem | elem num I | elem I

Ejercicio 07

E -> id | int | id unOp | E binOp C | E key: C | (E)
C -> E | E binOp C | E key: C