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.