028 - GIC - Forma Normal de Chomsky

Forma Normal de Chomsky

FNC

Ing. Maicol García

Que es una FNC

A las GIC (Gramaticas Independientes del Contexto), se les puede escribir en Forma Normal de Chomsky para optimizar la Gramatica y para ello se deben deben ser libres de ε. L(G1C) = L(GIC) - {ε}

Forma Normal de Chomsky (FNC)

Simplificaciones a realizar:

Tenemos que eliminar las producciones-ε, aquellas de la forma A -> ε para alguna variable A.

Tenemos que eliminar las producciones unitarias, aquellas de la forma A -> B para A y B

Tenemos que eliminar los símbolos inutiles, aquellas variables o símbolos No-terminales que no aparecen en ninguna derivación de una cadena terminal que parta del símbolo inicial.

Convertir producciones en una de las dos formas siguientes:

1. A -> BC, donde A, B y C son Variables o
2. B -> b , donde B es una variable y b es un terminal.

1- Quitar las Producciones-ε

Las producciones-ε no generan nada para G. Por tanto, las siguientes producciones constituyen G.

Eliminamos Epsilon(ε) , para ello reemplazamos ε: ninguna, una y muchas veces dependiendo las producciones para las no Terminales A y B.

SOLUCION: GIC Simple:

Ejemplo#1 GIC Simple: S -> AB A -> aAA B -> bBB A -> ε B -> ε

B -> ε

A -> ε

S -> AB | A | B A -> aAA | aA | a B -> bBB | bB | b

S -> AB | A | B A -> aAA | aA | a B -> bBB | bB | b

A -> ε

AA -> εε

B -> ε

BB -> εε

2- Eliminar las Producciones Unitarias

Una producción Unitaria es una producción de la forma A ->B, donde A y B son No terminales.

Determinar en primer lugar, todos aquellos pares de variables A y B donde A -> B, utlizando solo una secuencia de Producciones unitarias.

Ejemplo#1 GIC Simple: S -> AB S -> aAA S -> aA S -> a S -> bBB S -> bB S -> b A -> aAA | aA | a B -> bBB | bB | b

Reemplaza , las reglas de producción de A en asignaciones de la manera : S -> A o B -> A

Ejemplo#1 GIC Simple: S -> AB | A | B A -> aAA | aA | a B -> bBB | bB | b

3-Eliminar Simbolos Inutiles

El método para eliminar los símbolos inútiles identifica las dos cosas que un símbolo tienen que cumplir para resultar util:

Decimos que X es un generador si X -> w, para alguna cadena terminal w. Todo símbolo No terminal es generador. SI una produccion puede convertirse en una terminal.

Decimos que X es Alcanzable si existe una derivación S-> aXc para algúna X, tal que sea alcanzable desde cualquier ruta empezando en el simbolo inicial.

Simbolos Inútiles: son simbolos que no son generadores o alcanzables.

Si eliminamos los símbolos que no son generadores en primer lugar y luego eliminamos los que no son alcanzables, tendremos sólo los símbolos útiles.

3-Eliminar Simbolos Inutiles

CORRECTO

ELIMINAMOS NO ALCANZABLES

ELIMINAMOS NO GENERADORES

SOLUCION GIC Simple: S -> a

Ejemplo#1 GIC Simple: S -> AB S -> a A -> b

SOLUCION GIC Simple: S -> a A -> b

INCORRECTO

ELIMINAMOS NO GENERADORES

ELIMINAMOS NO ALCANZABLES

Ejemplo#1 GIC Simple: S -> AB S -> a A -> b

SOLUCION GIC Simple: S -> a A -> b

SOLUCION GIC Simple: S -> AB S -> a A -> b

4- Convertir a FNC

Una producción de FNC es una ´produccion de la forma siguiente:

Convertir, Todas las producción a la forma Normal de Chomsky: A -> BC A -> a

Solución GIC Simple: E -> AA C -> a S -> AB B -> CE A -> b

Solucion GIC Simple: C -> a S -> AB B -> CAA A -> b

Ejemplo#1 GIC Simple: S -> AB B -> aAA A -> b

EJEMPLO #1 CONVIERTA LA SIGUIENTE GIC a FNC

Convertir: C -> 0 D -> 1 E -> 2 F -> DB G -> AD H -> AF S -> CH S -> CF A -> CG A -> CD B -> EB B -> 2

Convertir: C -> 0 D -> 1 E -> 2 F -> DB G -> AD S -> CAF | CF A -> CG | CD B -> EB B -> 2

Convertir: C -> 0 D -> 1 E -> 2 S -> CADB | CDB A -> CAD | CD B -> EB B -> 2

Inutiles: S -> 0A1B | 01B A -> 0A1 | 01 B -> 2B B -> 2

Prod ɛ: S -> 0A1B | 01B A -> 0A1 | 01 B -> 2B B -> 2

GIC: S -> 0A1B A -> 0A1 A -> ɛ B -> 2B B -> 2

Prod Unit: S -> 0A1B | 01B A -> 0A1 | 01 B -> 2B B -> 2

EJEMPLO #2 CONVIERTA LA SIGUIENTE GIC a FNC

Convertir: C -> a D -> b E -> SB F -> AD G -> BC S -> AE S -> SB S -> AB A -> CF A -> CD B -> DG B -> DC

Convertir: C -> a D -> b E -> SB F -> AD G -> BC S -> AE | SB | AB A -> CF | CD B -> DG | DC

NO SE PUEDE PORQUE ACEPTA EPSILON

Convertir: C -> a D -> b S -> ASB | SB | AB A -> CAD | CD B -> DBC | DC

Inutiles: S -> ASB | SB | AB A -> aAb | ab B -> bBa | ba

Prod Unit: S -> ASB | SB | AB A -> aAb | ab B -> bBa | ba

Prod ɛ: S -> ASB | SB | AB A -> aAb | ab B -> bBa | ba

GIC: S -> ASB | ɛ A -> aAb | ɛ B -> bBa | ba

EJERCICIOS CONVIERTA LA SIGUIENTE GIC a FNC

GIC#3 S -> A | B A -> aB | bS | b B -> AB | Ba | CC C -> AS | b | ε

GIC#2 S -> b | bHF | bH | bF H -> bHc | bc G -> dG | d F -> dFe | de | G

GIC#1: S -> ASB | ɛ A -> aA | ɛ B -> bB | ɛ

¡GRACIAS!