PUERTA | PUERTA CS 1997 | Pregunta 55

Considere la gramática

S→ bSe
S→ PQR
P→ bPc
P→ ε
Q→ cQd
Q→ ε
R→ dRe
R→ ε

donde S,P,Q,R son símbolos no terminales, siendo S el símbolo de inicio; b, c, d, e son símbolos terminales y ‘ε’ es la string vacía. Esta gramática genera strings de la forma b ⁱ , c ^j , d ^k , e ^m para alguna i, j, k, m ≥ 0.

• (a). ¿Cuál es la condición sobre los valores de i, j, k, m  ?
• (b). Encuentre la string más pequeña que tenga dos árboles de análisis.

Respuesta:
Explicación: (a). Condición sobre los valores de i, j, k, m

i+k = j+m 

donde i, j, k, m >= 0

(b). La string más pequeña que tiene dos árboles de análisis = bcde
La producción utilizada para generar la string más pequeña es: –

S- > bSe
S- > bSe
S- > bSe
S -> PQR
P-> null
Q ->cQd
Q -> null
R- > null 

Finalmente, obtendrá la string como «bbbcdeee»
, lo que significa que i=3, j=1, k=1, m=3 y, por lo tanto, la respuesta i+k=j+m.

Ahora la producción utilizada para generar la string más pequeña es: –

S-> bSe 
S ->  bPQRe
S ->  bεQRe
S ->  bcQdRe
S ->  bcεdRe
S ->  bcdεe
S -> bcde 

Por lo tanto, la string más pequeña es bcde.
Por lo tanto, podemos ver que se genera el mismo número de b, c, d, e.
Las potencias de b, c, d, e son respectivamente i, j, k, m.
Por lo tanto, la relación entre i, j, k, m es: –

i+k = j+m   

Cuestionario de esta pregunta