Post on 26-Jun-2015
PRODUCCIONES VACIASPRODUCCIONES VACIASLas producciones vacías, A λ en una gramática sólo son útiles en el caso de generar la cadena vacía.
En el resto de derivaciones de una gramática incontextual, este tipo de producciones provocan el efecto de alargar innecesariamente el número de pasos de derivación necesarios para generar cualquier cadena distinta de la vacía. Es por eso, por lo que interesa eliminar el conjunto de producciones
vacías de una gramática sin perder su capacidad generativa, con la excepción de la cadena vacía.
Para la eliminación de las producciones vacías se debe calcular en primer lugar el conjunto de símbolos anulables, es decir, símbolos que, en uno o más
pasos de derivación, son capaces de generar la cadena vacía. El siguiente algoritmo, proporciona un esquema de cálculo de los símbolos anulables de
una gramática.
Producciones VacíasProducciones VacíasSi λ ∈ L(G) entonces no se pueden eliminar todas las λ-producciones de G. Por el contrario, si λ∉L(G) entonces sí se pueden eliminar todas las λ-producciones de G.
Símbolos anulables. Un símbolo no terminal A es anulable ⇔A⇒*λ•Si A→ λ es una producción, entonces A es anulable.•Si A→ α es una producción y todos los símbolos de α son anulables, entonces A es anulable.
Eliminar λ-producciones o producciones vacías
Ejemplo. Dadas las producciones S→AbC A→a | λ C→c | λ, entonces A y C son anulables.
Producciones vacíasProducciones vacías
Teorema. Si L(G) es generada por una GLC G, entonces L(G)-{λ} es generada por una GLC G’ sin símbolos inútiles ni λ-producciones.
Eliminar λ-producciones: Algoritmo1. Determinar los símbolos anulables.2. Incluir en P’ todas las producciones de P menos las λ-producciones3. Si A→ αBβ está en P’ y B es anulable, entonces se añade a P’ la regla A→ αβ ( excepto si A→ αβ es una λ-producción).4. Repetir 3. hasta que no se puedan añadir más Producciones
Producciones VacíasProducciones VacíasEliminar λ-producciones: Ejemplos
Encontrar la gramática equivalente sin λ-producciones.S→0A
A→10A| λ
Encontrar la gramática equivalente sin λ-producciones.S→0A
A→10AB| λB→ BAB | 1
PRODUCCIONES UNARIASPRODUCCIONES UNARIASLas producciones unitarias en las gramáticas incontextuales, A B, provocan el efecto de aumentar el número de pasos de derivación en la generación de las cadenas de la misma. Es por ello que su eliminación resulta interesante.
Para realizar la eliminación de producciones unitarias, en primer lugar hay que realizar el cálculo de la alcanzabilidad de tales producciones a partir de un símbolo auxiliar dado.
Producciones Unidad
Las producciones unidad o reglas de redenominación son producciones de la forma:
A→B
es decir, la parte derecha es un único símbolo no terminal.
PRODUCCIONES UNITARIASPRODUCCIONES UNITARIASAlgoritmo para eliminar Producciones Unidad.
1. Eliminar λ-producciones2. Para toda producción unidad A→B, con
B → α1 | α2 |... | αn sustituir A→B porA → α1 | α2 |... | αn
3. Repetir 2. mientras queden producciones unidad
Eliminar producciones unidad: EjemplosEncontrar la gramática equivalente sin producciones unidad.S→Cbh | DA→aaCB→Sf | gggC→cA | d | CD→E | SABCE→be