Normalna forma Gribah

U računarstvu, za kontekstno-slobodnu gramatiku se kaže da je u normalnoj formi Gribah (GNF), ako su sva njena pravila izvođenja oblika:

$A\to \alpha X$

ili

$S\to \lambda$

gde je A neterminalni simbol, α je terminalni simbol, X je (možda prazan) niz neterminalnih simbola isključujući početni simbol, S je početni simbol, a λ je prazan string.

Iz ovoga sledi da je gramatika koja je u normalnoj formi Gribah bez levih rekurzija.

Svaka kontekstno-slobodna gramatika može da se transformiše u ekvivalentnu gramatiku u normalnoj formi Gribah. (Neke definicije ne dozvoljavaju drugi od navedena dva oblika pravila izvođenja, u kom slučaju kontekstno-slobodna gramatika koja može da generiše praznu nisku ne može da se transformiše u normalnu formu Gribah.) Ovo može da se koristi za dokaz da svaki kontekstno-slobodni jezik može da bude prepoznat od strane nedeterminističkog potisnog automata.

Za datu gramatiku u GNF i nisku dužine n, izvodljivu u toj gramatici, svaki top-daun parser će stati na dubini n.

Normalna forma Gribah je dobila ime po Šili Gribah.

Vidi još

• Bekus-Naurova forma
• Normalna forma Čomskog
• Normalna forma Kurode

Literatura

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X . (See chapter 4.)
• Duško M. Vitas, Prevodioci i interpretatori (Uvod u teoriju i metode kompilacije programskih jezika), Matematički fakultet, Beograd, 2006'