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

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

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

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

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

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

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

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

Смотрите также

Ссылки

^ Грейбах, Шейла (январь 1965 г.). «Новая теорема нормальной формы для контекстно-свободных грамматик фразовой структуры». Журнал ACM . 12 (1): 42–52. doi : 10.1145/321250.321254 . S2CID 12991430.
^ Блюм, Норберт; Кох, Роберт (1999). «Повторное рассмотрение преобразования нормальной формы Грейбаха». Информация и вычисления . 150 (1): 112–118. CiteSeerX 10.1.1.47.460 . doi :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 г.). «Новая теорема нормальной формы для контекстно-свободных грамматик фразовой структуры». Журнал ACM . 12 (1): 42–52. doi : 10.1145/321250.321254 . S2CID 12991430.

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