Razlika između inačica stranice »Greibachin normalni oblik«

Sheila Greibach nije istrazivac vec istrazivacica.
m (Ivucica je premjestio stranicu Greibachov normalni oblik na Greibachin normalni oblik preko preusmjeravanja: Sheila Greibach je istrazivacica, ne istrazivac.)
(Sheila Greibach nije istrazivac vec istrazivacica.)
U [[računarstvo|računarstvu]], za [[kontekstno neovisna gramatika|kontekstno neovisnu gramatiku]] kažemo da je u GreibachovomGreibachinom normalnom obliku ako ima sve produkcije oblika:
 
:<math>A \to \alpha X</math>
Primjetimo da gramatika ne smije imati lijevih rekurzija.
 
Svaka kontekstno neovisna gramatika se može svesti u istovjetnu gramatiku u GreibachovomGreibachinom normalnom obliku. (Neke definicije GreibachovogGreibachinog normalnog oblika ne dozvoljavaju drugu komponentu pravila, u kojem pak slučaju u GreibachovGreibachin 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]].
 
Za danu gramatiku u GreibachovomGreibachinom 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''.
 
'''GreibachovGreibachin normalni oblik''' je naziv dobio po [[Sheila Greibach|Sheili Greibach]].
 
== Vidjeti također ==
41

uređivanje