Линейная грамматика — это контекстно-свободная грамматика, такая что правая часть любого её правила вывода содержит не больше одного нетерминала.
Линейный язык — язык, порождаемый некоторой линейной грамматикой.
Пример Простым примером линейной грамматики служит грамматика с множеством нетерминалов , алфавитом , начальным нетерминалом и правилами вывода
Данная грамматика порождает нерегулярный язык .
Соответствие регулярным языкам
Выделяют особые виды линейных грамматик:
Леволинейная грамматика, в которой нетерминалы всегда находятся в начале правых частей правил вывода; Праволинейная грамматика, в которой нетерминалы всегда находятся в конце правых частей правил вывода.
Каждый из этих видов в отдельности описывает в точности класс регулярных языков. Регулярной грамматикой называют грамматику, являющуюся либо леволинейной, либо праволинейной.
Другим особым типом линейной грамматики является:
Линейная грамматика, в которой нетерминалы всегда находятся либо в начале, либо в конце правых частей правил вывода.
Добавлением новых нетерминалов можно привести любую линейную грамматику к описанному выше виду, не меняя при этом порождаемый грамматикой язык. Например, может быть приведена к виду
Таким образом, линейные грамматики такого вида порождают такой же класс языков, что и произвольные линейные грамматики.
Выразительность Все регулярные языки являются линейными. Классическим примером линейного, но не регулярного языка является описанный выше язык . Все линейные языки являются контекстно-свободными. Примером контекстно-свободного, но не линейного языка является язык Дика, состоящий из правильных скобочных последовательностей. Таким образом, регулярные языки являются собственным подмножеством линейных языков, которые, в свою очередь, являются собственным подмножеством контекстно-свободных языков.
В то время, как все регулярные линейные языки являются детерминированными, существуют недетерминированные линейные языки. Примером такого языка может служить язык палиндромов чётной длины над алфавитом , который задаётся линейной грамматикой . Произвольное слово данного языка не может быть разобрано автоматом с магазинной памятью без считывания всех его символов, поэтому язык является недетерминированным. Задача проверки заданного контекстно-свободного языка на то, является ли он линейным, неразрешима.
Примечания
Категория:Формальные грамматики