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

В Информатика, а линейная грамматика это контекстно-свободная грамматика который имеет не более одного нетерминала в Правая сторона каждой своей продукции.

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

Пример

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

S → aSb

S → ε

Он порождает язык ${ Displaystyle {а ^ {я} Ь ^ {я} ; | ; я geq 0 }}$.

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

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

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

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

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

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

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

S → aA

А → Sb

S → ε

Следовательно, линейные грамматики этой специальной формы могут порождать все линейные языки.

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

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

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

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

Если L является линейным языком и M - регулярный язык, то пересечение ${ Displaystyle L cap M}$ снова линейный язык; другими словами, линейные языки замкнуты относительно пересечения с регулярными множествами. Кроме того, линейные языки замкнуты относительно гомоморфизм и обратный гомоморфизм.^[3] Эти три свойства замыкания показывают, что линейные языки образуют полное трио. Полные трио - это языковые семьи, обладающие парой других желаемых математических свойств.

Рекомендации