Chomskyjev normalni oblik - Wikipedia, slobodna enciklopedija

# Chomskyjev normalni oblik

### Sa Wikipedije, slobodne enciklopedije

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.

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

Svaka gramatika u Chomskyjevom normalno obliku je kontekstno nezavisna, te prema tome, svaka kontekstno nezavisna gramatika se može svesti na istovjetnu gramatiku u Chomskyjevom normalnom obliku.

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

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

## [uredi] Alternativne definicije

Neki autori definišu 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 ili
  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 tome što unaprijed isključuje mogućnost da će gramatika generisati prazni niz, ε. Ostaje vrijediti svojstvo da bilo koja kontekstno nezavisna gramatika koja generiše jezik L se može svesti u gramatiku u Chomskyjevom normalnom obliku koja generiše jezik L - {ε}. Principijelna prednost potonje definicije jest što kao posljedica dokazi mogu biti marginalno jednostavniji, budući da svaki korak u generisanju međunizova nikad neće smanjiti dužinu rezultirajućeg međuniza. Nedostatak je, dakako, posebna pažnja koju treba posvetiti ukoliko je izvorna gramatika generisala ε

## [uredi] Također pogledajte

- Greibachov normalni oblik
- Kurodin normalni oblik

## [uredi] Reference

- Michael Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997; ISBN 0-534-94728-X Pages 98–101 of section 2.1: context-free grammars. Page 156.

- John Martin - Introduction to Languages and the Theory of Computation, McGraw Hill, 2003; ISBN 0-07-232200-4 Pages 237–240 of section 6.6: simplified forms and normal forms.

Preuzeto sa: "http://bs.wikipedia.org../../../c/h/o/Chomskyjev_normalni_oblik.html"

Kategorije: Formalni jezici

##### Views

- Članak
- Razgovor
- Trenutna verzija

##### interakcija

- Pomoć
- Vrata zajednice
- Čaršija
- Novosti
- Dobrovoljni prilozi

##### Pretraga

##### Drugi jezici

- Afrikaans
- Deutsch
- English
- Suomi
- Français
- Hrvatski
- 日本語
- Nederlands
- Polski