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

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

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

$A\to aA_{1}A_{2}\cdots A_{n}$;

$S\to aA_{1}A_{2}\cdots A_{n}$;

$S\to \varepsilon$;

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

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

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

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

Див. також

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

Посилання

• Alexander Meduna (6 грудня 2012). Automata and Languages: Theory and Applications. Springer Science & Business Media. ISBN 978-1-4471-0501-5.
• György E. Révész (17 березня 2015). Introduction to Formal Languages. Courier Corporation. ISBN 978-0-486-16937-8.