Есть ли способ проверить, принимают ли два NFA один и тот же язык?

10

Или, по крайней мере, сгенерируйте набор строк, которые принимает один NFA, чтобы я мог передать их в другой NFA. Если я сделаю поиск по каждому пути NFA, это будет работать? Хотя это займет много времени.

algorithms regular-languages finite-automata Дункан
источник
Нет (по крайней мере, насколько нам известно). Равенство NFA является PSPACE-полным. Смотрите это обсуждение .
Шалл
@Shaull: OP не так эффективно .
frafl
@frafl: Вы правы. Я предположил, что «это займет много времени», что ОП хочет эффективное решение. Тем не менее, мой комментарий упоминает, что это в PSPACE, так что это разрешимо.
Шалл

Ответы:

10

Решение проблемы является PSPACE-полным, как отметил Шаул.

Тем не менее, оказывается, что на практике часто можно достаточно быстро определить эквивалентность NFA. Майр и Клементе (на основе экспериментальных данных) утверждают, что сложность среднего случая масштабируется квадратично . Их методы основаны на обрезке базовой маркированной переходной системы с помощью локальных аппроксимаций следовых включений.

Точно так же, как SAT является NP-полной в анализе наихудшего случая, но часто оказывается удивительно пригодным для реальных случаев, поэтому представляется вероятным, что эквивалентность NFA может быть эффективно решена для многих реальных случаев.

Андраш Саламон
источник