Métodos de Simplificación de Gramáticas y Conversión a Forma Normal de Chomsky (FNC)

B)Eliminación DE Símbolos NO ACCESIBLES:

1) Inicializar N' = {s} ,       =       , P' =       
2) Repetir: para A € N', si A--> es una producción de P, entonces:

2.1)

Introducir A-->w en P' 2.2)
Para todo no terminal
B d w, introducir B en N' 2.3)
Para todo terminal        d w, introducir        en         hasta q no se puedan añadir + reglas a P'.

C) Eliminación DE REGLAS - EPSYLON:

 G= (N,      , P,S) tal que       € L(G) ; S-->      (esta no se elimina) el resto d reglas epsylon se podrán eliminar:

Símbolo anulable:

A € N es anulable si A =^*>       ; //
1)El conjunto d símbolos anulables de una gramática (      ) se calcla:

1.1)

Inicializamos        con todos los no terminales
A tal q A-->      € P 1.2)
Repetir: añadir a        tos los no terminales B tal q B --> w € P y todos los símbolos d w están en        hasta q no se puedan añadir + no terminales a      
2) Modificamos las reglas d P como sigue: sea B --> x₁x₂...X_n €P, introducimos en P' todas las siguientes producciones:
B--> y₁y₂...Y_n tal q y_i = x_i si x_i no es anulable, x_i o       si x_i SI es anulable, x_i no puede ser       para todo i • NOTA: si       € L(G) al final añadimos S-->      

D)Eliminación D REGLAS UNITARIAS:

(A(no terminal) --> B(no terminal)): para cada A € N, unitario (A) = {B € N / A =*> B usando solo reglas unitarias}. Calculamos P':
1) Inicializar P' = P
2) Para todo A € N, obtener unitario(A)
3) Para todo A € N tal q unitario(A) distinto de {A}: para tpdp B €unitario(A): para todo B-->w € P, añadir A-->w a P'
4) Eliminar las reglas unitarias de P'

• 1º aplicar elminacion epsylon, luego unitaria y luego A) y B)

3.6 FORMA NORMAL DE CHOMSKY:

 diremos q una gramática esta en forma normal d chomsky cuando todas las reglas sean d la forma: A--> a o A--> BC • ¿Como paso de una gramática arbitraria limpia G (sin reglas epsylon ni reglas unitarias ni símbolos inútiles ni símbolos inaccesibles) a otra G'? --> Para cada regla d la gramática se hace (en caso de épsilon formar parte de S, la quitamos y trabajamos sin ella, al final la volvemos a poner): A --> w tal q |w|>=1 1a)
|w|=1 (w solo tiene un símbolo:
Necesariamente w es un terminal (pq esta limpa), la regla se deja, ya esta en FN 1b)
|w|>1, A--> x₁,x₂...,x_n1b.1)
si x_i es un no terminal, no se toca 1b.2)
si x_i es el terminal       , lo cambiamos por un no terminal        y añadimos la regla       -->       
2) Binarizamos la regla: A-->B₁D₁ ; D₁-->B₂D₂......D_n-2-->B_n-1B_n
3) Al final si       € L(G) añadimos la regla S-->      .