Simplificación de Gramáticas Independientes

Explique el funcionamiento del algoritmos de simplificación de gramáticas independientes. ?

Algoritmo para la simplificación de Gramáticas Independientes

• Eliminación símbolos inútiles
  1. Eliminación de símbolos no derivables
     • Un símbolo no terminal es derivable si del lado derecho de ese símbolo solo existen símbolos terminales $A\to a;a\in VT$ entonces $A$ es derivable.
     • Si todos los símbolos no terminales de la parte derecha de una producción son derivables o útiles, el símbolo no terminal de la parte izquierda lo es $B\to CcA$ si $A$ y $C$ son derivables entonces $B$ también lo es.
  2. Eliminación de los símbolos no alcanzables o inaccesibles.
     • Los símbolos accesibles son aquellos que se llegan a través de la producción de inicio. Los símbolos no alcanzables son símbolos (VT y VN) a los que no se llega a través del símbolo inicial.
     • El símbolo inicial siempre es accesible.
     • Si el símbolo no terminal del lado izquierdo es accesible, todos los símbolos (VN y VT) del lado derecho también lo son $S\to AcB$ y si $S$ es accesible entonces $A$, $c$ y $B$ son accesibles
• Eliminación de las producciones la palabra vacía
  • Las producciones nulas son aquellas producciones del tipo $A\to \lambda$
  • Los símbolos anulables son los que en uno o más pasos de derivación pueden generar la cadena vacía.
• Eliminación de las producciones unitarias
  • Son aquellas de la forma $A\to B$ para las variables $A$ y $B$

---

Flashcards