Usuario:Escaldon/Eliminación de producciones vacías

Una producción gramatical es vacía si es de la forma A$\rightarrow \epsilon$. Modificaremos la gramática para eliminar este tipo de producciones sin cambiar el lenguaje generado por la gramática. Si $\epsilon \in$ L(G) no podremos eliminar todas las producciones vacías, de modo que en este caso dejaremos como única producción vacía: $S\rightarrow \epsilon$. Un símbolo $A\in V$ se dice que es anulable si $A\Rightarrow ^{*}\epsilon$. El siguiente algoritmo permite el cálculo de todos los símbolos anulables de una gramática.

Algoritmo

H = $\emptyset$;
forall (Producción de la forma A $\rightarrow \epsilon$) do
  $\mid$  H = H $\cup$ {A};
end
while (H cambie) do
  $\mid$  forall (Producción B$\rightarrow A_{1}A_{2}...A_{n}$ donde $A_{i}\in H\,\forall _{i}=1,2,...n$) do)
  $\mid$     $\mid$   H = H $\cup${B};
  $\mid$   end
end

Una vez calculado el conjunto de símbolos anulables, permite la eliminación de las producciones vacías de la gramática con el siguiente algoritmo:

Eliminar todas las producciones vacías (A $\rightarrow \epsilon$)
forall (Producción de la forma A $\rightarrow X_{1}X_{2}...X_{n}(X_{i}\in (\Sigma \cup$ V)) do
  $\mid$     Eliminar la producción A $\rightarrow X_{1}X_{2}...X_{n}$;
  $\mid$     Añadir todas las producciones A $\rightarrow Y_{1}Y_{2}...Y_{n}$;
  $\mid$     Donde:$Y_{i}=X_{i}$ si $X_{i}$ es no anulable;
  $\mid$     ($Y_{i}=X_{i}$)$\vee$($Y_{i}=\epsilon$) si $X_{i}$ es anulable;
  $\mid$     $Y_{i}$ no es $\epsilon \;\forall _{i}$(no se introducen producciones vacías);
end

Ejemplos

Apliquemos el algoritmo de elmininación de producciones vacías a la siguiente gramática:

$S\rightarrow aA$
$A\rightarrow aA\vert \epsilon$

El resultado que se obtiene es:

$S\rightarrow aA\vert a$
$A\rightarrow aA\vert a$

Se ha eliminado la única producción vacía: $A\rightarrow \epsilon$ . Apliquémoslo a esta otra gramática:

$S\rightarrow ABb\vert ABC$
$A\rightarrow aA\vert \epsilon$
$B\rightarrow bB\vert \epsilon$
$C\rightarrow abC\vert AB$

El resultado que se obtiene es:

$S\rightarrow \epsilon \vert ABb\vert Ab\vert Bb\vert b$
$S\rightarrow ABC\vert AB\vert AC\vert BC\vert A\vert B\vert C$
$A\rightarrow aA\vert a$
$B\rightarrow bB\vert b$
$C\rightarrow abC\vert ab\vert AB\vert A\vert B$

Referencias

• Kelley, Dean (1995). Teoría de Autómatas y Lenguajes Formales. Prentice Hall. ISBN 0-13-518705-2.