Нормальная форма Грейбаха - Greibach normal form

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

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

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

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

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

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

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

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

использованная литература

^ Грейбах, Шейла (январь 1965 г.). «Новая теорема о нормальной форме для грамматик контекстно-свободных фраз». Журнал ACM. 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.

Александр Медуна (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. Дои:10.1145/321250.321254. S2CID 12991430.

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

[1]

[2]