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

один и" видов формальной грамматики, служащий для порождения цепочек вместе с деревьями подчинения (см. Синтаксическая структура). Формально Г. д. может быть определена как грамматика бесконтекстная, у к-рой; в каждом правиле, за исключением правил вида [img: http://localhost:8080/file/010426-224.jpg], где [img: http://localhost:8080/file/010426-225.jpg] - начальный и а - основной символы, одно из вхождений символов в правую часть снабжено специальной мет кой; при этом правая часть каждого такого правила должна содержать не менее двух вхождений символов. Система составляющих, отвечающая выводу в такой грамматике (см. Грамматика составляющих), становится иерархнзованной, если считать главными те составляющие, к-рые "происходят" от помеченных вхождений символов в правые части правил. Каждой цепочке порождаемого грамматикой языка сопоставляется дерево подчинения, связанное с указанной иерархнзованной системой составляющих (к-рая не обязана, вообще говоря, быть единственной). На рис. показано одно из деревьев подчинения, к-рое сопоставляет цепочке [img: http://localhost:8080/file/010426-227.jpg] Г. д. с правилами [img: http://localhost:8080/file/010426-228.jpg] начальный символ, штрих служит меткой); это дерево отвечает выводу [img: http://localhost:8080/file/010426-229.jpg] здесь скобками выделены нетривиальные составляющие. [img: http://localhost:8080/file/010426-226.jpg] Важнейший частный класс Г. д.- так наз. простые Г. д., у к-рых в правых частях правил помечаются только основные символы (грамматика рассмотренного примера - простая). Для всякой простой Г. д. существует такое натуральное число k, что в каждом дереве подчинения, к-рое эта Г. д. сопоставляет к.-л. цепочке, ни из одной вершины не выходит более kдуг. Обратно, для всякой Г. д., обладающей указанным: свойством, существует эквивалентная ей простая Г. д. такая, что для кажд(и цепочки множества деревьев подчинения, приписываемых ей обеими грамматиками, совпадают. Простая Г. д. наз. также грамматикой зависимостей.