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

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

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

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

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

При изучении Г. п. естественно возникают алгоритмич. проблемы. Если α - свойство языков, - нек-рый класс грамматик, и если существует алгоритм, позволяющий по любой грамматике Г ∈ распознать, обладает ли язык L(Г) свойством α, то говорят, что α распознаваемо в классе . В классе всех Г. п. ни одно нетривиальное свойство (т. е. такое, что в соответствующем классе языков есть как языки, обладающие этим свойством, так и не обладающие им) не распознаваемо. Аналогичным образом можно говорить о распознаваемых в нек-ром классе грамматик отношениях. Возникают также проблемы иного типа, напр. о существовании для данной грамматики Г алгоритма, позволяющего по любым n цепочкам x₁, ..., x_n в ее основном алфавите найти значение заданного предиката Р(L, ω₁, ..., ω_n) для L = L(Г), ω₁ = x₁, ..., ω_n = x_n. В частности, если Р(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 стб. с илл.