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.