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

— разновидность грамматики формальной. Г. к. использует конструируемые спец. способом имена-категории для обозначения типов слов и словосочетаний описываемого языка. Сопоставление категорий с синтаксическими типами, которые выделяют из смысловых соображений для конкретных естественных или искусственных языков, проводится следующим образом. Определенные типы, считающиеся элементарными (исходными), обозначаются символами (буквами), которые наз. элементарными категориями. Если имеется синтаксический тип, все словосочетания которого, будучи присоединенными слева к словосочетаниям типа, обозначенного L, дают словосочетания типа, обозначенного К, то первый из трех названных типов получает обозначение . Аналогично, синтаксический тип, который, присоединяясь справа к L, дает К, получает обозначение .

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

присоединяясь к С слева, — С; наречие, присоединяясь к глаголу слева, — глагольную группу (пример намеренно упрощен; в действительности описание естественного языка несравненно сложнее).

Формально Г. к. и описываемый ею язык задаются следующим образом. Г. к. определяется как четверка компонент: 1) словарь (т. е. конечное множество) основных символов; 2) словарь элементарных категорий; 3) выделенная элементарная категория, называемая главной; 4) приписывающая функция, ставящая в соответствие каждому основному символу конечное число категорий, образованных из элементарных. Основные символы интерпретируются как слова языка; элементарные категории — как названия синтаксических типов слов и словосочетаний, принимаемых за исходные. Главная категория интерпретируется как символ предложения, приписывающая функция — как задание для каждого слова всех его синтаксических типов. Наличие у одного слова или словосочетания нескольких синтаксических типов соответствует синтаксической омонимии. Приписывающая функция ставит в соответствие каждой цепочке основных символов конечное множество цепочек категорий, состоящее из всевозможных цепочек вида , где одна из категорий, сопоставленных . Непосредственным сокращением цепочки категорий наз. замена в ней соседней пары категорий, имеющей вид или категорией К (непосредственное сокращение категорий аналогично сокращению дробей, но с той разницей, что для категорий различаются левые и правые «знаки дроби» и соответственно сокращения). Цепочка категорий сокращается до цепочки категорий если имеется последовательность цепочек, начинающаяся цепочкой и кончающаяся цепочкой . В этой последовательности каждая последующая цепочка получается непосредственным сокращением предыдущей. Цепочка основных символов наз. предложением, если хотя бы одна из сопоставленных ей цепочек категорий сокращается до главной категории. Множество предложений наз. языком, допускаемым (или описываемым) данной Г. к. Напр., при задании фрагмента русского языка с помощью Г. к., описанным выше способом, цепочке слов «старый человек спит» сопоставляется цепочка категорий ; она непосредственно сокращается до цепочки , а — до главной категории Пр; поэтому указанная цепочка слов является предложением.

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

Класс языков, допускаемых Г. к., совпадает с классом языков, порождаемых грамматиками бесконтекстными. Понятие «Г. к.» было введено в 50-х годах 20 ст. для построения алгоритма синтаксического анализа естественных языков. Однако аппарат Г. к. мало пригоден для практического моделирования естественных языков и теперь используется почти исключительно в теоретических исследованиях.