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.
Para entender la eliminación de símbolos inútiles, es necesario entender qué se considera un símbolo útil:
Un símbolo se dice que es útil una derivación de la forma:
.
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:
;
para todo Producción de la forma hacer
;
mientras cambie hacer
para todo Producción de la forma hacer
si todos los no-terminales de entonces
;
Eliminar todas las variables que estén en y no en ;
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:
;
;
;
mientras hacer
Extraer un no terminal de : ;
para todo Producción de la forma hacer
Poner todos los terminales de en ;
para todo no-terminal en hacer
si entonces
;
;
Eliminar todos los no terminales que no estén en y todos los terminales que no estén en ;
Eliminar todas las producciones donde aparezca un símbolo o variable de los eliminados;
Algoritmo aplicado a un ejemplo concreto[editar]
Considérese la CFG siguiente:
Etapa 1:
Primer bucle; se analizan las 8 producciones, pero sólo se detiene en aquellas que generan un símbolo terminal:
;
;
Segunda estructura iterativa; ha cambiado, luego se entra dentro del bucle.
entonces:
No hay no-terminales que evaluar.
entonces:
No hay no-terminales que evaluar.
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:
y , luego será eliminada.
La producción será eliminada también.
La CFG tendrá el aspecto siguiente después de este primer paso:
Etapa 2:
;
;
;
Se entra al bucle;
El primer no terminal que se extrae es ;
Se analizan todas las producciones de :
No terminal en
No se actualiza
No terminal en
Se extrae un nuevo no-terminal:
Se analizan sus producciones:
No se actualiza
No terminal en
Ya está en
No terminal en
Ya está en
No se actualiza
No terminal en
Ya está en
Se extrae nuevamente un no terminal:
Se analiza su única producción:
No se actualiza
No hay no terminal en
Fin del bucle
Eliminamos los no terminales que no aparecen en , es decir: eliminamos
Eliminamos los terminales que no aparecen en , en este caso: eliminamos
La CFG después de la segunda etapa, y por tanto sin símbolos inútiles será como sigue:
Referencias[editar]