3

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

セットが定義に含まれるjava.util.Setを使用することを計画しました。

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

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

私の処理アルゴリズムでは、次のシンボルを読み取るときに現在の状態になります。これら2つを使用してTransitionオブジェクトを作成し、一致するTransitionをセットから引き出すことを期待していました。これにより、次の状態が通知され、反復できます。

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

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

4

6 に答える 6

2

セットはおそらくあなたがこれに使用したいものではありません。私の推奨は、List <Transition>、または場合によってはMap <State、List<Transition>>を使用することです。実際にビルドしてベンチマークを実行しないと、どちらが良いかわかりません。

于 2009-01-14T22:08:27.610 に答える
1

equals（）とhashCode（）のオーバーライドは疑わしいように聞こえます。これは、元のトランジションがequals（）に従ってセット内のトランジションと一致しているにもかかわらず、2つは互換性がないためです（そうでない場合は、新しいトランジションをそのまま使用します）。オリジナルの。）

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

于 2009-01-14T22:14:44.087 に答える
1

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

于 2009-01-14T22:15:29.763 に答える
1

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

単純なステートマシンの場合、静的整数と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;
      }
   }
}

于 2009-01-14T22:31:56.113 に答える
1

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

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

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;
}

このオートマトンは、パターン「」で記述された正規言語の入力単語を認識します"a(bb*|bbb*)。つまり、「a」の後に2の倍数または3の倍数の多くの「b」が続きます。

于 2009-01-14T22:40:42.227 に答える
1

状態の外部コレクションや 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...
于 2009-01-14T22:20:23.670 に答える