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

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

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

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

${\displaystyle S\to aSb}$

${\displaystyle S\to \varepsilon }$

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

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

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

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

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

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

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

${\displaystyle S\to aA}$

${\displaystyle A\to Sb}$

${\displaystyle S\to \varepsilon }$

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

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

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