Forma normal de Chomsky

De Viquipèdia
Salta a: navegació, cerca

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[modifica]

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.[modifica]

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[modifica]

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[modifica]

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 ε[modifica]

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[modifica]

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[modifica]

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).

Exemple[modifica]

Arbre sintàctic abstracte de l'expressió aritmètica "a^2+4*b". La gramàtica d'exemple (a dalt) i la seva forma normal de Chomsky (a baix)

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 S0Expr. Després del pas 'TERM' la gramàtica es veu així:

S0 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:

S0 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:

S0 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 Na introduïts al pas "TERM" son PowOp, Open, and Close. Els Ai introduïts al pas "BIN" son AddOp_Term, MulOp_Factor, PowOp_Primary, i Expr_Close.

Definicions alternatives[modifica]

Forma reduïda de Chomsky[modifica]

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:

or
,

on , i son símbols no terminals i és un símbol terminal. Usant aquesta definició, o 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[modifica]

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]

o
o
,

on , i son símbols no terminals i é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é[modifica]

Bibliografia[modifica]

Referències[modifica]

  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.
  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. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  4. 4,0 4,1 Knuth, Donald E. «Backus Normal Form vs. Backus Naur Form». Commun. ACM, 7, 12, desembre 1964, pàg. 735–736. DOI: 10.1145/355588.365140. ISSN: 0001-0782.