Prijeđi na sadržaj

Chomskyjev normalni oblik

Izvor: Wikipedija

U računarstvu, formalna gramatika je u Chomskyjevom normalnom obliku ako i samo ako ima sve produkcije u obliku:

ABC or
A → α or
S → ε

gdje su A, B i C nezavršni znakovi, α je završni znak (znak koji predstavlja konstantnu vrijednost), S je početni znak i ε je prazni niz. Također, ni B niti C ne smiju biti početni znakovi.

Svaka gramatika u Chomskyjevom normalno obliku je kontekstno neovisna, te sljedbeno tome, svaka kontekstno neovisna gramatika se može učinkovito svesti na istovjetnu gramatiku u Chomskyjevom normalnom obliku.

S iznimkom opcionalnog pravila S → ε (uključenog kad gramatika može generirati prazni niz), sva pravila gramatika u Chomskyjevom normalnom obliku su strogo ekspanzivna - prilikom prijelaza između međunizova za vrijeme geneiranja niza znakova, svaki međuniz završnih i nezavršnih znakova je uvijek ili iste duljine ili za jedan element veći od prethodnog međuniza. Generiranje niza znakova duljine n se uvijek obavlja u 2n-1 koraka. Štoviše, jer sve produkcije koje stvaraju nezavršne znakova transformiraju jedan nezavršni znak u točno dva nezavršna znaka, stablo parsiranja gramatike u Chomskyjevom normalnom obliku jest binarno stablo, a dubina ovog stabla ima gornju granicu jednaku duljini niza.

Zbog ovih svojstava, mnogi dokazi u području formalnih jezika i izračunljivosti koriste Chomskyjev normalni oblik. Ova svojstva mogu dovesti do raznih učinkovitih algoritama baziranih na gramatikama u Chomskyjevom normalnom obliku; npr. CYK algoritam koji odlučuje generira li dana gramatika dani niz znakova koristi Chomskyjev normalni oblik.

Chomskyjev normalni oblik je imenovan po Noamu Chomskyu, američkom jezikoslovacu, tvorcu Chomskyjeve hijerarhije.

Alternativne definicije

[uredi | uredi kôd]

Neki autori definiraju Chomskyjev normalni oblik na malo drugačiji način:

Formalna gramatika je u Chomskyjevom normalnom obliku ako i samo ako ima sve produkcije u obliku:

ABC or
A → α

gdje su A, B i C nezavršni znakovi, a α završni znak. Po ovoj definiciji B ili C mogu biti početni znakovi.

Ova se definicija razlikuje od prethodne u tom što unaprijed isključuje mogućnost da će gramatika generirati prazni niz, ε. Ostaje vrijedeće svojstvo da bilo koja kontekstno neovisna gramatika koja generira jezik L se može učinkovito svesti u gramatiku u Chomskyjevom normalnom obliku koja generira jezik L - {ε}. Principijelna prednost potonje definicije jest što kao posljedica dokazi mogu biti marginalno jednostavniji, jer svaki korak u generiranju međunizova nikad neće smanjiti duljinu rezultirajućeg međuniza. Nedostatak je, dakako, posebna pažnja koju treba posvetiti ako je izvorna gramatika generirala ε

Vidjeti također

[uredi | uredi kôd]

Izvori

[uredi | uredi kôd]
  • Michael Sipser. 1997. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Pages 98–101 of section 2.1: context-free grammars. Page 156.
  • John Martin. 2003. Introduction to Languages and the Theory of Computation. McGraw Hill. ISBN 0-07-232200-4 Pages 237–240 of section 6.6: simplified forms and normal forms.