ГРАММАТИКА СОСТАВЛЯЮЩИХ

ГРАММАТИКА СОСТАВЛЯЮЩИХ, грамматика непосредственно составляющих, НС-грамматика, грамматика контекстная, - частный случай грамматики порождающей, Г = 〈:V, W, I, R〉, когда каждое ее правило имеет вид ξ₁Аξ₂ → ξ₁θξ₂, где ξ₁, ξ₂, θ - цепочки в алфавите V ∪ W, А ∈ W и θ непуста. Каждый шаг вывода в Г. с. состоит в замене одного вхождения символа A вхождением цепочки θ, причем возможность замены обусловлена наличием «контекста» ξ₁, ξ₂. Вхождения символов в θ потом также могут заменяться и т. д. Таким образом, вхождение символа «развертывается» в нек-рый отрезок возникающей в результате вывода цепочки. Это дает возможность представить вывод в Г. с. с помощью дерева (дерева вывода):

напр., если грамматика имеет правила I → ААВ, AB → DBB, аВВ → аbВ, А → а, D → a, В → С, С → с (а, b, с - основные символы, I, А, В, С, D - вспомогательные символы, I - начальный символ), то вывод (I, ААВ, аАВ, aDBB, ааВВ, ааbВ, ааbС, ааbс) имеет дерево, изображенное на рис. Множество всех отрезков последней цепочки вывода, получающихся «развертыванием» вхождений вспомогательных символов - иначе говоря, «происходящих» от (неконцевых) вершин дерева вывода - при добавлении всех одноточечных отрезков образует систему составляющих указанной цепочки (см. Синтаксическая структура); отсюда и название «Г. с». Если все одноточечные отрезки также получаются заменой вхождений вспомогательных символов, то можно получить размеченную систему составляющих, приписывая каждой составляющей в качестве меток те вспомогательные символы, от вхождении к-рых она «происходит»; так, в приведенном выше примере для цепочки ааbс получается размеченная система составляющих

((а)А ((a)D(b)B)A(с)В,С)I

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

где ПРЕДЛ, S_xyz, Ṽ³, V^t3 - вспомогательные символы, означающие, соответственно, «предложение», «существительное рода х в числе y и падеже z», «группа глагола в 3-м лице», «переходный глагол в 3-м лице», а символ ПРЕДЛ - начальный, приписывает предложению «Эллипс пересекает параболу» размеченную систему составляющих

((Эллипс) S_{муж, ед, им} ((пересекает) V^t3 (параболу) S_{жен, ед, вин})Ṽ³) ПРЕДЛ.

Математич. значение Г. с. определяется прежде всего тем, что порождаемые ими языки (так наз. НС-языки) представляют собой простой подкласс класса примитивно рекурсивных множеств: класс НС-языков совпадает с классом языков, допускаемых недетерминированными линейно ограниченными Тьюринга машинами с одной лентой и одной головкой. «Конкретные» числовые множества при обычных способах кодирования натуральных чисел весьма часто оказываются НС-языками (таковы, напр., множество полных квадратов, множество простых чисел, множество десятичных приближений числа √2 и т. п.).

Для каждой Г. с. может быть построена эквивалентная ей левоконтекстная (соответственно правоконтекстная) Г. с, то есть Г. с, все правила к-рой имеют вид ξA → ξθ (соответственно Aξ → θξ). В то же время всякая Г. с, все правила к-рой имеют вид хАу → xθy, где х, у - цепочки в основном алфавите, эквивалентна нек-рой грамматике бесконтекстной.

Класс НС-языков замкнут относительно объединения, пересечения, умножения, усеченной итерации, подстановки; неизвестно, замкнут ли он относительно дополнения.

Сложность вывода. Временнáя сложность вывода в Г. с. ограничена сверху показательной функцией. Существуют языки, порождаемые Г. с. с временнóй сложностью порядка n² и не порождаемые никакими Г. с. с меньшей по порядку временнóй сложностью (например, язык {хbх| х ∈ {а₁, a₂}^*}); примеров более высоких нижних оценок временной сложности неизвестно. Емкость всякой Г. с. очевидным образом равна n; для произвольной порождающей грамматики, емкость к-рой ограничена сверху линейной функцией

f(n) = kn,

существует эквивалентная ей Г. с. (эта Г. с. может быть построена эффективно, если известно k).

Алгоритмические проблемы. Если нек-рый класс языков содержит хотя бы один НС-язык н хотя бы для одного НС-языка L₀ содержит разве лишь конечное число «почти совпадающих» с L₀ языков (языки L₁ и L₂ «почти совпадают», если их симметрич. разность (L₀ - L₂) ∪ (L₂ - L₁) конечна), то свойство принадлежать данному классу нераспознаваемо в классе Г. с. В частности, нераспознаваемы свойства быть пустым, конечным, автоматным, линейным, бесконтекстным языком, иметь пустое или конечное дополнение, совпадать с (любым) фиксированным НС-языком. Примером свойства языков, распознаваемого в классе Г. с., может служить свойство содержать (любую) фиксированную цепочку.

См. также Грамматика бесконтекстная.

А. В. Гладкий.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.