GNF apzīmē Greibach normālo formu. CFG (bezkonteksta gramatika) ir GNF (Greibaha normālā formā), ja visi ražošanas noteikumi atbilst vienam no šiem nosacījumiem:
runas in powershell
- Sākuma simbols, kas ģenerē ε. Piemēram, S → ε.
- Neterminālis, kas ģenerē termināli. Piemēram, A → a.
- Neterminālis, kas ģenerē termināli, kam seko jebkāds skaits netermināļu. Piemēram, S → aASB.
Piemēram:
G1 = aB, A → aA G2 = S → aAB
Gramatikas G1 ražošanas noteikumi atbilst GNF noteiktajiem noteikumiem, tāpēc gramatika G1 ir GNF. Tomēr Gramatikas G2 ražošanas noteikums neatbilst GNF noteiktajiem noteikumiem, jo A → ε un B → ε satur ε (tikai sākuma simbols var ģenerēt ε). Tātad gramatika G2 nav GNF.
Soļi CFG pārvēršanai GNF
1. darbība: Pārvērtiet gramatiku par CNF.
Ja dotā gramatika nav CNF, konvertējiet to par CNF. Varat atsaukties uz šo tēmu, lai pārveidotu CFG par CNF: Chomsky parastā forma
2. darbība: Ja gramatikā ir kreisā rekursija, izslēdziet to.
atgriežot masīvu java
Ja konteksta brīvā gramatika satur kreiso rekursiju, izslēdziet to. Lai novērstu kreiso rekursiju, varat atsaukties uz šo tēmu: Kreisā rekursija
3. darbība: Gramatikā konvertējiet doto ražošanas noteikumu GNF formā.
Ja kāds gramatikas ražošanas noteikums nav GNF formā, konvertējiet to.
Piemērs:
S → XB | AA A → a | SA B → b X → a
Risinājums:
Tā kā dotā gramatika G jau ir CNF un nav kreisās rekursijas, mēs varam izlaist 1. un 2. darbību un tieši pāriet uz 3. darbību.
knn
Ražošanas noteikums A → SA nav GNF, tāpēc mēs aizstājam S → XB | AA ražošanas noteikumā A → SA kā:
S → XB | AA A → a | XBA | AAA B → b X → a
Ražošanas noteikums S → XB un B → XBA nav GNF, tāpēc mēs aizstājam X → a ražošanas noteikumā S → XB un B → XBA kā:
S → aB | AA A → a | aBA | AAA B → b X → a
Tagad mēs noņemsim kreiso rekursiju (A → AAA), mēs iegūstam:
S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a
Tagad mēs noņemsim nulles ražošanu C → ε, mēs iegūstam:
alfabēta numurēšana
S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a
Ražošanas noteikums S → AA nav GNF, tāpēc mēs aizstājam A → aC | aBAC | a | aBA ražošanas noteikumā S → AA kā:
S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a
Ražošanas noteikums C → AAC nav GNF, tāpēc mēs aizstājam A → aC | aBAC | a | aBA ražošanas noteikumā C → AAC kā:
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
Tādējādi šī ir GNF forma gramatikai G.