Грамматика Доминационная

один и" видов формальной грамматики, служащий для порождения цепочек вместе с деревьями подчинения (см. Синтаксическая структура). Формально Г. Д. Может быть определена как грамматика бесконтекстная, у к-рой. В каждом правиле, за исключением правил вида , где - начальный и а - основной символы, одно из вхождений символов в правую часть снабжено специальной мет кой. При этом правая часть каждого такого правила должна содержать не менее двух вхождений символов. Система составляющих, отвечающая выводу в такой грамматике (см. Грамматика составляющих), становится иерархнзованной, если считать главными те составляющие, к-рые "происходят" от помеченных вхождений символов в правые части правил. Каждой цепочке порождаемого грамматикой языка сопоставляется дерево подчинения, связанное с указанной иерархнзованной системой составляющих (к-рая не обязана, вообще говоря, быть единственной).

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

Простая Г. Д. Наз. Также грамматикой зависимостей. Лит.:[1] Белецкий М. И., "Кибернетика", 1967, № 4, с. 90-7. [2] Гладкий А. В., Формальные грамматики и языки, М., 1973. А. В. Гладкий.