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

Материал из WikiGrapp
Версия от 16:16, 24 декабря 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Проблема пустоты''' (''Empty problem'') - для заданного определенного типа описани...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

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

Литература

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

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