GNF означає нормальну форму Грейбаха. CFG (контекстно-вільна граматика) знаходиться в GNF (нормальній формі Грейбаха), якщо всі правила виробництва задовольняють одну з таких умов:

• Початковий символ, що генерує ε. Наприклад, S → ε.
• Нетермінал, що генерує термінал. Наприклад, A → a.
• Нетермінал, що генерує термінал, за яким слідує будь-яка кількість нетерміналів. Наприклад, S → aASB.

Наприклад:

заблоковані контакти

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

Правила створення граматики G1 задовольняють правила, визначені для GNF, тому граматика G1 знаходиться в GNF. Однак правило створення граматики G2 не задовольняє правила, визначені для GNF, оскільки A → ε і B → ε містить ε (лише початковий символ може генерувати ε). Отже, граматика G2 не в GNF.

Кроки для перетворення CFG в GNF

Крок 1: Перетворіть граматику в CNF.

Якщо задана граматика не в CNF, перетворіть її на CNF. Ви можете звернутися до наступної теми, щоб перетворити CFG у CNF: нормальна форма Хомського

крок 2: Якщо в граматиці існує ліва рекурсія, усуньте її.

Якщо контекстно-вільна граматика містить ліву рекурсію, вилучіть її. Ви можете звернутися до такої теми, щоб усунути ліву рекурсію: ліва рекурсія

крок 3: У граматиці перетворіть подане правило виробництва у форму GNF.

Якщо будь-яке правило виробництва в граматиці не є у формі GNF, перетворіть його.

приклад:

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

рішення:

Оскільки дана граматика G уже знаходиться в CNF і немає лівої рекурсії, тому ми можемо пропустити крок 1 і крок 2 і безпосередньо перейти до кроку 3.

Правила виробництва A → SA немає в GNF, тому ми замінюємо S → XB | AA у правилі виробництва A → SA як:

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

Правило виробництва S → XB і B → XBA не є в GNF, тому ми замінюємо X → a в правило виробництва S → XB і B → XBA як:

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

Тепер приберемо ліву рекурсію (A → AAA), отримаємо:

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

Тепер видалимо нульове виробництво C → ε, отримаємо:

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

Правила виробництва S → AA немає в GNF, тому ми підставляємо A → aC | aBAC | a | aBA в правилі виробництва S → AA як:

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

Правила виробництва C → AAC немає в GNF, тому ми замінюємо A → aC | aBAC | a | aBA у правилі виробництва C → AAC як:

 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 

Отже, це форма GNF для граматики G.