7

非決定論的有限状態オートマトン (NFA) を決定論的有限状態オートマトン (DFA) に変換するプログラムに取り組んでいます。これを行うには、イプシロン遷移を持つ NFA 内のすべての状態のイプシロン クロージャを計算する必要があります。私はすでにこれを行う方法を考え出していますが、私が最初に考えるのは、通常、何かを行う最も効率の悪い方法であると常に想定しています。

単純なイプシロン クロージャを計算する方法の例を次に示します。

遷移関数の入力文字列: 形式は startState、symbol = endState です。

EPS はイプシロン遷移です

1、EPS = 2

新しい状態 { 12 } になります

明らかに、これは非常に単純な例です。任意の数の状態から任意の数のイプシロン遷移を計算できる必要があります。この目的のために、私の解決策は、イプシロン遷移がある状態を見て、指定された状態のイプシロン クロージャーを計算する再帰関数です。その状態にイプシロン遷移がある場合、関数は for ループ内で、イプシロン遷移と同じ数だけ再帰的に呼び出されます。これで作業は完了しますが、おそらく最速の方法ではありません。だから私の質問はこれです:Javaでイプシロンクロージャーを計算する最速の方法は何ですか?

4

4 に答える 4

4

エッジがエピルソン遷移であるグラフに対する深さ優先検索 (または幅優先検索 - 実際には問題ではありません)。つまり、クロージャーに既に追加した状態を効率的に追跡する場合、ソリューションは最適です。

于 2011-02-14T10:33:50.620 に答える
3

JFLAPはこれを行います。それらのソース、具体的には ClosureTaker.java を確認できます。これは深さ優先検索 (Peter Taylor が提案したもの) であり、JFLAP がそれを使用しているため、これが最適に近いソリューションであると思います。

于 2011-02-14T18:45:27.260 に答える
0

アルゴリズムの本を調べましたか？しかし、大幅に優れたアプローチが見つかるとは思えません。ただし、このアルゴリズムの実際のパフォーマンスは、グラフの実装に使用する具体的なデータ構造に大きく依存する場合があります。また、グラフを簡略化する順序に応じて作業を共有できます。イプシロン接続され、2 つの異なるノードから参照されるサブグラフについて考えてみましょう。これが最適な方法で実行できるかどうか、またはヒューリスティックに頼る必要があるかどうかはわかりません。

アルゴリズムに関する文献をスキャンします。

于 2011-02-14T11:21:26.787 に答える