Аноним

Проблема принадлежности: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Проблема принадлежности''' (''[[Membership problem]]'') -
'''Проблема принадлежности''' (''[[Membership problem]]'')
для заданного определенного
для заданного определенного
типа описания языка и заданной [[цепочка|цепочки]] <math>\omega</math>
типа описания языка и заданной [[цепочка|цепочки]] <math>\,\omega</math>
требуется установить, принадлежит ли
требуется установить, принадлежит ли
цепочка <math>\omega</math> этому языку или нет.
цепочка <math>\,\omega</math> этому языку или нет.


Эффективно решается для ''[[регулярные выражения|регулярных выражений]]'' и
Эффективно решается для ''[[регулярные выражения|регулярных выражений]]'' и
''неразрешима'' для ''[[КС-Грамматика|КС-грамматик]]''.
''неразрешима'' для ''[[КС-Грамматика|КС-грамматик]]''.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],  
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.


[Касьянов/95]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.