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

Один и" видов формальной грамматики, служащий для порождения цепочек вместе с деревьями подчинения (см. Синтаксическая структура). Формально Г. д. может быть определена как грамматика бесконтекстная, у к-рой; в каждом правиле, за исключением правил вида , где — начальный и а — основной символы, одно из вхождений символов в правую часть снабжено специальной мет кой; при этом правая часть каждого такого правила должна содержать не менее двух вхождений символов. Система составляющих, отвечающая выводу в такой грамматике (см. Грамматика составляющих), становится иерархнзованной, если считать главными те составляющие, к-рые "происходят" от помеченных вхождений символов в правые части правил. Каждой цепочке порождаемого грамматикой языка сопоставляется дерево подчинения, связанное с указанной иерархнзованной системой составляющих (к-рая не обязана, вообще говоря, быть единственной). На рис. показано одно из деревьев подчинения, к-рое сопоставляет цепочке Г. д. с правилами начальный символ, штрих служит меткой); это дерево отвечает выводу здесь скобками выделены нетривиальные составляющие. Важнейший частный класс Г. д.- так наз. простые Г. д., у к-рых в правых частях правил помечаются только основные символы (грамматика рассмотренного примера — простая). Для всякой простой Г. д. существует такое натуральное число k, что в каждом дереве подчинения, к-рое эта Г. д. сопоставляет к.-л. цепочке, ни из одной вершины не выходит более kдуг. Обратно, для всякой Г. д., обладающей указанным: свойством, существует эквивалентная ей простая Г. д. такая, что для кажд( и цепочки множества деревьев подчинения, приписываемых ей обеими грамматиками, совпадают. Простая Г. д. наз. также грамматикой зависимостей. Лит.:[1] Белецкий М. И., "Кибернетика", 1967, № 4, с. 90-7; [2] Гладкий А. В., Формальные грамматики и языки, М., 1973. А. В. Гладкий.