Puis-je implémenter des transitions d'état pour un DFA en Java en utilisant java.util.Set

Question

J'implémente un DFA aussi proche que possible de la définition formelle en tant qu'exercice d'apprentissage (et de matériel de blogging)

Je prévoyais d'utiliser un java.util.Set dans lequel un ensemble est impliqué dans la définition.

La définition implique un ensemble de n-uplets pour définir les transitions d'état légales: (état, symbole) - > nextState.

J'ai une classe de transition avec les membres state, symbol et nextState. J'ai mis en œuvre equals () et hashCode () pour indiquer que deux transitions sont égales si elles correspondent à l'état et au symbole. J'ai ensuite un java.util.Set d'instances de transition.

Dans mon algorithme de traitement, j'ai l'état actuel lorsque je lis le symbole suivant. Je prévoyais de créer un objet Transition en utilisant ces deux éléments pour extraire la transition correspondante de l'ensemble, qui me dirait alors l'état suivant, et je peux effectuer une itération.

Mais - je ne vois aucun moyen d'extraire un membre d'un java.util.Set pour une utilisation ultérieure. Je peux supprimer (objet o), mais cela ne fait que renvoyer un booléen.

Qu'est-ce que je fais de travers?

Answer 1

Set n’est probablement pas ce que vous voulez utiliser pour cela. Ma recommandation serait d'utiliser une liste & Lt; Transition & Gt ;, ou éventuellement une carte & Lt; Etat, liste & Lt; Transition & Gt; & Gt ;. Je ne suis pas sûr de ce qui serait mieux sans le construire et en faire une analyse comparative.

Answer 2

Il semble que votre remplacement de equals () et hashCode () soit douteux, car la transition d'origine correspond à celle de l'ensemble selon equals () et pourtant les deux ne sont pas interchangeables (sinon, vous utiliseriez simplement la nouvelle transition à la place de l'original.)

Vous voulez probablement une classe qui est juste une combinaison d'état et de symbole sans autre attribut, et l'utiliser comme clé dans une carte. Sinon, vous pouvez utiliser un Map<State, Map<Symbol, State>>

Answer 3

Je suis d’accord avec Matthew Brubaker pour dire que Set n’est probablement pas ce dont vous avez besoin. Vous voudrez peut-être essayer enums à la place; Voir le Glossaire Java pour un exemple.

Answer 4

Ne pouvez-vous pas accomplir cela sans avoir une collection d'états externe, ni même les objets Transistion? Si la classe d'état est définie comme suit:

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

Ensuite, si vous avez une référence à l'état initial, vous pouvez simplement passer d'un état à l'autre comme ceci:

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

Answer 5

Oui, je suis un peu perplexe quant à la raison pour laquelle nous aurions même besoin d'une collection.

Pour une machine à états simple, vous pouvez simplement utiliser des entiers statiques et une instruction case pour faire votre machine à états comme ceci:

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

C'est une machine d'état basique qui recherchera toute chaîne contenant 'abc'. Vous pouvez facilement prolonger cela aussi chercher ab * c ou ce que vous voulez.

Et si vous voulez une machine à états dynamique, construite au moment de l'exécution? Eh bien, j'ai fait ça aussi. Ce n'est pas trop dur Ce que j'ai fait est de créer une classe d'état avec une liste de transitions. Chaque transition comporte un pointeur sur l'état suivant et les critères de liaison.

Ainsi, par exemple, STATE1 aurait une transition avec les critères "a" et un pointeur sur un objet qui représente STATE2. Le code chercherait à vérifier les critères (qui pourrait être un objet qui prend un int comme paramètre et renvoie true ou false s'il correspond) et si les critères correspondent, il déplace le pointeur d'état sur l'état indiqué par la transition.

Le code pourrait ressembler à cela

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

Answer 6

Si vous souhaitez simplement implémenter un moteur de correspondance de modèle, un modèle de conception d'état peut être inutile, car il est peu probable que le modèle change. Comme l'a souligné Chad, utiliser un commutateur pour coder la fonction de transition est tout à fait acceptable dans de tels cas.

Voici un exemple d'automate de recherche de motifs non déterministe qui utilise des ensembles:

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

Cet automate reconnaît les mots d'entrée du langage usuel décrit par le modèle "a (bb * | bbb *) ", c'est-à-dire un «a» suivi d'un multiple de deux ou d'un multiple de trois nombreux "b" s.