Greibachin normalni oblik: razlika između inačica

m
ispravak
(Sheila Greibach nije istrazivac vec istrazivacica.)
m (ispravak)
 
gdje je a ''A'' [[Završni i nezavršni znakovi|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]].
 
PrimjetimoPrimijetimo 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 [[potisni automat|potisnog automata]].