Изворни код странице Нормална форма Грибах

У [[рачунарство|рачунарству]], за [[контекстно слободна граматика|контекстно-слободну граматику]] се каже да је у '''нормалној форми Грибах''' (ГНФ), ако су сва њена [[правило извођења|правила извођења]] облика:
:<math>A \to \alpha X</math> 
или
:<math>S \to \lambda</math>
где је ''-{A}-'' [[завршни и незавршни симболи|нетерминални симбол]], &alpha; је [[завршни и незавршни симболи|терминални симбол]], ''-{X}-'' је (можда празан) низ нетерминалних симбола искључујући почетни симбол, ''-{S}-'' је почетни симбол, а ''-{λ}-'' је празан стринг.

Из овога следи да је граматика која је у нормалној форми Грибах без левих рекурзија.

Свака контекстно-слободна граматика може да се трансформише у еквивалентну граматику у нормалној форми Грибах. (Неке дефиниције не дозвољавају други од наведена два облика правила извођења, у ком случају контекстно-слободна граматика која може да генерише празну [[ниска|ниску]] не може да се трансформише у нормалну форму Грибах.) Ово може да се користи за доказ да сваки [[контекст-слободни језик|контекстно-слободни језик]] може да буде препознат од стране недетерминистичког [[потисни аутомат|потисног аутомата]].

За дату граматику у ГНФ и ниску дужине ''-{n}-'', изводљиву у тој граматици, сваки [[топ-даун парсер]] ће стати на дубини ''-{n}-''.

'''Нормална форма Грибах''' је добила име по [[Шила Грибах|Шили Грибах]].

== Види још ==
* [[Бакус–Наурова форма|Бекус-Наурова форма]]
* [[Нормална форма Чомског]]
* [[Нормална форма Куроде]]

== Литература ==
* -{John E. Hopcroft and Jeffrey D. Ullman, ''Introduction to Automata Theory, Languages and Computation'', Addison-Wesley Publishing, Reading Massachusetts, 1979. {{ISBN|0-201-029880-X}}. ''(See chapter 4.)''}-
* Душко М. Витас, ''Преводиоци и интерпретатори (Увод у теорију и методе компилације програмских језика)'', [[Математички факултет Универзитета у Београду|Математички факултет]], Београд, 2006'

{{нормативна контрола}}

[[Категорија:Формални језици]]