Грамматика порождающая

грамматика Хомского,- один из видов формальной грамматики;представляет собой, по существу, частный случай исчисления Поста (см. Поста каноническая система). Систематич. изучение Г. п. было начато в 50-х гг. 20 в. Н. Хомскнм (N. Chomsky), к-рый указал пути ее приложения в лингвистике и выделил наиболее важные для этих приложений классы Г. п.- грамматики составляющих, грамматики бесконтекстные, грамматики автоматные;те же классы оказались особенно интересными и с чисто математич. точки зрения. Г. п. есть упорядоченная четверка [img: http://localhost:8080/file/010427-31.jpg], где V и W - непересекающиеся конечные множества, наз. соответственно основным и вспомогательным алфавитами, или словарями (их элементы наз. соответственно основными, пли терминальными, и вспомогательными, или нетерминальными, символам и), [img: http://localhost:8080/file/010427-32.jpg] - элемент [img: http://localhost:8080/file/010427-33.jpg], наз. начальным символом, и [img: http://localhost:8080/file/010427-34.jpg] - конечное множество правил, имеющих вид [img: http://localhost:8080/file/010427-35.jpg], где [img: http://localhost:8080/file/010427-36.jpg] - цепочки (слова).в алфавите [img: http://localhost:8080/file/010427-37.jpg] и [img: http://localhost:8080/file/010427-38.jpg] не принадлежит [img: http://localhost:8080/file/010427-39.jpg]; Rназ. схемой грамматики. Если цепочки [img: http://localhost:8080/file/010427-40.jpg] и [img: http://localhost:8080/file/010427-41.jpg] предста-вимы соответственно в виде [img: http://localhost:8080/file/010427-42.jpg] где [img: http://localhost:8080/file/010427-43.jpg] - одно из правил грамматики Г, то говорят, что h непосредственно выводима из [img: http://localhost:8080/file/010427-44.jpg] в [img: http://localhost:8080/file/010427-45.jpg] (обозначение: [img: http://localhost:8080/file/010427-46.jpg] или [img: http://localhost:8080/file/010427-47.jpg]). Последовательность цепочек ([img: http://localhost:8080/file/010427-48.jpg]) наз. выводом [img: http://localhost:8080/file/010427-49.jpg] из [img: http://localhost:8080/file/010427-50.jpg] в Г, если [img: http://localhost:8080/file/010427-51.jpg]; число песть длина вывода. Вывод наз. полным, если [img: http://localhost:8080/file/010427-52.jpg] и [img: http://localhost:8080/file/010427-53.jpg] не содержит вспомогательных символов. Если существует вывод цепочки [img: http://localhost:8080/file/010427-54.jpg] из цепочки [img: http://localhost:8080/file/010427-55.jpg] в Г, то говорят, что [img: http://localhost:8080/file/010427-56.jpg] выводима из [img: http://localhost:8080/file/010427-57.jpg] в Г. Множество цепочек в основном алфавите, выводимых в Г из I, наз. языком, порождаемым грамматикой Г (обозначается через L(Г)). Две Г. п. эквивалентны, если они порождают один и тот же язык. Класс языков, порождаемых всевозможными Г. п., совпадает с классом рекурсивно перечислимых множеств цепочек. Для оценки сложности вывода в Г. п. используются так наз. сигнализирующие функции, важнейшими из к-рых являются временная сложность и емкость. Временная сложность грамматики Г - это функция натурального аргумента [img: http://localhost:8080/file/010427-58.jpg], значение к-рой для каждого правно наименьшему из чисел k, обладающих тем свойством, что для любой цепочки [img: http://localhost:8080/file/010427-59.jpg] такой, что [img: http://localhost:8080/file/010427-60.jpg] ([img: http://localhost:8080/file/010427-61.jpg] - длина [img: http://localhost:8080/file/010427-62.jpg]), существует вывод Dэтой цепочки из начального символа Г, длина к-рого не превосходит [img: http://localhost:8080/file/010427-63.jpg]; если не существует цепочек хтаких, что [img: http://localhost:8080/file/010427-64.jpg] Емкость [img: http://localhost:8080/file/010427-65.jpg] грамматики Г определяется аналогично с заменой длины вывода [img: http://localhost:8080/file/010427-66.jpg] наибольшей из длин цепочек [img: http://localhost:8080/file/010427-67.jpg] Если [img: http://localhost:8080/file/010427-68.jpg] - нек-рое множество полных выводов в грамматике Г и [img: http://localhost:8080/file/010427-69.jpg] - множество заключительных цепочек выводов, принадлежащих [img: http://localhost:8080/file/010427-70.jpg], то [img: http://localhost:8080/file/010427-71.jpg]. Если при этом [img: http://localhost:8080/file/010427-72.jpg] задано эффективно, то говорят, что задан нек-рый способ управления выводом в Г. Изучение способов управления выводом существенно для приложений, так как возможность использовать не произвольные, а лишь нек-рые определенные выводы лучше отвечает ситуации, имеющей место в естественном языке. Управление выводом может задаваться, в частности, наложением ограничений на последовательности применяемых в выводе правил (напр., множество таких "допустимых" последовательностей правил может само порождаться нек-рой Г. п. Г'; в этом случае язык определяется упорядоченной парой Г. п. [img: http://localhost:8080/file/010427-73.jpg], к-рую наз. обобщенной грамматикой), или на вид входящих в выводы цепочек, или к.-л. более сложным способом (напр., применяемое на очередном шаге правило может зависеть от вида цепочки, полученной на предыдущем шаге). При изучении Г. п. естественно возникают алгорит-мич. проблемы. Если [img: http://localhost:8080/file/010427-74.jpg] - свойство языков, [img: http://localhost:8080/file/010427-75.jpg] - нек-рый класс грамматик, и если существует алгоритм, позволяющий по любой грамматике [img: http://localhost:8080/file/010427-76.jpg] распознать, обладает ли язык [img: http://localhost:8080/file/010427-77.jpg] свойством [img: http://localhost:8080/file/010427-78.jpg], то говорят, что [img: http://localhost:8080/file/010427-79.jpg] распознаваемо в классе [img: http://localhost:8080/file/010427-80.jpg] В классе всех Г. п. ни одно нетривиальное свойство (т. е. такое, что в соответствующем классе языков есть как языки, обладающие этим свойством, так и не обладающие им) не распознаваемо. Аналогичным образом можно говорить о распознаваемых в нек-ром классе грамматик отношениях. Возникают также проблемы иного типа, напр, о существовании для данной грамматики Г алгоритма, позволяющего по любым п цепочкам [img: http://localhost:8080/file/010427-81.jpg] в ее основном алфавите найти значение заданного предиката [img: http://localhost:8080/file/010427-82.jpg] для [img: http://localhost:8080/file/010427-83.jpg], [img: http://localhost:8080/file/010427-84.jpg] [img: http://localhost:8080/file/010427-85.jpg] В частности, если [img: http://localhost:8080/file/010427-86.jpg] означает [img: http://localhost:8080/file/010427-87.jpg], то речь идет об алгоритме для распознавания принадлежности произвольной цепочки языку [img: http://localhost:8080/file/010427-88.jpg]. Если для грамматики Г такой алгоритм есть, существенное значение имеет вопрос о сложности его работы, или, как говорят, о сложности распознавания языка [img: http://localhost:8080/file/010427-89.jpg]. См. также Грамматика составляющих, Грамматика бесконтекстная, Грамматика линейная, Грамматика автоматная, Математическая лингвистика.