У теорії формальної мови контекстно-вільна граматика перебуває в нормальній формі Грайбах (GNF), якщо праві частини всіх правил породження починаються з термінального символу, за яким можуть слідувати змінні. Нестрога форма допускає один виняток із цього обмеження, дозволяючи порожньому слову (epsilon, ε) перебувати в множині слів описаної мови. Авторкою концепції нормальної форми є Шейла Грайбах.
Отже, контекстно-вільна граматика має нормальну форму Грайбах тоді й тільки тоді, коли всі її правила породження задовольняють одному з перелічених нижче критеріїв:
де — це нетермінальний символ, — термінальний символ, — це (може бути порожня) послідовність нетермінальних символів, не включаючи початковий символ і — початковий символ.
Зверніть увагу, що граматика не має лівих рекурсій.
Будь-яка контекстно-вільна граматика може бути перетворена в еквівалентну, що відповідатиме критеріям нормальної форми Грайбах. В залежності від того, чи містить граматика ланцюгові правила, розмір побудованої граматики дорівнюватиме О(|G|4) (наявні) або О(|G|3) (відсутні), де — G це граматика, а |G| — її розмір.
Якщо взяти граматику в GNF та похідний рядок довжини n, будь-який низхідний аналізатор зупиниться на глибині .
Див. також
Форма Бакуса-Наура Нормальна форма Хомського Нормальна форма Куроди
Список літератури
Посилання