НОВОСТИ    БИБЛИОТЕКА    ЭНЦИКЛОПЕДИЯ    БИОГРАФИИ    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

ГРАММАТИКА ДОМИНАЦИОННАЯ

ГРАММАТИКА ДОМИНАЦИОННАЯ - один из видов формальной грамматики, служащий для порождения цепочек вместе с деревьями подчинения (см. Синтаксическая структура). Формально Г. д. может быть определена как грамматика бесконтекстная, у к-рой в каждом правиле, за исключением правил вида I → va, где I - начальный и a - основной символы, одно из вхождений символов в правую часть снабжено специальной меткой; при этом правая часть каждого такого правила должна содержать не менее двух вхождений символов. Система составляющих, отвечающая выводу в такой грамматике (см. Грамматика составляющих), становится иерархизованной, если считать главными те составляющие, к-рые «происходят» от помеченных вхождений символов в правые части правил. Каждой цепочке порождаемого грамматикой языка сопоставляется дерево подчинения, связанное с указанной иерархизованной системой составляющих (к-рая не обязана, вообще говоря, быть единственной). На рис. показано одно из деревьев подчинения, к-рое сопоставляет цепочке ааасbbb Г. д. с правилами I → a'Ib, I → aIb', I → c (I - начальный символ, штрих служит меткой); это дерево отвечает выводу

(I, aIb', aaIb'b', aaa'Ibb'b', aaa'cbb'b'),

здесь скобками выделены нетривиальные составляющие.

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

Простая Г. д. наз. также грамматикой зависимостей.

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

А. В. Гладкий.


Источники:

  1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.











© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'Математическая библиотека'
Рейтинг@Mail.ru