ГРАММАТИКА ПОРОЖДАЮЩАЯ


ГРАММАТИКА ПОРОЖДАЮЩАЯ

грамматика Хомского,- один из видов формальной грамматики;представляет собой, по существу, частный случай исчисления Поста (см. Поста каноническая система). Систематич. изучение Г. п. было начато в 50-х гг. 20 в. Н. Хомскнм (N. Chomsky), к-рый указал пути ее приложения в лингвистике и выделил наиболее важные для этих приложений классы Г. п.- грамматики составляющих, грамматики бесконтекстные, грамматики автоматные;те же классы оказались особенно интересными и с чисто математич. точки зрения.

Г. п. есть упорядоченная четверка , где V и W - непересекающиеся конечные множества, наз. соответственно основным и вспомогательным алфавитами, или словарями (их элементы наз. соответственно основными, пли терминальными, и вспомогательными, или нетерминальными, символам и), - элемент , наз. начальным символом, и - конечное множество правил, имеющих вид , где - цепочки ( слова).в алфавите и не принадлежит ; Rназ. схемой грамматики. Если цепочки и предста-вимы соответственно в виде где - одно из правил грамматики Г, то говорят, что h непосредственно выводима из в (обозначение: или ). Последовательность цепочек ( ) наз. выводом из в Г, если ; число песть длина вывода. Вывод наз. полным, если и не содержит вспомогательных символов. Если существует вывод цепочки из цепочки в Г, то говорят, что выводима из в Г. Множество цепочек в основном алфавите, выводимых в Г из I, наз. языком, порождаемым грамматикой Г (обозначается через L(Г)). Две Г. п. эквивалентны, если они порождают один и тот же язык. Класс языков, порождаемых всевозможными Г. п., совпадает с классом рекурсивно перечислимых множеств цепочек.

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

Емкость грамматики Г определяется аналогично с заменой длины вывода наибольшей из длин цепочек

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

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

См. также Грамматика составляющих, Грамматика бесконтекстная, Грамматика линейная, Грамматика автоматная, Математическая лингвистика.

Лит.:[1] Гросс М., Лантен А., Теория формальных грамматик, пер. с франц., М., 1971; [2] Гладкий А. В., Формальные грамматики и языки, М., 1973; [3] Норсrоft J. Е., Ullmаn J. D., Formal languages and their relation to automata, Reading (Mass.), 1969; [4] Гладкий А. В., Диковский А. Я., в кн.: Итог" науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика, 1972, т. 10, с. 107-42; [5] Маслов А. Н., Стоцкий Э. Д., в кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика, 1975, т. 12, с. 155-87; [6] Стоцкий Э. Д., "Проблемы передачи информации", 1971, т. 7, М 1, с. 87-101; № 3, с. 87-102. А. В. Гладкий.


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

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

  • ГРАММАТИКА, ПОРОЖДАЮЩАЯ (ГЕНЕРАТИВНАЯ) — 1. Область исследований в лингвистике и психолингвистике, которая сосредоточивается на разработке набора формальных правил, с помощью которых можно объяснить язык. 2. Сам набор формальных правил. Дело в том, что грамматика рассматривается, скорее …   Толковый словарь по психологии

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

  • Грамматика формальная — (в лингвистике)         логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным… …   Большая советская энциклопедия

  • ПОРОЖДАЮЩАЯ ГРАММАТИКА — См. грамматика, порождающая …   Толковый словарь по психологии

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

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

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

  • Порождающая грамматика — Лингвистика Теоретическая лингвистика Фонетика Фонология Морфология Синтаксис Семантика Лексическая семантика Прагматика …   Википедия

  • грамматика формальная — В лингвистике: логическая система, или исчисление, задающая некоторое множество ( правильных ) цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого алфавитом или основным (терминальным)… …   Словарь лингвистических терминов Т.В. Жеребило

  • Грамматика формальная —    В лингвистике: логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным (терминальным)… …   Общее языкознание. Социолингвистика: Словарь-справочник

Книги

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


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

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

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.