Базовые категориальные грамматики с однозначным присвоением типов и одним делением

Понятие базовой категориальной грамматики восходит к работам Айдукевича (1934) и Бар-Хиллела (1953). В базовых категориальных грамматиках каждая буква алфавита сопоставляется нескольким типам (категориям), а слово принадлежит языку, если хотя бы для одного выбора этих типов выводима соответствующая секвенция, т.е. последовательность типов может быть преобразована к фиксированному целевому типу. Известно, что любая контекстно-свободная грамматика эквивалентна некоторой базовой категориальной грамматике, более того, с определенными ограничениями на типы (форма Грейбах). Верно и обратное, любая базовая категориальная грамматика эквивалентна некоторой контекстно-свободной грамматике. Данный доклад посвящен базовым категориальным грамматикам с однозначным присвоением типов. Как уже было обозначено, множество языков, заданных данными грамматиками, лежит внутри множества контекстно-свободных языков. Для данного класса грамматик существуют естественные необходимые условия регулярности порождаемого языка. Данные необходимые условия дают полезные результаты в случае одного деления в грамматиках.