Математическая энциклопедия - грамматика порождающая

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

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

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

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