Greibachov normalni oblik - Wikipedia, slobodna enciklopedija

# Greibachov normalni oblik

### Sa Wikipedije, slobodne enciklopedije

U računarstvu, za kontekstno nezavisnu gramatiku kažemo da je u Greibachovom normalnom obliku ako ima sve produkcije oblika:

  ili

gdje je a A nezavršni znak, a X (moguće prazan) slijed nezavršnih znakova ne uključujući početni znak, S početni znak te ε prazni niz.

Primjetimo da gramatika ne smije imati lijevih rekurzija.

Svaka kontekstno nezavisna gramatika se može svesti u istovjetnu gramatiku u Greibachovom normalnom obliku. (Neke definicije Greibachovog normalnog oblika ne dozvoljavaju drugu komponentu pravila, u kojem slučaju se ne može svesti gramatika koja generiše prazni niz u Greibachov normalni oblik .) Ovo se svojstvo može iskoristiti za dokazivanje činjenice da svaki kontekstno nezavisni jezik može biti prihvaćen od strane nedeterminističkog potisnog automata.

Za datu gramatiku u Greibachovom normalnom obliku i neki niz znakova kojeg generiše dužine n, svaki parser od vrha prema dnu će zaustaviti parsiranje na dubini od najviše n.

Greibachov normalni oblik je naziv dobio po Sheili Greibach.

## [uredi] Vidjeti također

- Chomskyjev normalni oblik
- Kurodin normalni oblik

Preuzeto sa: "http://bs.wikipedia.org../../../g/r/e/Greibachov_normalni_oblik.html"

Kategorije: Formalni jezici

##### Views

- Članak
- Razgovor
- Trenutna verzija

##### interakcija

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

##### Pretraga

##### Drugi jezici

- Deutsch
- English
- Hrvatski
- 日本語
- Nederlands
- Polski
- Română
- 中文