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

В информатике линейная грамматика — это контекстно-свободная грамматика , имеющая не более одного нетерминала в правой части каждого из своих произведений.

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

Пример

Примером линейной грамматики является G с N = {S}, Σ = {a, b}, P с начальным символом S и правилами.

S → аСб

С → е

Он генерирует язык $\{a^{i}b^{i}\mid i\geq 0\}$.

Связь с обычными грамматиками

Два специальных типа линейных грамматик:

• леволинейные , или леворегулярные грамматики, в которых все правила имеют вид A → αw где α либо пусто, либо один нетерминал, а w — строка терминалов;
• праволинейные , или праворегулярные грамматики, в которых все правила имеют вид A → wα где w — строка терминалов, а α — либо пустая, либо один нетерминал.

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

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

С → аА

А → Сб

С → е

Однако требование, чтобы все правила были леволинейными (или все правила были праволинейными) приводит к резкому снижению выразительной силы линейных грамматик.

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

Все регулярные языки линейны; и наоборот, примером линейного нерегулярного языка является { a ^н б ^н }. как объяснено выше.Все линейные языки являются контекстно-свободными ; и наоборот, примером контекстно-свободного нелинейного языка является язык Дика хорошо сбалансированных пар скобок.Следовательно, регулярные языки являются собственным подмножеством линейных языков, которые, в свою очередь, являются собственным подмножеством контекстно-свободных языков.

Хотя обычные языки детерминированы , существуют недетерминированные линейные языки. четной длины Например, язык палиндромов в алфавите 0 и 1 имеет линейную грамматику S → 0S0 | 1С1 | е. Произвольная строка этого языка не может быть проанализирована без предварительного чтения всех ее букв, а это означает, что автомат с проталкиванием вниз должен пробовать альтернативные переходы состояний, чтобы приспособиться к различным возможным длинам полуразобранной строки. Этот язык недетерминирован. Поскольку недетерминированные контекстно-свободные языки не могут быть приняты за линейное время. В общем случае линейные языки не могут быть приняты за линейное время. Более того, неясно, является ли данный контекстно-свободный язык линейным контекстно-свободным языком.

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

Свойства замыкания

Положительные случаи

Линейные языки закрыты по союзу . Конструкция аналогична конструкции объединения контекстно-свободных языков. Позволять $L_{1},L_{2}$ если это два линейных языка, то $L_{1}\cup L_{2}$ построен с помощью линейной грамматики с $S\to S_{1}|S_{2}$, и $S_{1},S_{2}$ играющие роль линейных грамматик для $L_{1},L_{2}$.

Если L — линейный язык, а M — регулярный язык, то пересечение $L\cap M$ снова линейный язык; другими словами, линейные языки замкнуты относительно пересечения с регулярными множествами.

Линейные языки замкнуты относительно гомоморфизма и обратного гомоморфизма .

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

Отрицательные случаи

Линейные языки не замкнуты при пересечении. Например, пусть $L_{1}=\{a^{n}b^{n}c^{m}\mid n,m\geq 0\},L_{2}=\{a^{n}b^{m}c^{m}\mid n,m\geq 0\}$, то их пересечение не только не линейно, но и не контекстно-свободно. См. лемму о накачке для контекстно-свободных языков .

Как следствие, линейные языки не замкнуты относительно дополнения (поскольку пересечение может быть построено по законам де Моргана из объединения и дополнения).