Проблема принадлежности

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

Проблема принадлежности (Membership problem) - для заданного определенного типа описания языка и заданной цепочки </math>\omega[math]\displaystyle{ требуется установить, принадлежит ли цепочка }[/math]\omega<math> этому языку или нет.

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

Литература

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

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