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

В формального языка теории бесконтекстная грамматика находится в нормальной форме Грейбаха ( GNF ), если правые части всех правил производства начинаются с терминального символа , за которым необязательно следуют некоторые переменные. Нестрогая форма допускает одно исключение из этого ограничения формата, позволяющее пустому слову (эпсилон, ε) быть членом описываемого языка. Нормальную форму установила Шейла Грейбах и носит ее имя.

Точнее, контекстно-свободная грамматика находится в нормальной форме Грейбаха, если все продукционные правила имеют вид:

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

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

Обратите внимание, что в грамматике нет левых рекурсий .

Любую контекстно-свободную грамматику можно преобразовать в эквивалентную грамматику в нормальной форме Грейбаха. ^[1] Существуют различные конструкции. Некоторые не допускают вторую форму правила и не могут преобразовать контекстно-свободные грамматики, которые могут генерировать пустое слово. Для одной такой конструкции размер построенной грамматики равен O( n ⁴) в общем случае и O( n ³), если ни один вывод исходной грамматики не состоит из одного нетерминального символа, где n — размер исходной грамматики. ^[2] Это преобразование можно использовать для доказательства того, что каждый контекстно-свободный язык может быть принят (недетерминированным) автоматом с выталкиванием вниз в реальном времени , т. е. автомат на каждом шаге считывает букву со своего входа.

Учитывая грамматику в GNF и производную строку в грамматике длиной n , любой анализатор сверху вниз остановится на глубине n .

См. также

Ссылки

^ Грейбах, Шейла (январь 1965 г.). «Новая теорема о нормальной форме для грамматик контекстно-свободной фразовой структуры» . Журнал АКМ . 12 (1): 42–52. дои : 10.1145/321250.321254 . S2CID 12991430 .
^ Блюм, Норберт; Кох, Роберт (1999). «Возвращение к преобразованию нормальной формы Грейбаха». Информация и вычисления . 150 (1): 112–118. CiteSeerX 10.1.1.47.460 . дои : 10.1006/inco.1998.2772 . S2CID 10302796 .

Александр Медуна (6 декабря 2012 г.). Автоматы и языки: теория и приложения . Springer Science & Business Media. ISBN 978-1-4471-0501-5 .
Дьердь Э. Ревес (17 марта 2015 г.). Введение в формальные языки . Курьерская корпорация. ISBN 978-0-486-16937-8 .

[1] Грейбах, Шейла (январь 1965 г.). «Новая теорема о нормальной форме для грамматик контекстно-свободной фразовой структуры» . Журнал АКМ . 12 (1): 42–52. дои : 10.1145/321250.321254 . S2CID 12991430 .

[2] Блюм, Норберт; Кох, Роберт (1999). «Возвращение к преобразованию нормальной формы Грейбаха». Информация и вычисления . 150 (1): 112–118. CiteSeerX 10.1.1.47.460 . дои : 10.1006/inco.1998.2772 . S2CID 10302796 .

[1]

[2]