Проблема пустоты

Проблема пустоты (Empty problem) - для заданного определенного типа описания языка требуется установить, пуст ли этот язык или нет.

Эффективно решается для любого способа представления регулярных множеств, КС- языков, КЗ-языков и неразрешима для грамматик без ограничений.