Greibachov normalni oblik

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

$A\to \alpha X$

ili

$S\to \epsilon$

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.

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

Također pogledajte

• Chomskyjev normalni oblik
• Kurodin normalni oblik