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

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

Пример

Простым примером линейной грамматики служит грамматика ${\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 }$ . Произвольное слово данного языка не может быть разобрано автоматом с магазинной памятью без считывания всех его символов, поэтому язык является недетерминированным . Задача проверки заданного контекстно-свободного языка на то, является ли он линейным, неразрешима .

Примечания