Аннотация:
Работа посвящена базовым категориальным грамматикам с однозначным присвоением типов (БКГОПТ). Для данного класса рассмотрен ряд алгоритмических свойств. Доказано, что проверка для произвольного контекстно-свободного языка $L$ того, порождается ли он некоторой грамматикой из класса БКГОПТ, является алгоритмически неразрешимой. Кроме того, доказано, что для произвольных двух БКГОПТ задача определения пустоты пересечения языков, порождаемых этими грамматиками, также алгоритмически неразрешима.
Ключевые слова:
формальные грамматики, категориальные грамматики, единственность назначения категорий.
УДК:510.6
Статья представлена к публикации:А. Л. Семёнов Поступило: 29.04.2025 После доработки: 22.05.2025 Принято к публикации: 23.05.2025
