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

Материал из WEGA

Версия от 19:27, 24 декабря 2009; KEV (обсуждение | вклад)

(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Перейти к навигации Перейти к поиску

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

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

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/95]

Источник — http://pco.iis.nsk.su/wega/index.php?title=Проблема_пустоты&oldid=4183