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.