Это известно, как каждый добирается от NFA для регулярного языка к минимальному DFA. Однако DFA мог бы иметь экспоненциально большее число состояний.
То, в чем я нуждаюсь, является способом уменьшить NFA, давая снова NFA, но с меньшим числом состояний. T.i. Мне не нужен результат, чтобы быть детерминированным, но я хотел бы, чтобы он был как можно меньше при сохранении распознанного языка (возможно, не абсолютно оптимальный, но чем меньший, тем лучше).
Каковы лучшие алгоритмы для этой проблемы? Или возможно не "лучшее", но по крайней мере "самое легкое для реализации с неплачевной эффективностью"? Или проблема имеет известное имя так, чтобы я мог найти хорошие источники информации сам?
Я считаю, что проблема также известна как минимизация NFA. Я считаю, что в целом это NP-сложно.
Одним из плодотворных подходов может быть минимизация бисимуляции [Paige, Tarjan 1987] и последующие производные.
В этой презентации есть некоторые заметки о разрешимости проблемы, а также ссылки на некоторые подходы с разъяснением их относительных достоинств.