Tema 3.   Gramàtiques incontextuals

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.

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

1. ($a$)  

   $S$

   $\to$

   $(S)|SS|$

2. ($b$)  

   $S$

   $\to$

   $(S)S|$

3. ($c$)  

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

4. ($d$)  

   $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. ($e$)  

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

6. ($f$)  

   $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. ($g$)  

   $S$	$\to$	$Z_{1}a|Z_{2}b$
   $Z_{1}$	$\to$	$Z_{1}a|U_{1}b$
   $Z_{2}$	$\to$	$U_{2}a|Z_{3}b$
   $Z_{3}$	$\to$	$Fa|U_{2}$
   $U_{1}$	$\to$	$U_{2}|Fba$
   $U_{2}$	$\to$	$Fb$
   $F$	$\to$	$Fa|Fb|\lambda$

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.

Demostreu que la gramàtica concatenació $G_{1}\cdot G_{2}$ de de dues gramàtiques inambígües $G_{1},G_{2}$ sí podria ser ambígua.

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

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

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

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

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

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

1. ($a$)  

   $S$

   $\to$

   $SS|(S)|\lambda$

2. ($b$)  

   $S$

   $\to$

   $(S)S|\lambda$

3. ($c$)  

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

4. ($d$)  

   $S$	$\to$	$A$
   $A$	$\to$	$B$
   $B$	$\to$	$c$

5. ($e$)  

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

6. ($f$)  

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

7. ($g$)  

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

8. ($h$)  

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

9. ($i$)  

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

Expliqueu el procediment de passar d’una CFG $G$ a una CFG $G^{\prime}$ equivalent en Forma Normal de Chomsky (CNF) i analitzeu-ne el temps de computació.

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

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

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|$?

Justifiqueu la veracitat o falsetat de les següents afirmacions per a CFGs $G,G_{1},G_{2},G_{3}$.

1. ($a$)  
   ​

   $(G^{R})^{R}=G$.

2. ($b$)  
   ​

   $(G_{1}\cup G_{2})^{R}=G_{1}^{R}\cup G_{2}^{R}$.

3. ($c$)  
   ​

   $(G^{R})^{*}=(G^{*})^{R}$.

4. ($d$)  
   ​

   $(G_{1}\cup G_{2})G=(G_{1}G)\cup(G_{2}G)$.

5. ($e$)  
   ​

   $\sigma(G_{1}\cup G_{2})=\sigma(G_{1})\cup\sigma(G_{2})$.

6. ($f$)  
   ​

   $G_{1}(G_{2}G_{3})=(G_{1}G_{2})G_{3}$.

7. ($g$)  
   ​

   $(G_{1}G_{2})^{R}=G_{2}^{R}G_{1}^{R}$.

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

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

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

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

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$.

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.