Нормальна форма Грайбах

У теорії формальної мови контекстно-вільна граматика перебуває в нормальній формі Грайбах (GNF), якщо праві частини всіх правил породження починаються з термінального символу, за яким можуть слідувати змінні. Нестрога форма допускає один виняток із цього обмеження, дозволяючи порожньому слову (epsilon, ε) перебувати в множині слів описаної мови. Авторкою концепції нормальної форми є Шейла Грайбах.

Отже, контекстно-вільна граматика має нормальну форму Грайбах тоді й тільки тоді, коли всі її правила породження задовольняють одному з перелічених нижче критеріїв:

$A\to a{A}_1{A}_2\cdots A_n$;

$S\to a{A}_1{A}_2\cdots A_n$;

$S\to \epsilon$;

де $A$ — це нетермінальний символ, $a$ — термінальний символ, $A_1{A}_2\dots A_n$ — це (може бути порожня) послідовність нетермінальних символів, не включаючи початковий символ і $S$ — початковий символ.

Зверніть увагу, що граматика не має лівих рекурсій.

Будь-яка контекстно-вільна граматика може бути перетворена в еквівалентну, що відповідатиме критеріям нормальної форми Грайбах. В залежності від того, чи містить граматика ланцюгові правила, розмір побудованої граматики дорівнюватиме О(|G|⁴) (наявні) або О(|G|³) (відсутні), де — G це граматика, а |G| — її розмір.

Якщо взяти граматику в GNF та похідний рядок довжини n, будь-який низхідний аналізатор зупиниться на глибині Шаблон:Var.

Див. також

• Форма Бакуса-Наура
• Нормальна форма Хомського
• Нормальна форма Куроди

Посилання

• Шаблон:Cite book
• Шаблон:Cite book