Проблема пустоты
Перейти к навигации
Перейти к поиску
Проблема пустоты (Empty problem) - для заданного определенного типа описания языка требуется установить, пуст ли этот язык или нет.
Эффективно решается для любого способа представления регулярных множеств, КС-языков, КЗ-языков и неразрешима для грамматик без ограничений.
Литература
[Ахо-Хопкрофт-Ульман],
[Касьянов/95]