Limpieza de gramaticasLa gramtica en cuestin del ejercicio es la siguiente: S A | BCa | aDcd | EDF A aAb | c B CD | b | ECd | Ad C Cc | Bb | AaE | D aDd | Dd | E aaEB | EFG F aFd | d

Eliminando Smbolos IntilesEn este paso, eliminaremos todos aquel os smbolos que sean intiles. Hay dos tipos de smbolos intiles: los no generadores y los no alcanzables.

Eliminando Smbolos No GeneradoresPara eliminar smbolos no generadores, primero tratamos de identificar todos aquel os smbolos que sean generadores. Aquel as variables que no podamos determinar que son generadoras pasarn a ser smbolos no generadores y se eliminarn. Por definicin, todos los smbolos terminales de una gramtica son generadores, ya que se generan a s mismos. Tambin ser un smbolo generador toda aquel a variable que tenga por lo menos una produccin que est conforme nicamente smbolo generador. Identifiquemos en nuestra gramtica nuestros smbolos generadores: A es generador, ya que tiene la produccin A c. Tambin lo es B, ya que tiene produccin vaca C tiene la produccin generador tambin. E no es un smbolo generador. Tiene dos producciones, es verdad. Una es E aaEB y la otra es E EFG, y en las dos hay presentes smbolos generadores, como por ejemplo a y B en la primera produccin y F en la segunda. Pero ninguna de dichas producciones est completamente compuesta por smbolos generadores. Miremos por ejemplo la segunda produccin: est presente la variable G, que no tiene ninguna produccin asociada, por lo que es incapaz de ser un smbolo generador. Descartamos esta produccin entonces. Veamos la primera produccin, tal vez descubramos algo: Mmmmh, tiene a la variable E entre medio, la cual todava no sabemos si es generadora. Qu recursivo, eh? Pues bueno, la recursin llega hasta ah: No sabemos si E es generador y no hay ninguna otra produccin deE que nos ayude a verificar esto, as que la primera produccin no nos sirve para determinar a E como un smbolo generador, y como no podemos verificar que E es un smbolo generador, entonces lo consideramos como un smbolo NO generador. Procedemos ahora a eliminar las variables E y G de la gramtica y a todas las producciones en las que

de

smbolos generadores. El string vaco se considera un

B b. C y D son generadores, ya que tienen la F d. Por ltimo, S

y D , respectivamente. F tiene la produccin

S BCa, donde tanto B, C como a son smbolos generadores, por lo tanto S es

estn presentes. O sea, eliminamos S EDF , B ECd, C AaE, E aaEB y E EF. La gramtica queda

como sigue: S A | BCa | aDcd A aAb | c B CD | b | Ad C Cc | Bb | D aDd | Dd | F aFd | d

Eliminando Smbolos No AlcanzablesPuede que, desde un principio o por producto de la eliminacin de algunos smbolos no generadores, nuestra gramtica presente smbolos no alcanzables o, dicho de otras palabras, smbolos que no son deribables (directa o indirectamente) desde el smbolo de inicio S. En nuestro ejemplo particular, nuestra querida variable F sufre de esta injusticia: ya no existe produccin que la derive desde el smbolo inicial dichas producciones se eliminaron cuando estbamos eliminando las variables S, pues

no generadoras.

Qu hacemos entoncs? Somos ms injustos an y la sacamos del grupo tambin. La gramtica nos

queda algo as: S A | BCa | aDcd A aAb | c B CD | b | Ad C Cc | Bb | D aDd | Dd |

Eliminando Producciones Ahora viene un paso un poco ms difcil. La eliminacin de producciones consiste principalmente en eliminar las producciones de la forma X . Cuando uno haga esto, lo que tendr que hacer es contemplar la posibilidad de que, en donde antes apareca la variable X, sta ahora podr aparecer o no aparecer, ya que en una estar jugando el papel de ser el string vaco y en la otra se estar siendo otra cosa. Ah! tiene Ya estamos listos entonces! Bueno, no del todo: Qu pasa si una variable

una produccin que est compuesta de varios smbolos que pueden ser reemplazables por el string vaco? Por

ejemplo, digamos que tenemos Y X1X2X3...Xn, donde todos los Xi pueden ser el string . Entonces nos quedara una cosa as: Y , que se puede simplificar por Y . Aqu vemos que Y tambin puede generar al string vaco. Entonces vamos a definir a los smbolos Anulables. Un smbolo anulable Y va a ser aquel que tenga entre sus producciones a la produccin Y o tambin aquel que tenga por lo menos una produccin en donde todas las

variables involucradas son anulables a su vez.Viendo nuestro ejemplo, podemos identificar rpidamente a dos variables que son smbolos anulables: las variables C y D, ya que ambas tienen la produccin de la forma Y . Pero ojo, que no son las nicas variables anulables. Tambin est B que tiene la produccin B CD, la cual est compuesta enteramente por

smbolos anulables.Bien, procedamos a eliminar las producciones . Cmo hacemos esto? Muy fcil: en

cada produccin en la que estaban presentes uno o ms smbolos anulables, vemos todas las combinaciones en las

que cada una de dichas variables pudiera estar presente o no. Por ejemplo, si tenemos la produccin Y abX1, donde X1 es anulable, entonces se generan las producciones Y abX1 y Y ab, una en donde

X1 est presente y otra en la que no. Veamos el caso para producciones con dos y tres variables anulables: Y aX1bbX2 => Y aX1bbX2 | aX1bb | abbX2 | abb Y cX1X2ddX3a => Y cX1X2ddX3a | cX1X2dda | cX1ddX3a | cX2ddX3a | cX1dda | cX2dda | cddX3a | cddaEn general, si tenemos una produccin con n smbolos anulables, tendremos que reemplazar esa produccin con a

lo ms 2n producciones. En nuestro caso, la gramtica quedara como sigue: S A | BCa | Ba | Ca | a | aDcd | acd A aAb | c B CD | C | D | b | Ad C Cc | c | Bb | b D aDd | ad | Dd | d