正規言語の NFA から最小限の DFA に移行する方法はよく知られています。ただし、DFA には指数関数的に多くの状態が含まれる場合があります。
私が必要としているのは、NFA を減らす方法であり、NFA を再び与えますが、状態の数は少なくなります。結果が決定論的である必要はありませんが、認識された言語を維持しながらできるだけ小さくしたいと思います (おそらく完全に最適というわけではありませんが、小さいほど良いです)。
この問題に最適なアルゴリズムは何ですか? または、おそらく「最高」ではなく、少なくとも「非常に効率的に実装するのが最も簡単」ですか？それとも、自分で適切な情報源を見つけることができるように、問題によく知られている名前がありますか?