Greibachin normalni oblik

U računarstvu, za kontekstno neovisnu gramatiku kažemo da je u Greibachinom 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 Greibachinom normalnom obliku. (Neke definicije Greibachinog normalnog oblika ne dozvoljavaju drugu komponentu pravila, u kojem pak slučaju u Greibachin 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 Greibachinom 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.

Greibachin normalni oblik je naziv dobio po Sheili Greibach.

Vidjeti također

• Chomskyjev normalni oblik
• Kurodin normalni oblik