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