ГНФ је скраћеница за Греибацх нормалну форму. ЦФГ (граматика без контекста) је у ГНФ (Греибацх нормалном облику) ако сва правила производње задовољавају један од следећих услова:

• Почетни симбол који генерише ε. На пример, С → ε.
• Нетерминал који генерише терминал. На пример, А → а.
• Нетерминал који генерише терминал који прати било који број нетерминала. На пример, С → аАСБ.

На пример:

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

Правила производње Граматике Г1 задовољавају правила специфицирана за ГНФ, тако да је граматика Г1 у ГНФ-у. Међутим, правило производње Граматике Г2 не задовољава правила специфицирана за ГНФ јер А → ε и Б → ε садржи ε (само почетни симбол може да генерише ε). Дакле, граматика Г2 није у ГНФ-у.

Кораци за претварање ЦФГ у ГНФ

Корак 1: Претворите граматику у ЦНФ.

шта је говорник

Ако дата граматика није у ЦНФ, претворите је у ЦНФ. Можете погледати следећу тему да бисте претворили ЦФГ у ЦНФ: Чомски нормалан облик

како искључити режим програмера за Андроид

Корак 2: Ако граматика постоји лева рекурзија, елиминишите је.

Ако граматика без контекста садржи леву рекурзију, елиминишите је. Можете погледати следећу тему да бисте елиминисали леву рекурзију: Лева рекурзија

Корак 3: У граматици конвертујте дато правило производње у ГНФ облик.

Ако било које производно правило у граматици није у ГНФ облику, конвертујте га.

Пример:

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

Решење:

100 кмх у мпх

Како је дата граматика Г већ у ЦНФ-у и нема леве рекурзије, тако да можемо прескочити корак 1 и корак 2 и директно прећи на корак 3.

Правило производње А → СА није у ГНФ, па замењујемо С → КСБ | АА у правилу производње А → СА као:

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

Правило производње С → КСБ и Б → КСБА није у ГНФ-у, па заменимо Кс → а у производном правилу С → КСБ и Б → КСБА као:

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

Сада ћемо уклонити леву рекурзију (А → ААА), добијамо:

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

Сада ћемо уклонити нулту производњу Ц → ε, добијамо:

нумерисање азбуке

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

Правило производње С → АА није у ГНФ, па замењујемо А → аЦ | аБАЦ | а | аБА у производном правилу С → АА као:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

Правило производње Ц → ААЦ није у ГНФ, па замењујемо А → аЦ | аБАЦ | а | аБА у производном правилу Ц → ААЦ као:

 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 

Дакле, ово је ГНФ облик за граматику Г.