Расширения контекстно-свободных и категориальных грамматик

Речь пойдёт о двух формальных системах, изобретённых для формализации грамматики естественных языков. Первая – контекстно-свободные грамматики – восходит к работам Н. Хомского, вторая – категориальные грамматики – К. Айдукевича и И. Ламбека. Известно [М. Пентус 1992], что оба формализма задают один и тот же класс формальных языков, и оказывается, что он слишком беден для описания лингвистических феноменов. В докладе будет рассказано о нескольких подходах к расширению этих формализмов с сохранением их хороших свойств, прежде всего алгоритмических.