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.