Статьи автора

АЛГОРИТМИЧЕСКИЕ СВОЙСТВА БАЗОВЫХ КАТЕГОРИАЛЬНЫХ ГРАММАТИК С ОДНОЗНАЧНЫМ ПРИСВОЕНИЕМ КАТЕГОРИЙ

Номер выпуска 1 от 23.05.2025

Работа посвящена базовым категориальным грамматикам с однозначным присвоением типов (БКГОПТ). Для данного класса рассмотрен ряд алгоритмических свойств. Доказано, что проверка для произвольного контекстно-свободного языка L того, порождается ли он некоторой грамматикой из класса БКГОПТ, является алгоритмически неразрешимой. Кроме того, доказано, что для произвольных двух БКГОПТ задача определения пустоты пересечения языков, порождаемых этими грамматиками, также алгоритмически неразрешима.

11 0