Хорошо известно, что проблема эквивалентности неразрешима для общих контекстно-свободных языков. Тем не менее, все доказательства этого факта, о которых я знаю, похоже, включают в себя некоторые неоднозначные контекстно-свободные грамматики. По этой причине я хотел бы спросить, известно ли, остается ли проблема неразрешимой, ограничивая себя однозначными контекстно-свободными языками. То есть, учитывая две не зависящие от контекста грамматики, которые априори предоставлены для однозначности, можно ли решить, эквивалентны они или нет?
Я нахожу эту проблему немного интригующей, так как известно, что эквивалентность разрешима для детерминированных контекстно-свободных языков, хотя этот результат далеко не тривиален ... С другой стороны, может быть какая-то простая причина неразрешимости, которой я был вид.
Ответы:
В настоящее время это открытая проблема. Как правильно указано, если это разрешимо, то можно ожидать, что доказательство будет трудным, поскольку оно обобщает известную проблему эквивалентности DPDA. С другой стороны, классические аргументы в пользу неразрешимости проблемы универсальности КЛЛ используют по своей сути неоднозначные языки, и поэтому нужны новые идеи, чтобы продемонстрировать неразрешимость.
Позвольте мне отметить, что проблема универсальности для UCFL разрешима (в PSPACE) с использованием производящих функций [1].
ССЫЛКИ
[1] Н. Хомский и М. П. Шютценбергер. Алгебраическая теория языков без контекста, компьютерное программирование и формальные системы, 1963.
источник