GNF je zkratka pro normální formu Greibach. CFG (bezkontextová gramatika) je v GNF (normální forma Greibach), pokud všechna produkční pravidla splňují jednu z následujících podmínek:

• Počáteční symbol generující ε. Například S → ε.
• Neterminál generující terminál. Například A → a.
• Neterminál generující terminál, po kterém následuje libovolný počet neterminálů. Například S → aASB.

Například:

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

Produkční pravidla gramatiky G1 splňují pravidla specifikovaná pro GNF, takže gramatika G1 je v GNF. Produkční pravidlo gramatiky G2 však nesplňuje pravidla specifikovaná pro GNF, protože A → ε a B → ε obsahuje ε (pouze počáteční symbol může generovat ε). Takže gramatika G2 není v GNF.

řetězec na celé číslo v jazyce Java

Kroky pro konverzi CFG na GNF

Krok 1: Převeďte gramatiku do CNF.

Pokud daná gramatika není v CNF, převeďte ji do CNF. Chcete-li převést CFG na CNF, můžete se podívat na následující téma: Chomsky normální forma

Krok 2: Pokud gramatika existuje levá rekurze, odstraňte ji.

Pokud bezkontextová gramatika obsahuje levou rekurzi, odstraňte ji. Chcete-li odstranit levou rekurzi, můžete se podívat na následující téma: Levá rekurze

Krok 3: V gramatice převeďte dané produkční pravidlo do tvaru GNF.

Pokud některé produkční pravidlo v gramatice není ve formě GNF, převeďte jej.

Příklad:

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

Řešení:

Protože daná gramatika G je již v CNF a není zde žádná levá rekurze, můžeme přeskočit krok 1 a krok 2 a přejít přímo ke kroku 3.

Produkční pravidlo A → SA není v GNF, takže dosadíme S → XB | AA ve výrobním pravidle A → SA jako:

jak převést celé číslo na řetězec java

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

Produkční pravidlo S → XB a B → XBA není v GNF, proto dosadíme X → a v produkčním pravidle S → XB a B → XBA jako:

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

Nyní odstraníme levou rekurzi (A → AAA), dostaneme:

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

Nyní odstraníme nulovou produkci C → ε, dostaneme:

sloučení řazení java

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

Produkční pravidlo S → AA není v GNF, proto dosadíme A → aC | aBAC | a | aBA v produkčním pravidle 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 

Produkční pravidlo C → AAC není v GNF, proto dosadíme A → aC | aBAC | a | aBA v produkčním pravidle 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 

Jedná se tedy o formu GNF pro gramatiku G.