Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




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

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

Г. п. есть упорядоченная четверка Г = 〈V, W, I, R〉, где V и W - непересекающиеся конечные множества, наз. соответственно основным и вспомогательным алфавитами, или словарями (их элементы наз. соответственно основными, или терминальными, и вспомогательными, или нетерминальными, символами), I - элемент W, наз. начальным символом, и R - конечное множество правил, имеющих вид φ → ψ, где φ и ψ - цепочки (слова) в алфавите V ∪ W и → не принадлежит V ∪ W; R наз. схемой грамматики. Если цепочки ξ и η представимы соответственно в виде ξ = χ1φχ2, η = χ1ψχ2, где φ → ψ - одно из правил грамматики Г, то говорят, что η непосредственно выводима из ξ в Г (обозначение: ξ ⊨Г η или ξ ⊨ η). Последовательность цепочек (ω0, ..., ωn) наз. выводом ωn из ω1 в Г, если ∀i, 1 ≤ i ≤ n, (ωi-1Г ωi); число n есть длина вывода. Вывод наз. полным, если ω0 = I и ωn не содержит вспомогательных символов. Если существует вывод цепочки η из цепочки ξ в Г, то говорят, что η выводима из ξ в Г. Множество цепочек в основном алфавите, выводимых в Г из I, наз. языком, порождаемым грамматикой Г (обозначается через L(Г)). Две Г. п. эквивалентны, если они порождают один и тот же язык. Класс языков, порождаемых всевозможными Г. п., совпадает с классом рекурсивно перечислимых множеств цепочек.

Для оценки сложности вывода в Г. п. используются так наз. сигнализирующие функции, важнейшими из к-рых являются временная сложность и емкость. Временная сложность грамматики Г - это функция натурального аргумента τГ(n), значение к-рой для каждого n равно наименьшему из чисел k, обладающих тем свойством, что для любой цепочки х ∈ L(Г) такой, что |x| ≤ n (|x| - длина х), существует вывод D этой цепочки из начального символа Г, длина к-рого не превосходит k; если не существует цепочек х таких, что х ∈ L(Г) и |x| ≤ n, то τГ(n) = 0. Емкость σГ(n) грамматики Г определяется аналогично с заменой длины вывода D = (ω0, ..., ωs) наибольшей из длин цепочек ωi, i = 0, 1, ..., s.

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

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

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

Лит.: [1] Гросс М., Лантен А., Теория формальных грамматик, пер. с франц., М., 1971; [2] Гладкий А. В., Формальные грамматики и языки, М., 1973; [3] Норсrоft J. Е., Ullman 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.

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


Источники:

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




ИНТЕРЕСНО:

Зачем математики ищут простые числа с миллионами знаков?

Задача построения новых оснований математики - унивалентные основания

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru