Нормална форма Грибах

У рачунарству, за контекстно-слободну граматику се каже да је у нормалној форми Грибах (ГНФ), ако су сва њена правила извођења облика:

$A\to \alpha X$

или

$S\to \lambda$

где је A нетерминални симбол, α је терминални симбол, 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'