Линейная грамматика

Линейная грамматика — это контекстно-свободная грамматика, такая что правая часть любого её правила вывода содержит не больше одного нетерминала.

Линейный язык — язык, порождаемый некоторой линейной грамматикой.

Пример

Простым примером линейной грамматики служит грамматика $G$ с множеством нетерминалов $N=\{S\}$, алфавитом $\mathrm{\Sigma }=\{a,b\}$, начальным нетерминалом $S$ и правилами вывода

$S\to aSb$

$S\to \epsilon$

Данная грамматика порождает нерегулярный язык $\{a^i{b}^i|i\ge 0\}$.

Соответствие регулярным языкам

Шаблон:Основная статья Выделяют особые виды линейных грамматик:

• Леволинейная грамматика, в которой нетерминалы всегда находятся в начале правых частей правил вывода;
• Праволинейная грамматика, в которой нетерминалы всегда находятся в конце правых частей правил вывода.

Каждый из этих видов в отдельности описывает в точности класс регулярных языков. Регулярной грамматикой называют грамматику, являющуюся либо леволинейной, либо праволинейной.

Другим особым типом линейной грамматики является:

• Линейная грамматика, в которой нетерминалы всегда находятся либо в начале, либо в конце правых частей правил вывода.

Добавлением новых нетерминалов можно привести любую линейную грамматику к описанному выше виду, не меняя при этом порождаемый грамматикой язык. Например, $G$ может быть приведена к виду

$S\to aA$

$A\to Sb$

$S\to \epsilon$

Таким образом, линейные грамматики такого вида порождают такой же класс языков, что и произвольные линейные грамматики.

Выразительность

Все регулярные языки являются линейными. Классическим примером линейного, но не регулярного языка является описанный выше язык $\{a^i{b}^i:i\ge 0\}$. Все линейные языки являются контекстно-свободными. Примером контекстно-свободного, но не линейного языка является язык Дика, состоящий из правильных скобочных последовательностей. Таким образом, регулярные языки являются собственным подмножеством линейных языков, которые, в свою очередь, являются собственным подмножеством контекстно-свободных языков.

В то время, как все регулярные линейные языки являются детерминированными, существуют недетерминированные линейные языки. Примером такого языка может служить язык палиндромов чётной длины над алфавитом $\mathrm{\Sigma }=\{0,1\}$, который задаётся линейной грамматикой $S\to 0S0|1S1|\epsilon$. Произвольное слово данного языка не может быть разобрано автоматом с магазинной памятью без считывания всех его символов, поэтому язык является недетерминированным. Задача проверки заданного контекстно-свободного языка на то, является ли он линейным, неразрешима.