java.util.Setを使用してJavaでDFAの状態遷移を実装できますか

Question

学習演習（およびブログ資料）として公式定義にできるだけ近いDFAを実装しています

定義にセットが含まれるjava.util.Setを使用する予定でした。

定義には、正当な状態遷移を定義するためのタプルのセットが含まれます。（state、symbol）-<！> gt; nextState。

メンバーstate、symbol、nextStateを持つTransitionクラスがあります。 equals（）とhashCode（）を実装して、2つの遷移が状態とシンボルで一致する場合に等しいことを示します。次に、遷移インスタンスのjava.util.Setがあります。

処理アルゴリズムでは、次のシンボルを読み取ったときの現在の状態があります。これらの2つを使用して遷移オブジェクトを構築し、セットから一致する遷移を引き出すと予想しました。これにより、次の状態がわかり、反復することができます。

しかし、今後使用するためにjava.util.Setのメンバーを抽出する方法はありません。 （Object o）は削除できますが、ブール値を返すだけです。

何が間違っているのですか？

Answer 1

Setは、おそらくこれに使用したいものではありません。 List <！> lt;を使用することをお勧めします。 Transition <！> gt ;、またはMap <！> lt; State、List <！> lt;遷移<！> gt; <！> gt;。実際にビルドしてベンチマークを実行しないと、どちらが良いかわかりません。

Answer 2

equals（）とhashCode（）のオーバーライドは疑わしいようです。元の遷移はequals（）に従ってセット内の遷移と一致しますが、2つは交換可能ではありません（それ以外の場合は、単に新しいオリジナルの代わりに移行します。）

おそらく、他の属性を持たない状態とシンボルの単なる組み合わせであるクラスが必要であり、それをマップのキーとして使用します。または、Map<State, Map<Symbol, State>>

を使用できます

Answer 3

Setはおそらくあなたが必要とするものではないというマシュー・ブルベーカーに同意します。代わりにenumsを試してください。例については、 Java用語集を参照してください。

Answer 4

状態の外部コレクション、またはTransistionオブジェクトさえも持たずにこれを達成することはできませんか？ Stateクラスが次のように定義されている場合：

public class State
{
    private Map<Symbol, State> transitions = new HashMap<Symbol, State>();

    public State() { /* populate transitions somehow */ }

    public State nextState(Symbol symbol) { return transitions.get(symbol); }
}

その後、初期状態への参照がある場合、次のように状態から状態に移動できます。

State initial = getInitialStateSomehow();
State second = initial.nextState(SYMBOL_1);
State third = initial.nextState(SYMBOL_2);  // etc...

Answer 5

ええ、なぜコレクションが必要なのか、ちょっと混乱しています。

単純なステートマシンの場合、静的整数とcaseステートメントを使用して、次のようにステートマシンを実行できます。

int STATE1 = 1; 
int STATE2 = 2;
int STATE3 = 3;
int STATE4 = 4;

int currentstate = STATE1 ;
int input = nextInput();


while(currentstate != STATE4 ){
   switch(input){
      case STATE1: 
          if(input == 'a') currentstate = STATE2; 
          break;
      case STATE2: 
          if(input == 'b') currentstate = STATE3;
          else currentstate = STATE1;
          break;
      case STATE3: 
          if(input == 'c')  currentstate = STATE4;
          else currentstate = STATE1;
      }
 }

これは、「abc」を含む文字列を検索する基本的な状態マシンです。それを簡単に拡張して、ab * cまたは必要なものを探すこともできます。

では、実行時に構築される動的な状態マシンが必要な場合はどうでしょうか？まあ、私もこれをやった。難しくありません。私がしたことは、遷移のリストを持つ状態クラスを作成することです。各遷移には、次の状態へのポインターと、リンクする基準があります。

たとえば、STATE1には、条件 'a'を持つ遷移と、STATE2を表すオブジェクトへのポインターがあります。コードは、条件（パラメーターとしてintを受け取り、一致する場合はtrueまたはfalseを返すオブジェクトである可能性があります）を確認し、条件が一致した場合、状態ポインターを遷移によってポイントされた状態に移動します。

コードは次のようになります

public void move(int input){
   for(transition t : currentState.transitions){
      if(t.getCriteria().matches(input)){
         currentState = t.getNextState();
         break;
      }
   }
}

Answer 6

パターンマッチングエンジンを実装するだけの場合、パターンが変更される可能性は低いため、状態設計パターンは不要な場合があります。 Chadが指摘したように、このような場合には switch を使用して遷移関数をエンコードすることは完全に受け入れられます。

セットを使用する非決定的なパターンマッチングオートマトンの例を次に示します。

public boolean validate() {
    Set<Integer> currentStates = new HashSet<Integer>();
    final Set<Integer> acceptingStates = new HashSet<Integer>();

    currentStates.add(0); // Initial state.
    acceptingStates.add(1);
    acceptingStates.add(3);
    acceptingStates.add(6);

    for (int i = 0; i < getInput().length(); i++) {
        char c = getInput().charAt(i);
        Set<Integer> newStates = new HashSet<Integer>();

        for (int state : currentStates) {
            switch (state) {
                case 0:
                    if (c == 'a')
                        newStates.add(1);
                    break;
                case 1:
                    if (c == 'b') {
                        newStates.add(2);
                        newStates.add(4);
                    }
                    break;
                case 2:
                    if (c == 'b')
                        newStates.add(3);
                    break;
                case 3:
                    if (c == 'b')
                        newStates.add(2);
                    break;
                case 4:
                    if (c == 'b')
                        newStates.add(5);
                    break;
                case 5:
                    if (c == 'b')
                        newStates.add(6);
                    break;
                case 6:
                    if (c == 'b')
                        newStates.add(4);
                    break;
            }
        }

        if (newStates.size() == 0)
            return false;
        currentStates = newStates;

        System.out.printf("Character read: %c\n", c);
        System.out.printf("Current states: ");
        printStates(currentStates);
    }

    for (int state : acceptingStates)
        if (currentStates.contains(state))
            return true;
    return false;
}

このオートマトンは、パターン＆quot; a（bb * | bbb *）＆quot;、つまり＆＃8220; a＆＃8221;その後に2の倍数または3の倍数の＆＃8220; b＆＃8221;が続きます。