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

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

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