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

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


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


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

Навигация