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


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

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

Пример

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

S → a S b {displaystyle S o aSb} S → ε {displaystyle S o varepsilon }

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

Соответствие регулярным языкам

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

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

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

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

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

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

S → a A {displaystyle S o aA} A → S b {displaystyle A o Sb} S → ε {displaystyle S o varepsilon }

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

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

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

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






Яндекс.Метрика