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