特定の条件を満たすノードを高速に (対数的に) 見つけられるように、有限決定性オートマトンのノードを格納するデータ構造が必要です。問題の条件は次のとおりです。
nodeがあり、次のような
pnode を見つける必要があります。つまり、両方が最終であるか、両方が最終でなく、同じノードへの遷移があります。q(p ∈ F ≡ q ∈ F) & (∀ a : a ∈ Σ : δ(p,a) = δ(q,a))pq
遅いので、すべてのノードを通過したくありません。明らかに、トランジションを持つアルファベット文字のセットがトランジションを持つqセットと異なる場合、私が探しているノードはありません。pq
さらに、pとqが異なる数の遷移を持っている場合も、必要なqノードではありません。そこで、ファイナリティとトランジション数に応じてノードをソートするデータ構造を考えていたので、すべてのノードを調べる必要はなく、ファイナリティが同じでトランジション数が同じノードだけを調べる必要がありました。しかし、それはまだ対数ではありません。何か案は。
私はc++を使用しています。