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]

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₀, i una nova regla:

S₀ → S,

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

TERM: Eliminar regles amb terminals no solitaris

Per eliminar tota regla del tipus:

A → X₁ ... 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₁ ... a ... X_n

per

A → X₁ ... 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₁ X₂ ... X_n

amb més de 2 no terminals X₁,...,X_n per regles:

A → X₁ A₁,

A₁ → 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₀, 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₁ ... 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₁ ... 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₀:

S₀ → 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₀ ho son. Per tant, s'obté una gramàtica intermedia:

S₀ → 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₀ → 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₁ ... X_n,

on X₁ ... X_n és una cadena de símbols terminals i no terminals, s'afegeix la regla

A → X₁ ... 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₀→Expr. Després del pas 'TERM' la gramàtica es veu així:

S₀	→ 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₀	→ 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₀	→ 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:^[2]^[3]

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'" ^[4]

\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".^[4]

Vegeu també

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.
↑ ^2,0 ^2,1 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.
↑ ^4,0 ^4,1 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.

[1] 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] 2,0 ^2,1 1939-, Hopcroft, John E.,. Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley, 1979. ISBN 020102988X.

[3] Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.

[:0-4] 4,0 ^4,1 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.

[1]

[2]

[3]

[4]