Usuario:TooloTF/Eliminación de símbolos inútiles

La Eliminación de símbolos inútiles, es uno los procesos a ejecutar cuando se habla de Simplificación de gramáticas. En la primera etapa de este proceso, se eliminan los símbolos no terminales desde los que no se pueda llegar a una palabra de w y las producciones en las que aparezcan. En su última etapa, se eliminan aquellos símbolos no alcanzables desde el símbolo inicial (S), y las producciones en las que aparecen.

Algoritmo

Para entender la eliminación de símbolos inútiles, es necesario entender qué se considera un símbolo útil:

  Un símbolo $X\in (\Sigma \cup V)$ se dice que es útil $\Leftrightarrow \exists$ una derivación de la forma: 
  $S\Rightarrow ^{+}\alpha X\beta \Rightarrow ^{*}w\in \Sigma ^{*}$.

La eliminación de símbolos inútiles se lleva a cabo a través de un procedimiento en dos etapas:

• Los símbolos no terminales de los que no se puede derivar una cadena de terminales son identificados y borrados. Un pseudocódigo que describe esta etapa es:

  $V'=\emptyset$;
  para todo $($ Producción de la forma $A\rightarrow w)$ hacer
        $V'=V'\cup \{A\}$;
  mientras $(V'\$ cambie $)\$ hacer
        para todo $($ Producción de la forma $B\rightarrow \alpha )$ hacer
              si $($todos los no-terminales de $\alpha \in V')$ entonces
                    $V'=V'\cup \{B\}$;
  Eliminar todas las variables $(C\in V)\$ que estén en $V\$ y no en $V'\$;
  Eliminar todas las producciones donde aparezca una variable de las eliminadas en el paso anterior; 

• Los no terminales que no son alcanzables desde el símbolo de arranque o axioma son borrados. Este proceso puede ser descrito por el pseudocódigo que sigue:

  $J\ =\{S\}$;
  $V'\ =\{S\}$;
  $\Sigma '=\emptyset$;
  mientras $(J\neq \emptyset )$ hacer
     Extraer un no terminal $A\$ de $J\$: $J\ =J-\{A\}$;
     para todo $(\$Producción de la forma $A\ \rightarrow \alpha )$ hacer
        Poner todos los terminales de $\alpha \$ en $\Sigma '\$;
        para todo $(\$ no-terminal $B\$ en $\alpha \ )$ hacer
           si $(B\notin V')$ entonces
              $J=J\cup \{B\}$;
              $V'=V'\cup \{B\}$;
  Eliminar todos los no terminales que no estén en $V'\$ y todos los terminales que no estén en $\Sigma '\$;
  Eliminar todas las producciones donde aparezca un símbolo o variable de los eliminados;

Algoritmo aplicado a un ejemplo concreto

Considérese la CFG siguiente:

  $S\rightarrow Aa|B|D$
  $B\rightarrow b\$
  $A\rightarrow aA|bA|B$
  $C\rightarrow abd\$

Etapa 1:

  $V'=\emptyset$
  Primer bucle; se analizan las 8 producciones, pero sólo se detiene en aquellas que generan un símbolo terminal:
  $1.\$ $B\rightarrow b\$
     $V'=V'\cup \{B\}$;
  $2.\$ $C\rightarrow abd\$
     $V'=V'\cup \{C\}$;
  Segunda estructura iterativa; $V'\$ ha cambiado, luego se entra dentro del bucle.
     $1.\$ $S\rightarrow Aa\$ 
          $A\notin V'\$
     $2.\$ $S\rightarrow B\$
          $B\in V'$ entonces:
             $V'=V'\cup \{S\}$
     $3.\$ $S\rightarrow D\$
          $D\notin V'\$
     $4.\$ $B\rightarrow b\$
          No hay no-terminales que evaluar.
     $5.\$ $A\rightarrow aA\$
          $A\notin V'\$
     $6.\$ $A\rightarrow bA\$
          $A\notin V'\$
     $7.\$ $A\rightarrow B\$
          $B\in V'\$ entonces:
             $V'=V'\cup \{A\}$
     $8.\$ $C\rightarrow abd\$
          No hay no-terminales que evaluar.
     $V'\$ ha cambiado, pero no se producirán más cambios en las iteraciones siguientes del bucle
     "para todo", por lo que se sale del bucle "mientras".
  Finalmente:
     $V=\{S,A,B,C,D\}\$ y $V'=\{S,A,B,C\}\$, luego $D\$ será eliminada.
     La producción $S\rightarrow D\$ será eliminada también.

La CFG tendrá el aspecto siguiente después de este primer paso:

  $S\rightarrow Aa|B$
  $B\rightarrow b\$
  $A\rightarrow aA|bA|B$
  $C\rightarrow abd\$

Etapa 2:

  $J\ =\{S\}$;
  $V'\ =\{S\}$;
  $\Sigma '=\emptyset$;
  Se entra al bucle;
  El primer no terminal que se extrae es $S\$; $J=\emptyset$
     Se analizan todas las producciones de $S\$:
        $1.\$ $S\rightarrow Aa\$
             $\Sigma '=\Sigma '\cup \{a\}$
             No terminal en $\alpha =A\notin V'\$
                $J=\{A\}\$
                $V'=V'\cup \{A\}$
        $2.\$ $S\rightarrow B\$
             No se actualiza $\Sigma '\$
             No terminal en $\alpha =B\notin V'\$
                $J=J\cup \{B\}\$
                $V'=V'\cup \{B\}$
  Se extrae un nuevo no-terminal: $A\$
     Se analizan sus producciones:
         $1.\$ $A\rightarrow aA\$
             No se actualiza $\Sigma '\$
             No terminal en $\alpha =A\in V'\$
                Ya está en $V'\$
        $2.\$ $A\rightarrow bA\$
             $\Sigma '=\Sigma '\cup \{b\}$
             No terminal en $\alpha =A\in V'\$
                Ya está en $V'\$
        $3.\$ $A\rightarrow B\$
             No se actualiza $\Sigma '\$
             No terminal en $\alpha =A\in V'\$
                Ya está en $V'\$
  Se extrae nuevamente un no terminal: $B\$
     Se analiza su única producción:
        $1.\$ $B\rightarrow b\$
             No se actualiza $\Sigma '\$
             No hay no terminal en $\alpha \$
  Fin del bucle
  $V'=\{S,A,B\}\$
  $\Sigma '=\{a,b\}\$
  Eliminamos los no terminales que no aparecen en $V'\$, es decir: eliminamos $C\$
  Eliminamos los terminales que no aparecen en $\Sigma '\$, en este caso: eliminamos $d\$

La CFG después de la segunda etapa, y por tanto sin símbolos inútiles será como sigue:

  $S\rightarrow Aa|B\$
  $B\rightarrow b\$
  $A\rightarrow aA|bA|B\$

Referencias

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