Учитывая два недетерминированных конечных автомата M1 и M2 , существует ли эффективный алгоритм для определения того, является ли язык, принятый M1 , надмножеством принятого языка М2 ?
Нет, если P = NP. Если бы у вас был такой алгоритм, вы могли бы тривиально решить, были ли два NFA изоморфными (просто проверьте, является ли A надмножеством B, а B является надмножеством A), что является известной NP-трудной проблемой . Для получения более подробной информации прочитайте эту статью . У этого есть хорошая обескураживающая таблица результатов сложности.