Математическая энциклопедия - грамматика бесконтекстная

грамматика контекстно-свободная, КС-грамматика,грамматика составляющих, все правила к-рой имеют вид где А - вспомогательный символ и непустая цепочка (так наз. бесконтекстные правила). Языки, порождаемые такими грамматиками, наз. бесконтекстными языками. Напр., язык порождается Г. б. с правилами (начальный символ).

В определении Г. б. условие непустоты можно отбросить без существенного изменения класса языков (добавляются лишь языки, получаемые из бесконтекстных присоединением пустой цепочки). Г. б.наиболее употребительный в приложениях класс формальных грамматик;они широко используются для построения математич. моделей естественных языков (см. Математическая лингвистика).и для описания языков программирования. Класс бесконтекстных языков является собственным подклассом класса НС-языков (см. Грамматика составляющих;напр., НС-язык не бесконтекстный) и совпадает с классом языков, допускаемых так наз. автоматами с магазинной памятью (МП -автоматами).

Каждая Г. б. может быть эквивалентным образом приведена к стандартной бинарной форме Г. б., все правила к-рой имеют вид и , а также кнормальной форме Грейбах Г. б., все правила к-рой имеют вид , и (в обоих случаях А, В, С - вспомогательные символы, а - основной символ). Бесконтекстные языки определяются также грамматиками категориальными, грамматиками доминационными, грамматиками зависимостей. Иногда для определения бесконтекстных языков используются так наз. нормальные системы уравнений в языках, представляющие собой другую форму записи Г. б. Класс бесконтекстных языков замкнут относительно объединения, умножения, подстановки и усеченной итерации (а при наличии правил с пустой правой частью и относительно итерации) и не замкнут относительно пересечения и дополнения. Г. б. Г наз. однозначной, если для каждой цепочки языка L(Г)имеется единственное дерево вывода в Г. Бесконтекстный язык наз. однозначным, если он порождается нек-рой однозначной Г. б.; в противном случае он наз. неоднозначным (или существенно неоднозначным, существенно неопределенным). Пример неоднозначного бесконтекстного языка -

Если для любой Г. б., порождающей бесконтекстный язык L, и любого натурального найдется цепочка, имеющая более пдеревьев вывода в данной грамматике, говорят, что Lимеет бесконечную степень неоднозначности; пример язык где означает обращение (т. е. если ).

Бесконтекстный язык наз. детерминированным, если он допускается нек-рым детерминированным МП-автоматом. Всякий детерминированный язык однозначен, обратное неверно: напр., однозначный язык не является детерминированным.