# 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:
    $A\rightarrow BC$
    $A\rightarrow \alpha$
on $\alpha$ é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:
    $S\rightarrow \varepsilon$
on S és la variable inicial i $\varepsilon$ la paraula buida (també pot estar representada per λ), aquesta última regla només pot aparèixer si $\varepsilon$ é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 S$_0$, i una nova regla:
    S$_0$ → S,
On S és el símbol inicial anterior. Això no canvia el llenguatge produït per la gramàtica, i S$_0$ no apareixerà a cap costat dret de cap regla.

### TERM: Eliminar regles amb terminals no solitaris

Per eliminar tota regla del tipus:
    A → X$_1$ ... a ... X$_n$
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 N$_a$ i una nova regla:
    N$_a$ → a.
I es canvia cada regla
    A → X$_1$ ... a ... X$_n$
per
    A → X$_1$ ... N$_a$ ... X$_n$.
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:
    A → X$_1$ X₂ ... X$_n$
amb més de 2 no terminals X$_1$,...,X$_n$ per regles:
    A → X$_1$ A$_1$,
    A$_1$ → X₂ A₂,
    A$_{n-2}$ → X$_{n-1}$ X$_n$,
on A$_i$ 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 S$_0$, 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 → X$_1$ ... X$_n$ existeix, i cada símbol X$_i$ és nullable, llavors A també és nullable.
S'obté una gramàtica intermedia reemplaçant cada regla
    A → X$_1$ ... X$_n$
per totes les versions amb alguns símbóls X$_j$ 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 S$_0$:
    S$_0$ → AbB | C
    B → AA | AC
    C → b | c
    A → a | ε
El símbol no terminal A i, per tant, també B, és nullable, mentre que ni C ni S$_0$ ho son. Per tant, s'obté una gramàtica intermedia:
    S$_0$ → AbB | AbB | AbB | AbB | C
    B → AA | AA | AA | AεA | AC | AC
    C → b | c
    A → a | ε
En aquesta gramàtica, totes les regles ε s'han fet inline. Al següent pas, es poden esborrar, deixant la gramàtica:
    S$_0$ → AbB | Ab | bB | b | C
    B → AA | A | AC | C
    C → b | c
    A → a
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
    A → B,
on A, B son símbols no terminals. Per esborra-la, per cada regla
    B → X$_1$ ... X$_n$,
on X$_1$ ... X$_n$ és una cadena de símbols terminals i no terminals, s'afegeix la regla
    A → X$_1$ ... X$_n$
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.
Preservació mútua dels resultats :
| Transformació X sempre preserva (1) idem. pot destruir (2) el resultat d'Y: ||||||
| $_X$\$^Y$ | START | TERM | BIN | DEL | UNIT |
| START | | 1 | 1 | 2 | 2 |
| TERM | 1 | | 2 | 1 | 1 |
| BIN | 1 | 1 | | 1 | 1 |
| DEL | 1 | 1 | 1 | | 2 |
| UNIT | 1 | 1 | 1 | (1)$^*$ | |
| $^*$UNIT preserva el resultat de DEL si s'ha cridat START prèviament. ||||||
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|² o 2$^{2|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 són les que incrementen la mida en menor mesura (quadràtica).

## Exemple

La següent gramàtica, que comença amb el símbol Expr, descriu una versió simplificada del conjunt d'operacions aritmètiques en un llenguatge de programació tipus C o Algol60. Tant number com variable es consideren símbols terminals per simplicitat. El símbol terminal "^" vol dir exponent en Algol60.
    Expr → Term | Expr AddOp Term | AddOp Term Term → Factor | Term MulOp Factor Factor → Primary | Factor ^ Primary Primary → number | variable | (Expr) AddOp → + | − MulOp → * | /
El primer pas de l'algorisme per convertir la gramàtica a una forma normal (pas 'START') s'afegeix una regla del tipus S$_0$→Expr. Després del pas 'TERM' la gramàtica es veu així:
    S$_0$ → Expr Expr → Term | Expr AddOp Term | AddOp Term Term → Factor | Term MulOp Factor Factor → Primary | Factor PowOp Primary Primary → number | variable | Open Expr Close AddOp → + | − MulOp → * | / PowOp → ^ Open → ( Close →)
Després del pas "BIN", s'obté la següent gramàtica:
    S$_0$ → Expr Expr → Term | Expr AddOp_Term | AddOp Term Term → Factor | Term MulOp_Factor Factor → Primary | Factor PowOp_Primary Primary → number | variable | Open Expr_Close AddOp → + | − MulOp → * | / PowOp → ^ Open → ( Close →) AddOp_Term → AddOp Term MulOp_Factor → MulOp Factor PowOp_Primary → PowOp Primary Expr_Close → Expr Close
Com que la gramàtica no té cap regla ε, el pas "DEL" no canvia la gramàtica. Després del pas "UNIT", la gramàtica ja està en forma normal:
    S$_0$ → number | variable | Open Expr_Close | Factor PowOp_Primary | Term MulOp_Factor | Expr AddOp_Term | AddOp Term Expr → number | variable | Open Expr_Close | Factor PowOp_Primary | Term MulOp_Factor | Expr AddOp_Term | AddOp Term Term → number | variable | Open Expr_Close | Factor PowOp_Primary | Term MulOp_Factor Factor → number | variable | Open Expr_Close | Factor PowOp_Primary Primary → number | variable | Open Expr_Close AddOp → + | − MulOp → * | / PowOp → ^ Open → ( Close →) AddOp_Term → AddOp Term MulOp_Factor → MulOp Factor PowOp_Primary → PowOp Primary Expr_Close → Expr Close
Els N$_a$ introduïts al pas "TERM" son PowOp, Open, and Close. Els A$_i$ introduïts al pas "BIN" son AddOp_Term, MulOp_Factor, PowOp_Primary, i Expr_Close.

## Definicions alternatives
### Forma reduïda de Chomsky

Una altra forma de definir una forma normal de Chomsky és:
Una gramàtica formal està en forma reduïda de Chomsky si totes les seves regles son de la forma:
    $A\rightarrow \,BC$ or
    $A\rightarrow \,a$,
on $A$, $B$ i $C$ son símbols no terminals i $a$ és un símbol terminal. Usant aquesta definició, $B$ o $C$ poden ser el símbol d'inici. Només les gramàtiques lliures del context que no generen la cadena buida poden ser transformades a la forma reduïda de Chomsky.

### Forma normal de Floyd

En l'article on es proposava el terme Backus-Naur form (BNF), Donald E. Knuth afirma que una BNF és una "sintaxi on totes les definicions tenen una forma que es pot dir 'Forma normal de Floyd'"
    $\langle A\rangle ::=\,\langle B\rangle \mid \langle C\rangle$ o
    $\langle A\rangle ::=\,\langle B\rangle \langle C\rangle$ o
    $\langle A\rangle ::=\,a$,
on $\langle A\rangle$, $\langle B\rangle$ i $\langle C\rangle$ son símbols no terminals i $a$ és un símbol terminal, perquè Robert W. Floyd va descobrir que qualsevol sintaxi BNF es pot convertir a l'anterior el 1961. But he withdrew this term, "since doubtless many people have independently used this simple fact in their own work, and the point is only incidental to the main considerations of Floyd's note".

## Vegeu també

* Jerarquia de Chomsky
* Forma de Backus i naur
* Algorisme CYK

## Bibliografia

* Sipser, Michael. Introduction to the Theory of Computation. ISBN 978-0-619-21764-8.

## Referències

* ↑ Chomsky, Noam «On certain formal properties of grammars». Information and Control, 2, 2, pàg. 137–167. DOI: 10.1016/s0019-9958(59)90362-6.
* 1 2 1939-, Hopcroft, John E.,. Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley, 1979. ISBN 020102988X.
* ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
* 1 2 Knuth, Donald E. «Backus Normal Form vs. Backus Naur Form». Commun. ACM, 7, 12, 12-1964, pàg. 735–736. DOI: 10.1145/355588.365140. ISSN: 0001-0782.