Greibachov normalni oblik

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

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.

Primjetimo 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[uredi | uredi izvor]