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

Из Википедије, слободне енциклопедије

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

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'