GNF oznacza postać normalną Greibacha. CFG (gramatyka bezkontekstowa) jest w GNF (forma normalna Greibacha), jeśli wszystkie reguły tworzenia spełniają jeden z następujących warunków:

• Symbol startu generujący ε. Na przykład S → ε.
• Nieterminal generujący terminal. Na przykład A → a.
• Nieterminal generujący terminal, po którym następuje dowolna liczba nieterminali. Na przykład S → aASB.

Na przykład:

 G1 = aB, A → aA G2 = S → aAB 

Reguły tworzenia Gramatyki G1 odpowiadają regułom określonym dla GNF, więc gramatyka G1 jest w GNF. Jednak reguła tworzenia Gramatyki G2 nie spełnia reguł określonych dla GNF, ponieważ A → ε i B → ε zawiera ε (tylko symbol startu może wygenerować ε). Zatem gramatyki G2 nie ma w GNF.

Kroki konwersji CFG na GNF

Krok 1: Zamień gramatykę na CNF.

Jeśli podana gramatyka nie jest w CNF, zamień ją na CNF. Aby przekonwertować CFG na CNF, możesz zapoznać się z następującym tematem: Normalna postać Chomsky'ego

Krok 2: Jeśli gramatyka istnieje w rekurencji lewej, wyeliminuj ją.

Jeśli gramatyka bezkontekstowa zawiera lewą rekursję, wyeliminuj ją. Aby wyeliminować lewą rekursję, możesz zapoznać się z następującym tematem: Lewa rekurencja

Krok 3: W gramatyce przekształć podaną regułę produkcji do postaci GNF.

Jeśli jakakolwiek reguła tworzenia w gramatyce nie jest w formie GNF, przekonwertuj ją.

Przykład:

 S → XB | AA A → a | SA B → b X → a 

Rozwiązanie:

Ponieważ dana gramatyka G jest już w CNF i nie ma lewej rekurencji, możemy więc pominąć krok 1 i krok 2 i przejść bezpośrednio do kroku 3.

Reguła produkcji A → SA nie występuje w GNF, dlatego zastępujemy S → XB | AA w regule produkcyjnej A → SA jako:

 S → XB | AA A → a | XBA | AAA B → b X → a 

Reguły produkcji S → XB i B → XBA nie ma w GNF, więc podstawiamy X → a w regule produkcji S → XB i B → XBA jako:

 S → aB | AA A → a | aBA | AAA B → b X → a 

Teraz usuniemy lewą rekursję (A → AAA), otrzymamy:

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

Teraz usuniemy produkcję zerową C → ε, otrzymamy:

 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

Reguła produkcji S → AA nie występuje w GNF, więc zastępujemy A → aC | aBAC | | aBA w regule produkcyjnej S → AA jako:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

Reguła produkcji C → AAC nie występuje w GNF, dlatego zastępujemy A → aC | aBAC | | aBA w regule produkcyjnej C → AAC jako:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a 

Jest to zatem forma GNF dla gramatyki G.