ГРАММАТИКА ПОРОЖДАЮЩАЯ

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

Осн. классы Г. п. выделяются в зависимости от ограничений, налагаемых на вид синтаксических правил. В грамматике составляющих (иначе — непосредственно составляющих) синтаксические правила имеют вид ; в бесконтекстной, или контекстно-свободной грамматике: в автоматной грамматике (или грамматике с конечным числом состояний): или . Здесь а обозначает основной символ, А и В — вспомогательные, цепочки основных и вспомогательных символов, причем не пуста. Очевидно, что в указанной последовательности классов Г. п. каждый класс является частью предыдущего. Языки, порождаемые Г. п. перечисленных классов, наз. соответственно языками непосредственно составляющих, бесконтекстными и автоматными. В грамматиках составляющих на каждом шаге вывода заменяется только один символ, поэтому в них с каждым выводом предложения ассоциируется т. н. дерево вывода, строящееся следующим образом. Корень дерева соответствует начальному символу. Каждому символу цепочки, на которую заменяется начальный символ на первом шаге вывода, ставится в соответствие узел дерева и к нему проводится ветвь от корня. Для тех из полученных узлов, которые помечены вспомогательными символами, строится аналогичная конструкция и т. д.

Каждое дерево вывода, рассматриваемое как дерево составляющих предложения, задает на нем систему составляющих (для приведенного выше примера дерево вывода указано на рис. 1; соответствующая система составляющих состоит из цепочек . Эта особенность грамматик составляющих делает их важным инструментом для описания естественных и искусственных языков. Именно грамматики составляющих и их частные случаи являются одним из осн. объектов изучения математич. лингвистики.

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

Если при построении некоторого предложения используется правило указанного вида, то в дереве вывода от узла, помеченного символом А, идут ветви к узлам, помеченным символами символ а наз. главным в составляющей А (т. е. составляющей, соответствующей узлу с пометкой А), и по определению считается, что он управляет главными символами составляющих . Грамматика нашего примера — грамматика зависимостей, и указанный вывод задает отношение управления (рис. 2). Имеются также разновидности Г. п., в которых для порождаемых предложений задаются как системы составляющих, так и отношения управления.

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

Основы теории Г. п. были разработаны в 1950-60-х гг. (в основном в трудах амер. лингвиста Н. Хомского) как формальный аппарат для описания естественных и искусственных языков в связи с внутренними потребностями лингвистики и с решением языковых задач на ЭВМ.

Среди направлений математического исследования Г. п. выделяют два: сравнение различных классов Г. п. и исследование разрешимости алгоритмических проблем. Среди перечисленных классов языков (языки, порождаемые Г. п. общего вида; языки непосредственно составляющих; бесконтекстные; автоматные) каждый последующий существенно шире, чем предыдущий. Классы языков, порождаемых грамматиками зависимостей и категориальными, совпадают с классом бесконтекстных языков. Класс бесконтекстных грамматик обладает большими возможностями для построения описаний структуры (для бесконтекстной грамматики может не существовать сильно эквивалентной ей грамматики зависимостей или категориальной).

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

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

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

Кроме перечисленных направлений матем. исследований Г. п., можно указать следующие вопросы: распознавание порождаемых языков с помощью автоматов с магазинной памятью; изучение сложности вывода в Г. п.; поиск классов Г. п., занимающих по «порождающей силе» промежуточные места в описанной иерархии Г. п.; связь Г. п. с грамматиками распознающими; управление выводами в Г. п. и пр. (см. также. Лингвистика математическая).

Практическое применение аппарат Г. п. находит гл. образом при создании языков искусственных и в работах по машинному переводу. Большинство из создаваемых в настоящее время искусственных языков задается именно с помощью Г. п., причем чаще всего — бесконтекстных грамматик. Так, стандартные описания АЛГОЛ-60 и др. языков программирования по существу являются Г. п. Использование Г. п. в автоматическом машинном переводе было вызвано большими трудностями синтаксического анализа предложения. Алгоритм синтаксического анализа для языка, порождаемого Г. п., часто оказывается простым и легко обозримым. Большинство групп, работающих над автоматическим переводом и смежными проблемами, в той или иной мере используют моделирование естественного языка с помощью Г. п. В работах, ведущихся в СССР, используются Г. п., близкие к грамматикам зависимостей; в США — близкие к грамматикам составляющих. См. также Ингве гипотеза. Лит.: Гладкий А. В., Мельчук И. А. Элементы математической лингвистики. М., 1969 [биб-лиогр. с. 188—192]; Хомский Н. Формальные свойства грамматик. В кн.: Кибернетический сборник: Новая серия, в. 2. М., 1966; Фитиалов С. Я. Об эквивалентности грамматик НС и грамматик зависимостей. Проблемы структурной лингвистики. 1967. М., 1968; Гладкий А. В. Формальные грамматики и языки. М., 1973 [библиогр. с. 349—356]; Гинзбург С. Математическая теория контекстно-свободных языков. Пер. с англ. М., 1970 [библиогр. с. 310—319].