Greibachin normalni oblik

U računarstvu, za kontekstno neovisnu 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.

Primjetimo da gramatika ne smije imati lijevih rekurzija.

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

Za danu gramatiku u Greibachovom normalnom obliku i neki niz znakova kojeg generira duljine 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.

Vidjeti također

• Chomskyjev normalni oblik
• Kurodin normalni oblik