Категориальные грамматики Ламбека

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