Математическая энциклопедия - грамматика категориальная

один из видов формальной грамматики. Т. к. может быть определена как упорядоченная четверка где конечные множества, элементы к-рых наз. основными символами и элементарными категориями соответственно; Ф 0 элемент W, называемый главной категорией;

приписывающая функция, сопоставляющая каждому основному символу конечное множество категорий выражений, образованных из элементарных категорий и синтаксич. символов по следующему правилу: 1) всякая элементарная категория есть категория; 2) если категории, то и суть категории; 3) всякая категория является таковой либо в силу 1), либо в силу 2).

Если где и то говорят, что цепочка сопоставляется грамматикой Gцепочке х. Над цепочкой категорий можно производить (вообще говоря, неоднозначную) операцию сокращения, состоящую в последовательной замене вхождений подцепочек вида или вхождениями . Если нек-рая цепочка категорий , сопоставляемая цепочке х, сокращается до одной категории , а также если , то говорят, что Gприписывает цепочке хкатегорию Язык, определяемый грамматикой G (обозначается через ), есть множество тех цепочек основных символов, к-рым G приписывает главную категорию. Категория (соответственно ) может интерпретироваться как оператор, действующий справа (слева) на Ф и дающий в результате . На этом основано использование Г. к. в лингвистике. Так, если элементарными категориями являются П "предложение" и S -"существительное", то категория может интерпретироваться как "прилагательное" (это значит, что прилагательное рассматривается как оператор, действующий на существительное слева, причем получается снова существительное, точнее группа существительного), [S П] как "непереходный глагол" и т. п. Если при этом П главная категория, то определяемый грамматикой язык состоит из "правильных предложений".

Г. к. может быть превращена в грамматику бесконтекстную;для этого нужно: а) составить вспомогательный словарь Wиз тех категорий, к-рые являются элементами или частями элементов значений приписывающей функции f; б) сделать Ф 0 начальным символом; в) взять в качестве правил всевозможные выражения вида где (соответственно ) и вида , где Это позволяет сопоставлять цепочкам определяемого грамматикой языка системы составляющих стандартным способом (см. Грамматика составляющих). Получаемый таким образом подкласс класса бесконтекстных грамматик с лингвистич. точки зрения характеризуется тем, что в них вся "грамматическая информация" содержится в словаре. Однако для любой бесконтекстной грамматики Г можно построить эквивалентную ей Г. к. G (т. е. такую, что ); при этом можно добиться, чтобы значения приписывающей функции G содержали лишь категории вида и ], где А, В, С - элементарные категории. Имеются также простые и содержательно естественные способы получения из Г. к. грамматики доминационной.

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

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985