Алгоритм преобразования очень большого NFA в DFA

У меня действительно большой недетерминированный конечный автомат, и мне нужно преобразовать его в DFA.

По большому счету я имею в виду более 40 000 штатов. До сих пор я провел несколько экспериментов и запрограммировал алгоритм по умолчанию, который выполняет поиск в таблице (как описано здесь ), но даже после оптимизации он довольно медленный и занимает очень много памяти. Я осознаю тот факт, что число штатов может расти в геометрической прогрессии, но после минимизации результирующий DFA имеет около 9 000 штатов, и это терпимо.

Итак, мой вопрос, есть ли какой-нибудь алгоритм, который был бы быстрее или более дружественным к памяти?

Ты пробовала алгоритм Бжозовского ? Время выполнения в худшем случае является экспоненциальным, но я вижу, что некоторые ссылки указывают на то, что он часто работает очень хорошо, особенно при запуске с NFA, который вы хотите преобразовать в DFA и минимизировать.

Следующая статья кажется актуальной:

• О производительности алгоритмов минимизации автоматов , Марко Алмейда, Нельма Морейра, Рожерио Рейс.

Он оценивает ряд различных алгоритмов минимизации DFA, включая их применение в вашей ситуации, когда мы начинаем с NFA и хотим преобразовать его в DFA и минимизировать его.

Как выглядит декомпозиция сильно связанных компонентов (SCC) вашего NFA (рассматривая его как ориентированный граф)? Есть ли у него много компонентов, где ни один из компонентов не слишком велик? Если так, то мне интересно, возможно ли было бы разработать алгоритм «разделяй и властвуй», в котором вы берете один компонент, конвертируете его из NFA в DFA, а затем минимизируете его, а затем заменяете оригинал новой определенной версией. Это должно быть возможно для компонентов с одним входом (где все ребра в этом компоненте ведут к одной вершине, вершине входа). Я не сразу вижу, возможно ли сделать что-то подобное для произвольных NFA, но если вы проверите, как выглядит структура SCC, то вы сможете определить, стоит ли исследовать такого рода направление или нет. ,

это, очевидно, не очень хорошо изученная проблема в смысле известных / доступных алгоритмов, отличных от оригинальной / давней стратегии «определиться с DFA / минимизировать DFA». Вы, кажется, указываете, что этап определения является проблематичным, но это, конечно, типично, учитывая, что он имеет худший случай с экспоненциальным пространством / временем. обратите внимание, что существует несколько алгоритмов минимизации DFA, которые в среднем могут существенно различаться по производительности.

это также более неофициально известно как «минимизация NFA без определения» . известно, что это сложно, в том смысле, что в принципе даже нет алгоритмов аппроксимации, если P = Pspace, как показано в этой статье:

• Минимизация NFA и регулярных выражений Грегора Грамлича, Георга Шнитгера

однако в этой статье рассматривается редко изучаемый случай некоторых алгоритмов, которые не основаны на поиске определенного DFA 1- ^го :

• Алгоритмы сокращения NFA с помощью регулярных неравенств Жан-Марк Шампарно, Фабьен Кулон

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

обратите внимание на общедоступный пакет / реализацию, которая может обрабатывать большие преобразования / минимизации NFA / DFA и т. д. в целом максимально эффективно, - это библиотека AT & T FSM .

у него есть стратегия, fsmcompactкоторой иногда может хватить:

В тех случаях, когда преобразователь или взвешенный акцептор не может быть определен или становится очень большим, может быть полезна другая оптимизация - fsmcompact. Эта операция кодирует каждую тройку входной метки, выходной метки и стоимости в одну новую метку, выполняет классическое (невзвешенное акцепторное) определение и минимизацию, а затем декодирует закодированные метки обратно в их исходные значения. Это имеет то преимущество, что оно всегда определяется и не перемещает метки вывода или затраты по путям. Недостатком является то, что результат не может быть ни детерминированным, ни минимальным.