Chomskyjev normalni oblik
U računarstvu, formalna gramatika je u Chomskyjevom normalnom obliku ako i samo ako ima sve produkcije u obliku:
- A → BC 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.
Sa 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
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:
- A → BC 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 ukoliko je izvorna gramatika generirala ε
Vidjeti također
Izvori
- 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.