A GNF a Greibach normál formát jelenti. A CFG (kontextusmentes nyelvtan) GNF (Greibach normál formában) van, ha az összes előállítási szabály megfelel a következő feltételek egyikének:
- ε-t generáló start szimbólum. Például S → ε.
- Terminált generáló nem terminál. Például A → a.
- Nem terminál, amely egy terminált generál, amelyet tetszőleges számú nem terminál követ. Például S → aASB.
Például:
G1 = aB, A → aA G2 = S → aAB
A Grammar G1 előállítási szabályai megfelelnek a GNF-re meghatározott szabályoknak, így a G1 nyelvtan GNF-ben van. A G2 Grammar előállítási szabálya azonban nem teljesíti a GNF-re meghatározott szabályokat, mivel A → ε és B → ε tartalmazza az ε-t (csak a kezdőszimbólum generálhat ε-t). Tehát a G2 nyelvtan nincs a GNF-ben.
A CFG GNF-vé alakításának lépései
1. lépés: Alakítsa át a nyelvtant CNF-be.
Ha az adott nyelvtan nincs CNF-ben, konvertálja át CNF-be. A CFG CNF-be való konvertálásához tekintse át a következő témakört: Chomsky normál forma
2. lépés: Ha a nyelvtanban létezik bal oldali rekurzió, szüntesse meg.
Ha a kontextusmentes nyelvtan bal oldali rekurziót tartalmaz, törölje azt. A bal oldali rekurzió kiküszöbölésére a következő témakörre hivatkozhat: Bal oldali rekurzió
részstring string java
3. lépés: A nyelvtanban alakítsa át az adott termelési szabályt GNF formára.
Ha a nyelvtan bármely termelési szabálya nem GNF formátumú, akkor konvertálja azt.
Példa:
S → XB | AA A → a | SA B → b X → a
Megoldás:
Mivel az adott G nyelvtan már CNF-ben van, és nincs baloldali rekurzió, így kihagyhatjuk az 1. és 2. lépést, és közvetlenül a 3. lépésre léphetünk.
Az A → SA előállítási szabály nem szerepel a GNF-ben, ezért S → XB | AA az A → SA termelési szabályban, mint:
S → XB | AA A → a | XBA | AAA B → b X → a
Az S → XB és B → XBA termelési szabály nem szerepel a GNF-ben, ezért az S → XB és B → XBA termelési szabályban X → a-t helyettesítjük a következőképpen:
hoszt linux
S → aB | AA A → a | aBA | AAA B → b X → a
Most eltávolítjuk a bal oldali rekurziót (A → AAA), így kapjuk:
S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a
Most eltávolítjuk a C → ε nulltermelést, így kapjuk:
S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a
Az S → AA előállítási szabály nem szerepel a GNF-ben, ezért behelyettesítjük az A → aC | aBAC | a | aBA az S → AA termelési szabályban, mint:
S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a
A C → AAC előállítási szabály nincs a GNF-ben, ezért behelyettesítjük az A → aC | aBAC | a | aBA a C termelési szabályban → AAC, mint:
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
Ezért ez a G nyelvtan GNF formája.