ГРАММАТИКА КАТЕГОРИАЛЬНАЯ

ГРАММАТИКА КАТЕГОРИАЛЬНАЯ - один из видов формальной грамматики. Г. к. может быть определена как упорядоченная четверка G = 〈V, W, Ф₀, f〉, где V и W - конечные множества, элементы к-рых наз. основными символами и элементарными категориями соответственно; Ф₀ - элемент W, называемый главной категорией; f - приписывающая функция, сопоставляющая каждому основному символу конечное множество категорий - выражений, образованных из элементарных категорий и синтаксич. символов [,], \, / по следующему правилу: 1) всякая элементарная категория есть категория; 2) если Ф и Ψ - категории, то [Ф\Ψ] («Ф под Ψ») и [Ф/Ψ] («Ф над Ψ») суть категории; 3) всякая категория является таковой либо в силу 1), либо в силу 2).

Если x = a₁, ..., a_k, где a_i ∈ V, и Ф_i ∈ f(а_i), i = 1, ..., k, то говорят, что цепочка Ф₁ ... Ф_k сопоставляется грамматикой G цепочке х. Над цепочкой категорий можно производить (вообще говоря, неоднозначную) операцию сокращения, состоящую в последовательной замене вхождений подцепочек вида Ф[Ф\Ψ] или [Ψ/Ф]Ф вхождениями Ψ. Если нек-рая цепочка категорий ξ, сопоставляемая цепочке х, сокращается до одной категории в, а также если ξ = Θ, то говорят, что G приписывает цепочке х категорию Θ. Язык, определяемый грамматикой G (обозначается через L(G)), есть множество тех цепочек основных символов, к-рым G приписывает главную категорию. Категория [Ф\Ψ] (соответственно [Ψ/Ф]) может интерпретироваться как оператор, действующий справа (слева) на Ф и дающий в результате Ψ. На этом основано использование Г. к. в лингвистике. Так, если элементарными категориями являются П - «предложение» и S - «существительное», то категория [S/S] может интерпретироваться как «прилагательное» (это значит, что прилагательное рассматривается как оператор, действующий на существительное слева, причем получается снова существительное, точнее группа существительного), [S\П] - как «непереходный глагол» и т. п. Если при этом П - главная категория, то определяемый грамматикой язык состоит из «правильных предложений».

Г. к. может быть превращена в грамматику бесконтекстную; для этого нужно: а) составить вспомогательный словарь W' из тех категорий, к-рые являются элементами или частями элементов значений приписывающей функции f; б) сделать Ф₀ начальным символом; в) взять в качестве правил всевозможные выражения вида Ψ → Ф[Ф\Ψ] и Ψ → [Ψ/Ф]Ф, где [Ф\Ψ] ∈ W' (соответственно [Ψ/Ф] ∈ W') и вида Ф → a, где Ф ∈ f(а). Это позволяет сопоставлять цепочкам определяемого грамматикой языка системы составляющих стандартным способом (см. Грамматика составляющих). Получаемый таким образом подкласс класса бесконтекстных грамматик с лингвистич. точки зрения характеризуется тем, что в них вся «грамматическая информация» содержится в словаре. Однако для любой бесконтекстной грамматики Г можно построить эквивалентную ей Г. к. G (т. е. такую, что L(G) = L(Г)); при этом можно добиться, чтобы значения приписывающей функции G содержали лишь категории вида A, [A\B] и [A\[B\С]], где А, В, С - элементарные категории. Имеются также простые и содержательно естественные способы получения из Г. к. грамматики доминационной.

Лит.: [1] Bar-Hillel L., Gaifman С., Shamir Е., «Bull. Res. Council Israel», 1960, sec. F, v. 9, № 1, p. 155-66; [2] Бeлeцкий М. И., «Кибернетика», 1969, № 4, с. 129-35; № 5, с. 10-14; [3] Гладкий А. В., Формальные грамматики и языки, М., 1973.

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

Источники:

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