Введение

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

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

Все регулярные языки линейны; наоборот, примером линейного, нерегулярного языка является { aⁿbⁿ }, как было объяснено выше. Все линейные языки контекстно-свободны; наоборот, примером контекстно-свободного, нелинейного языка является язык Дика с хорошо сбалансированными парами скобок. Следовательно, регулярные языки являются собственным подмножеством линейных языков, которые, в свою очередь, являются собственным подмножеством контекстно-свободных языков. В то время как регулярные языки детерминированы, существуют линейные языки, которые недетерминированы. Например, язык палиндромов четной длины в алфавите 0 и 1 имеет линейную грамматику S → 0S0 | 1S1 | ε. Произвольную строку этого языка нельзя проанализировать, не прочитав все его символы, что означает, что автомат с магазинной памятью должен пробовать альтернативные переходы состояний, чтобы учесть различные возможные длины частично проанализированной строки. Этот язык недетерминирован. Поскольку недетерминированные контекстно-свободные языки не могут быть распознаны за линейное время, линейные языки не могут быть распознаны за линейное время в общем случае. Кроме того, неразрешимо, является ли данный контекстно-свободный язык линейным контекстно-свободным языком. Язык линеен тогда и только тогда, когда он может быть сгенерирован однооборотным автоматом с магазинной памятью – автоматом с магазинной памятью, который, начав извлечение, больше никогда не выполняет вставку.

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

Линейные языки замкнуты относительно операции объединения. Конструкция аналогична конструкции для объединения контекстно-свободных языков. Пусть L и M – два линейных языка, тогда L ∪ M конструируется линейной грамматикой с L и M, играющими роль линейных грамматик для L и M соответственно. Если L – линейный язык, а M – регулярный язык, то пересечение L ∩ M снова является линейным языком; другими словами, линейные языки замкнуты относительно пересечения с регулярными множествами. Линейные языки замкнуты относительно гомоморфизмов и обратных гомоморфизмов. Как следствие, линейные языки образуют полное трио. Полные трио в общем случае представляют собой семейства языков, обладающие несколькими другими желательными математическими свойствами.

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

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