Simplificación CFG
En un CFG, puede suceder que no se necesiten todas las reglas y símbolos de producción para la derivación de cadenas. Además, puede haber algunas producciones nulas y producciones unitarias. La eliminación de estas producciones y símbolos se llamasimplification of CFGs. La simplificación se compone esencialmente de los siguientes pasos:
- Reducción de CFG
- Eliminación de unidades de producción
- Eliminación de producciones nulas
Reducción de CFG
Los CFG se reducen en dos fases:
Phase 1 - Derivación de una gramática equivalente, G’, del CFG, G, de modo que cada variable derive alguna cadena terminal.
Derivation Procedure -
Paso 1: incluya todos los símbolos, W1, que derivan algún terminal e inicializan i=1.
Paso 2: incluye todos los símbolos, Wi+1, que derivan Wi.
Paso 3 - Incremento i y repita el Paso 2, hasta Wi+1 = Wi.
Paso 4: incluya todas las reglas de producción que Wi en eso.
Phase 2 - Derivación de una gramática equivalente, G”, del CFG, G’, de modo que cada símbolo aparece en forma de oración.
Derivation Procedure -
Paso 1: incluya el símbolo de inicio en Y1 e inicializar i = 1.
Paso 2: incluye todos los símbolos, Yi+1, que se puede derivar de Yi e incluir todas las reglas de producción que se hayan aplicado.
Paso 3 - Incremento i y repita el Paso 2, hasta Yi+1 = Yi.
Problema
Encuentre una gramática reducida equivalente a la gramática G, que tenga reglas de producción, P: S → AC | B, A → a, C → c | BC, E → aA | mi
Solución
Phase 1 -
T = {a, c, e}
W 1 = {A, C, E} de las reglas A → a, C → cy E → aA
W 2 = {A, C, E} U {S} de la regla S → AC
W 3 = {A, C, E, S} U ∅
Dado que W 2 = W 3 , podemos derivar G 'como -
G '= {{A, C, E, S}, {a, c, e}, P, {S}}
donde P: S → AC, A → a, C → c, E → aA | mi
Phase 2 -
Y 1 = {S}
Y 2 = {S, A, C} de la regla S → AC
Y 3 = {S, A, C, a, c} de las reglas A → a y C → c
Y 4 = {S, A, C, a, c}
Dado que Y 3 = Y 4 , podemos derivar G ”como -
G ”= {{A, C, S}, {a, c}, P, {S}}
donde P: S → AC, A → a, C → c
Eliminación de unidades de producción
Cualquier regla de producción en la forma A → B donde A, B ∈ No terminal se llama unit production..
Procedimiento de remoción -
Step 1 - Para eliminar A → B, agregar producción A → x a la regla gramatical siempre que B → xocurre en la gramática. [x ∈ Terminal, x puede ser nulo]
Step 2 - eliminar A → B de la gramática.
Step 3 - Repita desde el paso 1 hasta eliminar todas las unidades de producción.
Problem
Elimine la producción unitaria de lo siguiente:
S → XY, X → a, Y → Z | b, Z → M, M → N, N → a
Solution -
Hay 3 unidades de producción en la gramática:
Y → Z, Z → M y M → N
At first, we will remove M → N.
Como N → a, agregamos M → a, y M → N se elimina.
El conjunto de producción se convierte
S → XY, X → a, Y → Z | b, Z → M, M → a, N → a
Now we will remove Z → M.
Como M → a, agregamos Z → a, y Z → M se elimina.
El conjunto de producción se convierte
S → XY, X → a, Y → Z | b, Z → a, M → a, N → a
Now we will remove Y → Z.
Como Z → a, agregamos Y → a, y Y → Z se elimina.
El conjunto de producción se convierte
S → XY, X → a, Y → a | b, Z → a, M → a, N → a
Ahora Z, M y N son inalcanzables, por lo tanto, podemos eliminarlos.
El CFG final está libre de producción unitaria -
S → XY, X → a, Y → a | segundo
Eliminación de producciones nulas
En un CFG, un símbolo no terminal ‘A’ es una variable que acepta valores NULL si hay una producción A → ε o hay una derivación que comienza en A y finalmente termina con
ε: A → .......… → ε
Procedimiento de remoción
Step 1 - Descubra las variables no terminales que aceptan valores NULL que derivan ε.
Step 2 - Para cada producción A → a, construye todas las producciones A → x dónde x se obtiene de ‘a’ quitando uno o varios no terminales del Paso 1.
Step 3 - Combinar las producciones originales con el resultado del paso 2 y eliminar ε - productions.
Problem
Elimine la producción nula de lo siguiente:
S → ASA | aB | b, A → B, B → b | ∈
Solution -
Hay dos variables que aceptan valores NULL: A y B
At first, we will remove B → ε.
Después de quitar B → ε, el conjunto de producción se convierte en -
S → ASA | aB | b | a, A ε B | b | & épsilon, B → b
Now we will remove A → ε.
Después de quitar A → ε, el conjunto de producción se convierte en -
S → ASA | aB | b | a | SA | AS | S, A → B | b, B → b
Este es el conjunto de producción final sin transición nula.