Ejercicios para la evaluación continua

Tema 3: Gramàtiques incontextuals

Leyenda

= el ejercicio ha sido asignado a un/una estudiante/a y será resuelto en clase.
Para ver la asignación (y la fecha de entrega) consulta el racó.

Ejercicio 1 Doneu una gramàtica inambígua per a generar expressions amb operadors binaris de suma, resta, producte, divisió, i també admetent parentització explícita, de manera que l’arbre sintàctic generat es correspongui a la precedéncia habitual que donem als operadors.

Ejercicio 2 Justifica l’ambigüitat o no ambigüitat de les següents CFG’s:

1. $S \to (S)\ |\ SS\ |\$

2. $S \to (S)S\ |\$

3. $S \to aSb\ |\ B\\$ $B \to bAa\ |\ bCb\ |\ \lambda\\$ $A \to aAbA\ |\ bAaA\ |\ \lambda\\$ $C \to Aaa\ |\ aAa\ |\ aaA$

4. $S \to aU_1\ |\ aS\ |\ bZ_1\ |\ bS\\$ $Z_1 \to aU_2\ |\ bF\\$ $U_1 \to bU_2\\$ $U_2 \to bF\ |\ b\\$ $F \to aF\ |\ bF\ |\ a\ |\ b$

5. $S \to AaBA\ |\ ABaA\ |\ ACA\ |\ AbabA\\$ $B \to bb\\$ $C \to bB\\$ $A \to aA\ |\ bA\ |\ \lambda$

6. $S \to aU_1\ |\ aS\ |\ bZ_1\ |\ bS\\$ $Z_1 \to aU_2\ |\ bZ_2\\$ $U_1 \to bU_2\\$ $U_2 \to bF\\$ $Z_2 \to aF\ |\ bF\\$ $F \to aF\ |\ bF\ |\ \lambda$

7. $S \to Z_1a\ |\ Z_2b\\$ $Z_1 \to Z_1a\ |\ U_1b\\$ $Z_2 \to U_2a\ |\ Z_3b\\$ $Z_3 \to Fa\ |\ U_2\\$ $U_1 \to U_2\ |\ Fba\\$ $U_2 \to Fb\\$ $F \to Fa\ |\ Fb\ |\ \lambda$

Ejercicio 3 Demostreu que la gramàtica reunió $G_1\cup G_2$ de dues gramàtiques inambígües $G_1, G_2$ sí podria ser ambígua.

Ejercicio 4 Demostreu que la gramàtica concatenació $G_1\cdot G_2$ de dues gramàtiques inambígües $G_1, G_2$ sí podria ser ambígua.

Ejercicio 5 Demostreu que la gramàtica estrella $G^*$ d’una gramàtica inambígua $G$ sí podria ser ambígua.

Ejercicio 6 Demostreu que la gramàtica imatge $\sigma(G)$ d’una gramàtica inambígua $G$ per un morfisme $\sigma$ sí podria ser ambígua.

Ejercicio 7 Demostreu que la gramàtica revessada $G^R$ d’una gramàtica inambígua $G$ és també inambígua.

Ejercicio 8 Expliqueu el procediment d’eliminació de produccions nul.les i analitzeu-ne el temps de computació. Feu un exemple de la seva aplicació.

Ejercicio 9 Expliqueu el procediment d’eliminació de produccions unàries i analitzeu-ne el temps de computació. Feu un exemple de la seva aplicació.

Ejercicio 10 Explicqueu el procediment d’eliminació de símbols inútils i analitze-ne el temps de computació. Feu un exemple de la seva aplicació.

Ejercicio 11 Depureu (elimineu les $\lambda$-produccions, produccions unàries i símbols inútils) les CFGs següents:

1. $S \to SS \ |\ (S) \ |\ \lambda$

2. $S \to (S)S\ |\ \lambda$

3. $S \to AA\\$ $A \to AA\ |\ \lambda$

4. $S \to A\\$ $A \to B\\$ $B \to c$

5. $S \to AB\\$ $A \to a\ |\ \lambda\\$ $B \to b\ |\ \lambda$

6. $S \to AB\\$ $A \to aAb\ |\ \lambda\\$ $B \to bBc\ |\ \lambda$

7. $S \to BC\ |\ \lambda\\$ $A \to aA\ |\ \lambda\\$ $B \to bB\\$ $C \to c$

8. $S \to X\ |\ Y\\$ $X \to Xc\ |\ A\\$ $A \to aAb\ |\ \lambda\\$ $Y \to aY\ |\ B\\$ $B \to bBc\ |\ \lambda$

9. $S \to A\ |\ B\ |\ C\\$ $A \to SaSbS\ |\ \lambda\\$ $B \to SbSaS\ |\ \lambda\\$ $C \to Cc\ |\ \lambda$

Ejercicio 12 Expliqueu el procediment de passar d’una CFG $G$ a una CFG $G'$ equivalent en Forma Normal de Chomsky (CNF) i analitzeu-ne el temps de computació.

Ejercicio 13 Demostreu que totes les transformacions de gramàtiques exposades ens els exercicis anteriors preserven la no ambigüitat de la gramàtica original.

Ejercicio 14 Quin és el cost de l’algorisme CKY (o conegut també per CYK) per a decidir si una CFG $G$ donada genera un mot $w$ donat? Es a dir, descriviu i analitzeu el cost en temps de l’agorisme CYK tal que donada una CFG $G$ i donat un mot $w$, decideix si $w \in L(G)$.

Quin és el cost temporal si se suposa que $G$ és fixa i que per tant l’ entrada només conté $w$?

Ejercicio 15 Sigui $n$ el nombre de passos de derivació necessaris per a generar una certa palabra $w$ amb una certa CFG $G$ en forma normal de Chomsky. Podem establir alguna relació entre $n$ i $|w|$?

Ejercicio 16 Justifiqueu la veracitat o falsetat de les següents afirmacions per a CFGs $G,G_1,G_2,G_3$.

1. $(G^R)^R=G$.
2. $(G_1\cup G_2)^R=G_1^R\cup G_2^R$.
3. $(G^R)^*=(G^*)^R$.
4. $(G_1\cup G_2)G=(G_1G)\cup(G_2G)$.
5. $\sigma(G_1\cup G_2)=\sigma(G_1)\cup\sigma(G_2)$.
6. $G_1(G_2G_3)=(G_1G_2)G_3$.
7. $(G_1G_2)^R=G_2^RG_1^R$.

Ejercicio 17 Proposeu un algorisme de cost raonable per a decidir si una CFG d’ entrada genera algun mot.

Ejercicio 18 Proposeu un algorisme de cost raonable per a decidir si una CFG d’ entrada genera infinits mots.

Ejercicio 19 Proposeu un algorisme de cost raonable per a decidir si una CFG d’ entrada genera algun mot de longitud parell.

Ejercicio 20 Proposeu un algorisme de cost raonable per a decidir si una CFG d’ entrada genera infinits mots de londitud parell.

Ejercicio 21 Proposeu un algorisme de cost raonable per a calcular, donats una CFG $G$ i un natural $n$ d’entrada, quants arbres de derivació diferents de mots de mida $n$ genera $G$.

Ejercicio 22 Sigui $L$ un llenguatge incontextual infinit. Demostreu que hi ha una CFG $G$ tal que $\mathcal{L}(G)=L$ i totes les variables de $G$ generen un llenguatge infinit.