ГРАММАТИКА СОСТАВЛЯЮЩИХ это:

ГРАММАТИКА СОСТАВЛЯЮЩИХ

грамматика непосредственно составляющих, НС-грамматика, грамматика контекстная,- частный случай грамматики порождающей, когда каждое ее правило имеет вид , где - цепочки в алфавите и 0 непуста. Каждый шаг вывода в Г. с. состоит в замене одного вхождения символа Авхождением цепочки q, причем возможность замены обусловлена наличием "контекста"

Вхождения символов в q потом также могут заменяться и т. д. Таким образом, вхождение символа "развертывается" в нек-рый отрезок возникающей в результате вывода цепочки. Это дает возможность представить вывод в Г. с. с помощью дерева (дерева вывода):

напр., если грамматика имеет правила

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


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


где ПРЕДЛ, - вспомогательные символы, означающие, соответственно, "предложение", "существительное рода хв числе уи падеже г", "группа глагола в 3-м лице", "переходный глагол в 3-м лице", а символ ПРЕДЛ - начальный, приписывает предложению "Эллипс пересекает параболу" размеченную систему составляющих


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

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

Класс НС-языков замкнут относительно объединения, пересечения, умножения, усеченной итерации, подстановки; неизвестно, замкнут ли он относительно дополнения.

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


существует эквивалентная ей Г. с. (эта Г. с. может быть построена эффективно, если известно k).

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

В частности, нераспознаваемы свойства быть пустым, конечным, автоматным, линейным, бесконтекстным языком, иметь пустое или конечное дополнение, совпадать с (любым) фиксированным -языком. Примером свойства языков, распознаваемого в классе Г. с., может служить свойство содержать (любую) фиксированную цепочку.

См. также Грамматика бесконтекстная.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ГРАММАТИКА СОСТАВЛЯЮЩИХ" в других словарях:

  • Грамматика составляющих — Генеративная лингвистика …   Википедия

  • ГРАММАТИКА БЕСКОНТЕКСТНАЯ — грамматика контекстно свободная, КС грамматика, грамматика составляющих, все правила к рой имеют вид где А вспомогательный символ и непустая цепочка (так наз. бесконтекстные правила). Языки, порождаемые такими грамматиками, наз. бесконтекстными… …   Математическая энциклопедия

  • ГРАММАТИКА ПОРОЖДАЮЩАЯ — грамматика Хомского, один из видов формальной грамматики;представляет собой, по существу, частный случай исчисления Поста (см. Поста каноническая система). Систематич. изучение Г. п. было начато в 50 х гг. 20 в. Н. Хомскнм (N. Chomsky), к рый… …   Математическая энциклопедия

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

  • ГРАММАТИКА ДОМИНАЦИОННАЯ — один и видов формальной грамматики, служащий для порождения цепочек вместе с деревьями подчинения (см. Синтаксическая структура). Формально Г. д. может быть определена как грамматика бесконтекстная, у к рой; в каждом правиле, за исключением… …   Математическая энциклопедия

  • ГРАММАТИКА КАТЕГОРИАЛЬНАЯ — один из видов формальной грамматики. Т. к. может быть определена как упорядоченная четверка где конечные множества, элементы к рых наз. основными символами и элементарными категориями соответственно; Ф 0 элемент W, называемый главной категорией;… …   Математическая энциклопедия

  • ГРАММАТИКА ТРАНСФОРМАЦИОННАЯ — один из видов формальной грамматики. Г. т. предназначаются для преобразования синтаксических структур, что делает их более адекватными для описания естественного языка, чем формальные грамматики других типов, осуществляющие порождение или… …   Математическая энциклопедия

  • грамматика —    (греч.; первонач. «учение о письме»). Учение о формах речи, т. е. о звуковых выражениях отношений между понятиями, выраженными словами. Г. обычно делят на морфологию (см.), т. е. учение о формах отдельных слов, и синтаксис (см.), т. е. учение… …   Грамматический словарь: Грамматические и лингвистические термины

  • Генеративная грамматика — Эту страницу предлагается переименовать в Порождающая грамматика. Пояснение причин и обсуждение  на странице Википедия:К переименованию/16 сентября 2012. Возможно, её текущее название не соответствует нормам современного русского языка… …   Википедия

  • Универсальная грамматика — Генеративная лингвистика …   Википедия

Книги

Другие книги по запросу «ГРАММАТИКА СОСТАВЛЯЮЩИХ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»