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