Simplificación de gramáticas libres de contexto

La definición de gramáticas libres de contexto (CFGs) nos permite desarrollar una amplia variedad de gramáticas. La mayoría de las veces, algunas de las producciones de CFG no son útiles y son redundantes. Esto sucede porque la definición de CFG no nos restringe de hacer estas producciones redundantes. 

Al simplificar los CFG, eliminamos todas estas producciones redundantes de una gramática, mientras mantenemos la gramática transformada equivalente a la gramática original. Dos gramáticas se llaman equivalentes si producen el mismo lenguaje. Es necesario simplificar los CFG para luego convertirlos en formas Normales. 

Los tipos de producciones redundantes y el procedimiento para eliminarlas se mencionan a continuación. 
1. Producciones inútiles – Las producciones que nunca pueden participar en la derivación de ninguna string, se denominan producciones inútiles. De manera similar, una variable que nunca puede participar en la derivación de ninguna string se denomina variable inútil. Por ej. 
 

S -> abS | abA | abB
A -> cd
B -> aB
C -> dc                         

En el ejemplo anterior, la producción ‘C -> dc’ es inútil porque la variable ‘C’ nunca aparecerá en la derivación de ninguna string. Las otras producciones están escritas de tal manera que la variable ‘C’ nunca puede alcanzarse desde la variable inicial ‘S’. 

La producción ‘B ->aB’ también es inútil porque no hay forma de que termine. Si nunca termina, nunca podrá producir una string. Por lo tanto, la producción nunca puede tomar parte en ninguna derivación. 

Para eliminar producciones inútiles, primero encontramos todas las variables que nunca conducirán a una string terminal como la variable ‘B’. Luego eliminamos todas las producciones en las que aparece la variable ‘B’. 
Entonces la gramática modificada se convierte en – 
 

S -> abS | abA
A -> cd
C -> dc

Luego tratamos de identificar todas las variables que nunca se pueden alcanzar desde la variable inicial, como la variable ‘C’. Luego eliminamos todas las producciones en las que aparece la variable ‘C’. 
La gramática a continuación ahora está libre de producciones inútiles: 
 

S -> abS | abA
A -> cd

2. Producciones λ – Las producciones de tipo ‘A -> λ’ se denominan producciones λ (también denominadas producciones lambda y producciones nulas). Estas producciones solo se pueden eliminar de aquellas gramáticas que no generan λ (una string vacía). Es posible que una gramática contenga producciones nulas y, sin embargo, no produzca una string vacía. 

Para eliminar producciones nulas, primero tenemos que encontrar todas las variables anulables. Una variable ‘A’ se denomina anulable si λ se puede derivar de ‘A’. Para todas las producciones de tipo ‘A -> λ’, ‘A’ es una variable anulable. Para todas las producciones de tipo ‘B -> A1A2…An’, donde todas las ‘Ai’ son variables anulables, ‘B’ también es una variable anulable. 

Después de encontrar todas las variables anulables, ahora podemos comenzar a construir la gramática libre de producción nula. Para todas las producciones en la gramática original, agregamos la producción original así como todas las combinaciones de la producción que se pueden formar reemplazando las variables anulables en la producción por λ. Si todas las variables en el RHS de la producción son anulables, entonces no agregamos ‘A -> λ’ a la nueva gramática. Un ejemplo aclarará el punto. Considere la gramática – 
 

S -> ABCd                        (1)
A -> BC                                (2)
B -> bB | λ                        (3)    
C -> cC | λ                        (4)    

Primero busquemos todas las variables anulables. Las variables ‘B’ y ‘C’ son claramente anulables porque contienen ‘λ’ en el RHS de su producción. La variable ‘A’ también admite valores NULL porque en (2), ambas variables en el RHS también admiten valores NULL. Del mismo modo, la variable ‘S’ también admite valores NULL. Entonces, las variables ‘S’, ‘A’, ‘B’ y ‘C’ son variables anulables. 

Vamos a crear la nueva gramática. Empezamos con la primera producción. Agregue la primera producción tal como está. Luego creamos todas las combinaciones posibles que se pueden formar reemplazando las variables anulables con λ. Por lo tanto, la línea (1) ahora se convierte en ‘S -> ABCd | ABd | ACd | BCd | Anuncio | Bd | Cd | d ‘. Aplicamos la misma regla a la línea (2) pero no agregamos ‘A -> λ’ a pesar de que es una combinación posible. Eliminamos todas las producciones de tipo ‘V -> λ’. La nueva gramática ahora se convierte en: 
 

S -> ABCd | ABd | ACd | BCd | Ad  |  Bd  |Cd | d
A -> BC | B | C
B -> bB | b
C -> cC | c

3. Producciones unitarias – Las producciones de tipo ‘A -> B’ se denominan producciones unitarias. 
Para crear una gramática libre de producción unitaria ‘Guf’ a partir de la gramática original ‘G’, seguimos el procedimiento mencionado a continuación. 

Primero agregue todas las producciones no unitarias de ‘G’ en ‘Guf’. Luego, para cada variable ‘A’ en la gramática ‘G’, encuentre todas las variables ‘B’ tales que ‘A *=> B’. Ahora, para todas las variables como ‘A’ y ‘B’, agregue ‘A -> x1 | x2 | …xn’ a ‘Guf’ donde ‘B -> x1 | x2 | …xn ‘ está en ‘Guf’ . Ninguno de los x1 , x2 … xn son variables individuales porque solo agregamos producciones no unitarias en ‘Guf’. Por lo tanto, la gramática resultante está libre de producción de unidades. Por ej. 
 

S -> Aa | B
A -> b | B
B -> A | a

Agreguemos todas las producciones no unitarias de ‘G’ en ‘Guf’. ‘Guf’ ahora se convierte en – 
 

S -> Aa
A -> b
B -> a

Ahora encontramos todas las variables que satisfacen ‘X *=> Z’. Estos son ‘S*=>B’, ‘A *=> B’ y ‘B *=> A’. Para ‘A *=> B’, agregamos ‘A -> a’ porque ‘B ->a’ existe en ‘Guf’. ‘Guf’ ahora se convierte en 
 

    
S -> Aa
A -> b | a
B -> a

Para ‘B *=> A’, agregamos ‘B -> b’ porque ‘A -> b’ existe en ‘Guf’. La nueva gramática ahora se convierte en 
 

S -> Aa
A -> b | a
B -> a | b

Seguimos el mismo paso para ‘S*=>B’ y finalmente obtenemos la siguiente gramática: 
 

S -> Aa | b | a
A -> b | a
B -> a | b

Ahora elimine B -> a|b , ya que no ocurre en la producción ‘S’, entonces la siguiente gramática se convierte en,

S->Aa|b|a
A->b|a

Nota: Para eliminar todo tipo de producciones mencionadas anteriormente, primero elimine las producciones nulas, luego las producciones unitarias y finalmente, elimine las producciones inútiles. Seguir este orden es muy importante para obtener el resultado correcto. 

Este artículo es una contribución de Nitish Joshi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.