Задача о неэквивалентности регулярных выражений

Материал из WikiGrapp
Перейти к:навигация, поиск

Задача о неэквивалентности регулярных выражений (Regular expression nonequivalence problem) — одна из основных \mathcal NP-полных задач. Формулируется следующим образом.

У с л о в и е. Заданы конечный алфавит \Sigma и два регулярных выражения E_1 и E_2 над алфавитом \Sigma.

В о п р о с. Верно ли, что E_1 и E_2 представляют различные языки?

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.