ИСТИНА

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