Forma normal de Chomsky

En informàtica, una gramàtica lliure de context G es diu que està en la forma normal de Chomsky si totes les seves regles són de la forma: [1] [2]

on és qualsevol símbol terminal (un símbol que representa un valor constant) i A, B i C són símbols no terminals, B i C no poden ser el símbol inicial. També es permet la regla:

on S és la variable inicial i la paraula buida (també pot estar representada per λ), aquesta última regla només pot aparèixer si és a L(G), és a dir, el llenguatge produït per la gramàtica lliure del context G.

Tota gramàtica en forma normal de Chomsky és lliure del context, i per contra, tota gramàtica lliure del context es pot transformar en una equivalent en forma normal de Chomsky i té una mida menor al quadrat de la mida de la gramàtica original.

Convertir una gramàtica a la forma normal de Chomsky

Per convertir una gramàtica a la forma normal de Chomsky s'apliquen una sèrie de transformacions senzilles en un cert ordre i està descrit en forma llibres de text. La presentació següent segueix Hopcroft, Ullman (1979), però adaptada per usar els noms de Lange, Leiß (2009).

START: Eliminar el símbol d'inici de la part dreta.

S'introdueix un nou símbol S0, i una nova regla:

S0S,

On S és el símbol inicial anterior. Això no canvia el llenguatge produït per la gramàtica, i S0 no apareixerà a cap costat dret de cap regla.

TERM: Eliminar regles amb terminals no solitaris

Per eliminar tota regla del tipus:

AX1 ... a ... Xn

amb un símbol terminal a que no és l'únic a la part dreta, introdueix per cada terminal un nou símbol no terminal Na i una nova regla:

Naa.

I es canvia cada regla

AX1 ... a ... Xn

per

AX1 ... Na ... Xn.

Si hi ha molts símbols terminals a la part dreta, es canvien simultàniament cada un d'ells pel seu símbol no terminal associat. No canvia el llenguatge produït per la gramàtica.

BIN: Eliminar parts dretes amb més de 2 no-terminals

Es reemplaça cada regla:

AX1 X2 ... Xn

amb més de 2 no terminals X1,...,Xn per regles:

AX1 A1,
A1X2 A2,
... ,
An-2Xn-1 Xn,

on Ai son nous símbols no-terminals. De nou, la gramàtica produeix el mateix llenguatge.

DEL: Eliminar regles ε

Una regla ε és una regla del tipus:

A → ε,

on A no és S0, el símbol inicial de la gramàtica.

Per eliminar totes les regles d'aquesta mena primer es determina el conjunt de tots els símbols no terminals que deriven ε. Hopcroft and Ullman (1979) anomenen aquests no-terminals com nullable, i els cerquen de la següent manera:

  • Si una regla A → ε existeix, llavors A és nullable.
  • Si una regla A → X1 ... Xn existeix, i cada símbol Xi és nullable, llavors A també és nullable.

S'obté una gramàtica intermedia reemplaçant cada regla

AX1 ... Xn

per totes les versions amb alguns símbóls Xj nullable omesa. Esborrant d'aquesta gramàtica tota regla ε, excepte si a l'esquerra el seu símbol és el símbol d'inic, s'obté la gramàtica transformada.

Per exemple, a la següent gramàtica, amb un símbol d'inici S0:

S0AbB | C
BAA | AC
Cb | c
Aa | ε

El símbol no terminal A, i per tant també B, és nullable, mentre que ni C ni S0 ho son. Per tant, s'obté una gramàtica intermedia:

S0AbB | AbB | AbB | AbB   |   C
BAA | AA | AA | AεA   |   AC | AC
Cb | c
Aa | ε

En aquesta gramàtica, totes les regles ε s'han fet inline. Al següent pas, es poden esborrar, deixant la gramàtica:

S0AbB | Ab | bB | b   |   C
BAA | A   |   AC | C
Cb | c
Aa

Aquesta gramàtica produeixel mateix llenguatge que la gramàtica original: {ab,aba,abaa,abab,abac,abb,abc,b,bab,bac,bb,bc,c}, però aparentment no té regles ε.

UNIT: Eliminar regles unitàries

Una regla unitària és una regla del tipus

AB,

on A, B son símbols no terminals. Per esborra-la, per cada regla

BX1 ... Xn,

on X1 ... Xn és una cadena de símbols terminals i no terminals, s'afegeix la regla

AX1 ... Xn

a menys que sigui una regla unitària que ja s'hagi esborrat prèviament.

Ordre de les transformacions

Quan es tria l'ordre en que s'han d'aplicar les transformacions prèviament explicades, s'ha de considerar que algunes transformacions poden destruir els resultats obtinguts per algunes d'altres. Per exemple, START pot re-introduir regles unitàries si s'aplica després d'UNIT. La taula mostra quins ordres son admissibles.

D'altra banda, el pitjor cas d'inflar la mida de la gramàtica depèn de l'ordre de les transformacions. Usant |G| per indicar la mida de la gramàtica G original, la mida pot explotar fins a |G|2 o 22 |G| depenent de l'algorisme de transformació que s'usi. Aquest increment depèn bàsicament de l'ordre entre DEL i BIN. Pot ser exponencial quan s'aplica DEL primer, però és linear en altre cas. UNIT pot incrementar la mida de forma quadràtica. Els ordres START,TERM,BIN,DEL,UNIT i START,BIN,DEL,UNIT,TERM son les que incrementen la mida en menor mesura (quadràtica).

Altres idiomes