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